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)