Präfixsumme

In der Informatik ist die Präfixsumme einer Folge von Zahlen a₀, a₁, a₂, … die Zahlenfolge s₀, s₁, s₂, … ihrer Partialsummen:

Beispielsweise ist die Präfixsumme der natürlichen Zahlen die Folge der Dreieckszahlen:

Eingabefolge	1	2	3	4	5	6	…
Präfixsumme	1	3	6	10	15	21	…

Die Präfixsumme ist mit einer einfachen Schleife sequenziell berechenbar, indem mit der Formel

für i>0 jeder Summenwert sukzessive aufaddiert wird. Die Präfixsumme bildet die Grundlage für Algorithmen wie den Countingsort. Sie kann statt der Summierung als Basisoperation eine allgemeine assoziative binäre Operation verwenden, womit sie beispielsweise zur Polynominterpolation oder zur Stringbearbeitung eingesetzt und in der funktionalen Programmierung auf Funktionen höherer Ordnung angewandt werden kann; in diesem Falle wird sie auch Scan genannt. Da die Präfixsumme mit dem Fork-join-Modell zudem effizient auf Mehrkernprozessorsystemen und Rechnerclustern berechnet werden kann, spielt sie in Betrachtungen zu parallelen Algorithmen eine wichtige theoretische und praktische Rolle, als zu lösendes Testproblem ebenso wie als Subroutine wichtiger paralleler Algorithmen.

Mathematisch kann die Berechnung der Präfixsumme von endlichen auf unendliche Folgen verallgemeinert werden. Sie stellt dann eine Reihe dar. Die Präfixsummierung ist ein linearer Operator auf einem Vektorraum endlicher oder unendlicher Folgen. Seine Inverse ist ein Differenz-Operator.

Präfixoperationen (Scans) von Funktionen höherer Ordnung

Die eigentliche Präfixsumme basiert auf der binären Operation der Addition. In der funktionalen Programmierung kann die Präfixsumme auf jede binäre assoziative Operation verallgemeinert werden, also statt einer Präfixsumme eine Präfixoperation darstellen. (Allerdings wird oft der Begriff „Präfixsumme“ auch dafür verwendet.) Die aus dieser Verallgemeinerung resultierende Präfixoperation ist eine Funktion höherer Ordnung und wird auch Scan genannt. Zum Beispiel kann die Folge der Fakultäten (a_k) als Präfixprodukt berechnet werden, indem die Addition durch die Multiplikation ersetzt wird:

Eingabefolge	1	2	3	4	5	6	…
Präfixprodukt	1	2	6	24	120	720	…

Die Scan-Operation ist daher ähnlich der Reduce-Operation, allerdings liefert Scan die gesamte Folge der Partialoperationen, während Reduce nur den Wert der letzten Partialoperation als Ergebnis liefert.

In Haskell gibt es zwei Varianten von Scan, nämlich scanl und scanl1. Die prozeduralen MPI-Bibliotheken bieten eine Operation MPI_Scan an, um eine Scan-Operation zwischen vernetzten Processoreinheiten zu berechnen. Die Programmiersprache C++ hat eine Funktion partial_sum in ihrer Standardbibliothek, welche, trotz ihres Namens, eine Scan-Operation mit einer beliebigen binären Operation ausführt. Die Programmiersprache Java bietet (ab der Version 1.8) in dem Standardpaket java.util.Arrays eine Methode parallelPrefix in mehreren Varianten an, die neben dem zu bearbeitenden Array einen binären Operator erwartet. Die Präfixsumme eines Arrays a[k] wird damit durch die folgende Anweisung berechnet und in dem Eingabearray gespeichert:

Arrays.parallelPrefix(a, (x,y) -> x + y); 

Der binäre Operator ist hier als Lambda-Ausdruck, also eine anonyme Funktion mit zwei Parametern angegeben. Entsprechend kann die Fakultät nach obigem Beispiel als Präfixprodukt

Arrays.parallelPrefix(a, (x,y) -> x * y); 

programmiert werden.

Parallele Berechnung

Abfolge der Rechenschritte einer parallelen Präfixsumme mit 16 Eingabeeinträgen

Mit Hilfe des Fork-join-Modells kann eine Präfixsumme mit den folgenden Schritten effizient parallel berechnet werden.

1. Berechne die Summen der aufeinanderfolgenden Paareinträge, in denen der erste Eintrag jeweils einen geraden Index hat: z₀ = a₀ + a₁, z₁ = a₂ + a₃, ….
2. Berechne rekursiv die Präfixsumme w₀, w₁, w₂, … der Folge z₀, z₁, z₂, ….
3. Drücke jeden Term der Ergebnisfolge s₀, s₁, s₂, … als die Summe von höchstens zwei Termen dieser Zwischenfolge aus: y₀ = a₀, y₁ = z₀, y₂ = z₀ + a₂, y₃ = w₀ etc. Nach dem ersten Wert ist jede sukzessive Zahl y_i entweder eine Kopie des Werts mit halb so großem Index in der Folge w, oder sie ist der vorherige Wert plus einem Wert in der originalen Folge a.

Hat die Eingabefolge n Einträge, so schreitet die Rekursion bis zu einer Tiefe von O(log n) fort, was ebenso die Begrenzung der parallelen Laufzeit darstellt. Die Anzahl der Schritte des Algorithmus beträgt O(n) und kann auf einer PRAM mit O(n/log n) Prozessoren implementiert werden, indem in Runden, in denen mehr Einträge als Prozessoren vorhanden sind, einem Prozessor einfach mehrere Indizes zugewiesen werden.

Parallele Algorithmen für Präfixsummen können auf andere Präfixoperationen (Scans) assoziativer binärer Operationen verallgemeinert werden. Sie laufen effizient auf paralleler Hardware wie Mehrkernprozessoren, GPU's oder Rechnerclustern ab. Viele parallele Implementierungen verwenden dazu zwei Durchgänge: im ersten Durchgang werden die partiellen Präfixsummen auf jeder Prozessoreinheit berechnet; die Präfixsumme dieser Teilsummen wird dann berechnet und zum zweiten Durchgang an die einzelnen Prozessoreinheiten zurückgesendet, die nun mit dem bekannten Präfix als Anfangswert weiterrechnen. Asymptotisch angenähert erfordert diese Methode etwa zwei Lese- und eine Schreiboperation pro Eintrag.

Anwendungen

• Countingsort ist ein Algorithmus zur Sortierung einer Folge ganzer Zahlen, der die Präfixsumme eines Histogramms der Schlüsselhäufigkeiten verwendet, um die Position jedes Schlüssels in der sortierten Ausgabefolge zu bestimmen. Der Algorithmus hat lineare Zeitkomplexität O(n) für ganzzahlige Schlüsselwerte, die kleiner als die Anzahl Einträge sind, und ebenso lineare Speicherkomplexität. Countingsort wiederum kann eine von zwei möglichen Subroutinen für den Radixsort.
• List ranking ist das Problem, eine verkettete Liste in ein Array derselben Elementfolge zu transformieren. Es kann durch Berechnung einer Präfixsumme der Folge 1, 1, 1, … und der Zuordnung jedes Listenelements zu seinem Präfixsummenwert als Array-Index. Durch Kombination von List Ranking, Präfixsumme und Eulerkreise können viele wichtige Probleme an Baumstrukturen effizient durch parallele Algorithmen gelöst werden.
• Parallele Präfixsummenalgorithmen können für den Entwurf von Addierwerken verwendet werden, also Boole’schen Schaltnetzen, die zwei n-stellige Binärzahlen addieren. Hierbei kann eine Folge von Übertragbits als eine Präfixoperation der Konjunktion der Folge von Bitpaaren berechnet werden; jedes Bit der Ergebniszahl ist dann ein XOR der beiden Eingabebits und des zugehörigen Übertragbits. Damit kann man ein paralleles Addierwerk für n-stellige Binärzahlen mit O(n) Logikgattern and O(log n) Rechenschritten realisieren.
• Der Gray-Code einer ganzen binären Zahl n kann einfach durch Berechnung des XOR von n und n/2 (also der Rechtsverschiebung von n um ein Bit) gebildet werden. Die inverse Operation, also die Dekodierung eines Gray-Codes x in eine Binärzahl, kann als Präfixsumme der Bits von x modulo 2 ausgedrückt werden, also als Präfixoperation mit der assoziativen XOR-Funktion .
• Parallele Präfixprodukte (mit der Multiplikation als assoziative Operation) können als Baustein von schnellen parallelen Algorithmen zur Polynominterpolation eingesetzt werden. Insbesondere können sie zur Koeffizientenberechnung nach dem Schema der dividierten Differenz im Newton’schen Algorithmus verwendet werden. Ähnlich kann die Hermite-Interpolation oder die Interpolation von Funktionen mit Hilfe der Vandermonde-Matrizen effizient parallel berechnet werden.

Siehe auch

• Reihe (Mathematik)

Weblinks

• Eric W. Weisstein: Cumulative Sum. In: MathWorld (englisch).

Einzelnachweise

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, McGraw-Hill, 2001, ISBN 0-262-03293-7, 8.2 Counting Sort, S. 168–170. 
2. Guy Blelloch: Prefix Sums and Their Applications (Lecture Notes). Carnegie Mellon University, 2011 (Online [PDF]). 
3. Paul Callahan, S. Rao Kosaraju: A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. In: Journal of the ACM. Band 42, Nr. 1, 1995. 
4. A. de Vries (2014): Funktionale Programmierung und Streams in Java (PDF) Einführendes Vorlesungsskript Wirtschaftsinformatik, FH Südwestfalen Hagen, § 3
5. R. E. Ladner, M. J. Fischer: Parallel Prefix Computation. In: Journal of the ACM. Band 27, Nr. 4, 1980, S. 831–838, doi:10.1145/322217.322232. 
6. Robert E. Tarjan, Uzi Vishkin: An efficient parallel biconnectivity algorithm. In: SIAM Journal on Computing. Band 14, Nr. 4, 1985, S. 862–874, doi:10.1137/0214061. 
7. S. Lakshmivarahan, S.K. Dhall: Parallelism in the Prefix Problem. Oxford University Press, 1994, ISBN 0-19-508849-2. 
8. Haskell 98 Language and Libraries: The Revised Report. 2002, Standard Prelude (Online). 
9. Java SE 8 API (2014)
10. Yuri Petrovich Ofman: Об алгоритмической сложности дискретных функций. In: Doklady Akademii Nauk SSSR. Band 145, Nr. 1, 1962, S. 48–51 (russisch, English translation, On the algorithmic complexity of discrete functions. In: Soviet Physics Doklady, 7, S. 589–591 1963). 
11. V. M. Khrapchenko: Asymptotic Estimation of Addition Time of a Parallel Adder. In: Problemy Kibernet. Band 19, 1967, S. 107–122 (russisch, English translation in: Syst. Theory Res., 19, 1970, S. 105–122). 
12. Shubhabrata Sengupta, Mark Harris, Yao Zhang, John D. Owens: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. 2007, Scan primitives for GPU computing, S. 97–106 (Online). 
13. Henry S. Warren: Hacker’s Delight. Addison-Wesley, 2003, ISBN 978-0-201-91465-8, S. 236 (Google Books). 
14. O. Eğecioğlu, E. Gallopoulos, C. Koç: A parallel method for fast and practical high-order Newton interpolation. Band 30, Nr. 2, 1990, S. 268–288, doi:10.1007/BF02017348 (BIT Computer Science and Numerical Mathematics). 
15. O. Eğecioğlu, E. Gallopoulos, C. Koç: Fast computation of divided differences and parallel Hermite interpolation. In: Journal of Complexity. Band 5, 1989, S. 417–437, doi:10.1016/0885-064X(89)90018-6.