Reduktions-Operator

Grundidee der Reduktion

Ein Reduktions-Operator (englisch: Reduction Clause) fasst die Elemente eines Arrays zu einem einzelnen Ergebnis zusammen. Er ist wichtig für parallele Programmierung: Mehrere Kerne lösen Teilaufgaben gleichzeitig; anschließend werden ihre Teilergebnisse zum Gesamtergebnis kombiniert. So lassen sich bestimmte eigentlich serielle Berechnungen parallelisieren und die Zahl der Berechnungsschritte verringern.

Ein solcher Operator speichert Teilresultate zunächst in privaten Kopien einer Variablen. Am Ende werden diese zu einer gemeinsamen Kopie zusammengeführt. Ein Operator ist ein Reduktions-Operator, wenn er erstens ein Array auf einen einzelnen Wert reduzieren kann und zweitens das Endergebnis aus den Teilergebnissen gebildet werden kann. Dies gilt für Operatoren, die assoziativ und kommutativ sind: Assoziativ bedeutet, dass unterschiedliche Klammerungen dasselbe Ergebnis liefern; kommutativ bedeutet, dass die Reihenfolge der Operanden keine Rolle spielt. Beispiele sind Addition, Multiplikation sowie logisches und und oder.

Reduktionen sind unter anderem Bestandteil von MapReduce. Sie werden außerdem in anderen parallelen Algorithmen als grundlegende Operation eingesetzt und können teilweise auch zur Verteilung von Daten auf alle Prozessoren dienen.

Vektorreduktion und Summe als Beispiel

Für p Vektoren v₀, v₁, …, vₚ₋₁ mit jeweils m Elementen kann ein Reduktions-Operator ⊕ elementweise angewendet werden. Das Ergebnis r enthält an jeder Position die Verknüpfung aller entsprechenden Vektorelemente, also beispielsweise r = (⊕ᵢ₌₀ᵖ⁻¹ eᵢ⁰, …, ⊕ᵢ₌₀ᵖ⁻¹ eᵢᵐ⁻¹)ᵀ. Es muss nach der Ausführung bei einem festgelegten Prozessor gespeichert sein. Soll es bei allen Prozessoren verfügbar sein, heißt die Operation häufig Allreduce.

Ein optimaler sequenzieller Linearzeit-Algorithmus kombiniert die Vektoren nacheinander; nach jeder Kombination verringert sich ihre Anzahl um eins. Dafür werden (p−1)·m Schritte benötigt. Parallele Algorithmen können diese Laufzeit verkürzen.

Beim Array [2,3,5,1,7,6,8,4] ergibt die serielle Reduktion mit Addition: ((((((2+3)+5)+1)+7)+6)+8)+4 = 36. Mit vier Kernen lassen sich zunächst (2+3), (5+1), (7+6) und (8+4) berechnen, dann (5+6) und (13+12) und zuletzt (11+25)=36. Ein Binärbaum benötigt damit log₂8=3 statt 7 Schritte. Die Rechnung ist ((2+3)+(5+1))+((7+6)+(8+4)); wegen der Assoziativität der Addition ist ihr Ergebnis gleich. Kommutativität ist besonders wichtig, wenn ein Hauptkern Teilaufgaben verteilt und Ergebnisse in wechselnder Reihenfolge zurückkommen.

Matrixmultiplikation ist nicht kommutativ und daher kein Reduktions-Operator im genannten Sinn. Sie ist aber assoziativ. Wenn die Teilergebnisse, etwa durch einen Binärbaum, in der richtigen Reihenfolge kombiniert werden, bleibt das Endergebnis korrekt.

Binomialbaum im gemeinsamen Speicher

Der PRAM-Algorithmus (Parallel Random Access Machine) arbeitet mit gemeinsamem Speicher und p Kernen, wobei p eine Zweierpotenz ist. Zu Beginn gilt xᵢ=vᵢ. In jeder von ⌈log₂p⌉ Iterationen kombiniert ein aktiver Kern seinen Vektor mit dem eines passenden anderen Kerns; die andere Hälfte der Kerne wird inaktiv. Die Entscheidung ergibt sich aus dem k-ten niedrigstwertigen Bit des Kernindexes i. Ein aktiver Kern mit nicht gesetztem Bit kombiniert gegebenenfalls xᵢ mit xᵢ₊₂ᵏ, während Kerne mit gesetztem Bit inaktiv werden.

Für Vektoren ist der verwendete Operator ⊕* elementweise definiert: (eᵢ⁰,…,eᵢᵐ⁻¹)ᵀ ⊕* (eⱼ⁰,…,eⱼᵐ⁻¹)ᵀ = (eᵢ⁰⊕eⱼ⁰,…,eᵢᵐ⁻¹⊕eⱼᵐ⁻¹)ᵀ. Die Struktur ist ein Binomial-Baum. Am Ende liegt das Ergebnis nur bei p₀; ein anschließender Broadcast ist nötig, wenn alle Kerne das Resultat erhalten sollen. Ist p keine Zweierpotenz, kann die Anzahl bis zur nächsten Zweierpotenz aufgefüllt werden; dafür gibt es auch spezielle Algorithmen.

Jeder parallele Durchlauf dauert O(m), daher ist die parallele Laufzeit T(p,m)=O(log(p)·m). Exclusive Read, Exclusive Write kann Schreib-Lese-Konflikte vermeiden. Der Speedup erfüllt S(p,m)∈O(Tseq/T(p,m))=O(p/log(p)); die Effizienz ist E(p,m)∈O(S(p,m)/p)=O(1/log(p)). Sie sinkt, weil im Schritt i nur noch p/2ⁱ Kerne aktiv sind.

Verteilter Speicher und Pipeline

Bei verteiltem Speicher gibt es keinen gemeinsamen Speicher. Deshalb senden in der Binomialbaum-Variante die inaktiv werdenden Kerne ihre lokalen Daten ausdrücklich an andere Kerne. Ein empfangender Kern kombiniert sie anschließend mit seinem eigenen Vektor. Das Grundprinzip und die Zahl der logarithmischen Stufen entsprechen dem PRAM-Verfahren, aber Kommunikation verursacht zusätzlichen Aufwand.

Im BSP-Modell berücksichtigt die Laufzeit die Startzeit Tstart eines Datenaustauschs und die Übertragungszeit Tbyte pro Byte. Für die Binomialbaum-Reduktion beträgt sie Θ((Tstart+n·Tbyte)·log(p)), wobei m Elemente eines Vektors zusammen die Größe n haben.

Der Pipeline-Algorithmus ist für verteilte Speicher besonders sinnvoll, wenn Tstart klein gegenüber Tbyte ist. Er nutzt aus, dass Vektoren in einzelne Elemente oder logisch gebildete Gruppen zerlegt werden können. Benachbarte Kerne senden und empfangen diese Teile stufenweise und verrechnen sie; Senden und Empfangen müssen gleichzeitig erfolgen. Das Ergebnis liegt am Ende bei pₚ₋₁.

Die parallele Ausführung benötigt p+m−2 Schritte: p−1 Schritte, bis der letzte Kern das erste Element erhält, und m−1 weitere, bis alle Elemente angekommen sind. Die Laufzeit lautet T(n,p,m)=(Tstart+(n/m)Tbyte)(p+m−2). Durch Gruppieren von Elementen kann m verkleinert werden, während n gleich bleibt; das tauscht mehr Daten pro Schritt gegen weniger Schritte. Bei bekannten Tstart und Tbyte ist optimal: m=√(n·(p−2)Tbyte/Tstart), sofern dies ein kleineres m ergibt, das das ursprüngliche m teilt.

Einsatzgebiete

Reduktion gehört zu den wichtigsten kollektiven Operationen im Message Passing Interface (MPI). MPI_Reduce und MPI_Allreduce nehmen Operatoren als Parameter entgegen. Bei MPI_Reduce liegt das Ergebnis nur bei einem Kern vor, bei MPI_Allreduce bei allen Kernen. Die Leistungsfähigkeit der jeweiligen Algorithmen wird für unterschiedliche Anwendungsfälle fortlaufend untersucht.

Effiziente Reduktionsalgorithmen sind auch für MapReduce wichtig, damit große Datensätze selbst in großen Clustern verarbeitet werden können. Einige parallele Sortieralgorithmen verwenden Reduktionen ebenfalls zur Verarbeitung großer Datenmengen.