Parallele Berechnung von Präfixen über Arrays-Klasse in Java 8

Stehen mehrere Prozessoren bzw. Kerne zur Verfügung können einige Berechnungen bei Feldern parallelisiert werden. Eine Algorithmus nennt sich parallele Präfix-Berechnung und basiert auf der der Idee, dass eine assoziative Funktion – nennen wir sie f – auf eine bestimmte Art und Weise auf Elemente eines Feldes – nennen wir es a – angewendet wird, nämlich so:

· a[0]

· f(a[0], a[1])

· f(a[0], f(a[1], a[2]))

· f(a[0], f(a[1], f(a[2], a[3])))

· …

· f(a[0], f(a[1], … f(a[n-2], a[n-1])…))

In der Aufzählung sieht das etwas verwirrend aus, daher soll ein praktisches Beispiel zum Verständnis anregen. Das Feld sei [1, 3, 0, 4] und die binäre Funktion die Addition.

Index

Funktion

Ergebnis

0

a[0]

1

1

a[0] + a[1]

1 + 3 = 4

2

a[0] + (a[1] + a[2])

1 + (3+0) = 4

3

a[0] + (a[1] + (a[2] + a[3]))

1 + (3+(0+4)) = 8

Präfix-Berechnung vom Feld [1, 3, 0, 4] mit Additions-Funktion

Auf den ersten Blick wirkt das wenig spannend, doch kann der Algorithmus parallelisiert werden und somit im Besten Fall in logarithmischer Zeit (mit n Prozessoren) gelöst werden. Voraussetzung dafür ist allerdings eine assoziative Funktion, wie Summe, Maximum, … Ohne genau ins Detail zu gehen könnten wir uns vorstellen, dass ein Prozessor/Kern 0+4 berechnet, ein anderer zeitgleich 1+3, und dann das Ergebnis zusammengezählt wird.

Beispiel. Das Beispiel unserer Präfix-Berechnung mit Hilfe einer Methode aus Arrays:

int[] array = {1, 3, 0, 4};

Arrays.parallelPrefix( array, (a, b) -> a + b );

System.out.println( Arrays.toString( array ) ); // [1, 4, 4, 8]

Die Implementierung nutzt eine fortgeschrittene Syntax aus Java 8, die Lambda-Ausdrücke. statt (a + b) -> a + b kann es sogar mit Integer::sum noch verkürzt werden.

Ein weiteres Beispiel: Finde das Maximum in einer Menge von Fließkommazahlen:

double[] array = {4.8, 12.4, -0.7, 3.8 };

Arrays.parallelPrefix( array, Double::max );

System.out.println( array[array.length -1 ] ); // 12.4

Das Beispiel nutzt schon die Methode, die Arrays für die parallele Präfix-Berechnung bietet:

class java.util.Arrays

§ static void parallelPrefix(int[] array, IntBinaryOperator op)

§ static void parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op)

§ static void parallelPrefix(long[] array, LongBinaryOperator op)

§ static void parallelPrefix(long[] array, int fromIndex, int toIndex, LongBinaryOperator op)

§ static void parallelPrefix(double[] array, DoubleBinaryOperator op)

§ static void parallelPrefix(double[] array, int fromIndex, int toIndex, DoubleBinaryOperator op)

§ static <T> void parallelPrefix(T[] array, BinaryOperator<T> op)

§ static <T> void parallelPrefix(T[] array, int fromIndex, int toIndex, BinaryOperator<T> op)

Ähnliche Beiträge

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.