User:AnastasiaSlobodyanik/Reduktions-Operator

In der Informatik bezeichnet ein Reduktions-Operator[1] einen Operator welcher oft in der parallelen Programmierung eingesetzt wird, um Elemente eines Arrays auf ein einzelnes Ergebnis zu reduzieren. Reduktions-Operatoren sind assoziativ und häufig (aber nicht immer) kommutativ.[2][3][4] Die Reduktion von Mengen ist ein wichtiger Bestandteil von Programmiermodellen wie MapReduce, in welchen ein Reduktions-Operator auf alle Elemente angewendet wird bevor sie reduziert werden. Andere parallele Algorithmen benutzen Reduktions-Operatoren als primäre Operationen, um komplexere Probleme zu lösen. Viele dieser Operatoren können auch benutzt werden, um Daten auf alle Prozessoren zu verteilen.

Theorie

edit

Ein Reduktions-Operator kann dabei helfen, ein Problem in viele Teilprobleme aufzuteilen, indem die Lösungen der Teilprobleme genutzt werden, um das finale Ergebnis zu erhalten. Sie ermöglichen es, bestimmte serielle Operationen parallel auszuführen und dadurch die Anzahl der notwendingen Berechnungsschritte zu reduzieren. Ein Reduktions-Operator speichert die Ergebnisse der Teilprobleme in einer privaten Kopie der Variable. Diese privaten Kopien werden am Ende zu einer gemeinsamen Kopie zusammengeführt.

Ein Operator ist ein Reduktions-Operator, falls

  • er ein Array auf einen einzelnen Wert reduzieren kann[2] und
  • das finale Ergebnis aus den Teilergebnissen erhalten werden kann.[2]

Diese beiden Voraussetzungen sind für kommutative und assoziative Operatoren erfüllt, welche auf alle Elemente des Arrays angewendet werden.

Beispiele hierfür sind die Addition und Multiplikation sowie bestimmte logische Operatoren (und, oder etc.).

Ein Reduktions-Operator   kann in konstanter Zeit auf eine Menge   von   Vektoren mit jeweils   Elementen angewendet werden. Das Ergebnis   der Operation ist die Kombination der Elemente   und muss nach der Ausführung bei einem designierten Prozessor gespeichert werden. Wenn das Ergebnis   auf allen Prozessoren zur Verfügung stehen soll, wird dies oft Allreduce genannt. Ein optimaler sequenzieller Linearzeit-Algorithmus für Reduktion kann nach und nach von vorne nach hinten angewendet werden, wobei jeweils zwei Vektoren mit dem Ergebnis der Operation auf diese Vektoren ersetzt werden, wobei die Menge der Vektoren jedes Mal um eins reduziert wird. Hierfür werden   Schritte benötigt. Sequenzielle Algorithmen sind nicht schneller als Linearzeit-Algorithmen, parallele Algorithmen hingegen können die Laufzeit verkürzen.

Beispiel

edit

Gegeben sei ein Array  . Die Summe des gesamten Arrays can seriell berechnet werden, indem das Array sequenziell auf eine einzelne Summe mit Hilfe des '+' Operators reduziert wird. Startet man von vorne, ergibt sich folgende Berechnung:

 

Da '+' sowohl assoziativ als auch kommutativ ist, ist '+' ein Reduktions-Operator. Daher kann diese Reduktion auch parallel auf mehreren Kernen erfolgen, wobei jeder Kern nur die Summe einer Teilmenge des Arrays berechnet und der Reduktions-Operator diese Teilergebnisse zusammenführt. Mit Hilfe eines Binärbaums können auf 4 Kernen jeweils  ,  ,   und   berechnet werden. Daraufhin können zwei Kerne   und   berechnen und am Ende berechnet ein einzelner Kern  . Mit 4 Kernen kann die Summe also in   statt   Schritten berechnet werden, wie es bei dem seriellen Algorithmus der Fall ist. Der Algorithmus berechnet  , was auf Grund der Assoziativität der Addition dem gleichen Ergebnis entspricht. Die Kommutativität wäre wichtig, wenn es einen Hauptkern gäbe, welcher die Teilaufgaben auf andere Kerne verteilt, da hierbei die Teilergebnisse in unterschiedlicher Reihenfolgen zurückkommen könnten. Die Eigenschaft der Kommutativität würde hier garantieren, dass das Ergebnis weiterhin das gleiche ist.

Gegenbeispiel

edit

Matrixmultiplikation ist kein Reduktions-Operator, da diese Operation nicht kommutativ ist. Würden die Kerne ihre Teilergebnisse in beliebiger Reihenfolge zurückgeben, wäre das Endergebnis höchstwahrscheinlich falsch. Allerdings ist Matrixmultiplication assoziativ, weshalb das Endergebnis korrekt ist, wenn man dafür sorgt, dass die Teilergebnisse in der richtigen Reihenfolge sind. Dies ist bei der Benutzung von Binärbäumen der Fall.

Algorithmen

edit

Binomial-Baum Algorithmen

edit

Bezüglich der parallelen Algorithmen gibt es hauptsächlich zwei Modelle, die Parallel Random Access Machine als eine Erweiterung des Arbeitsspeichers mit gemeinsamen Speicher zwischen den Kernen und Bulk Synchronous Parallel Computers, bei welchen die Kerne kommunizieren und synchronisiert werden. Beide Modelle haben unterschiedliche Effekte auf die Zeitkomplexität, weshalb hier beide vorgestellt werden.

PRAM-Algorithmus

edit

Dieser Algorithmus nutzt eine weit verbreitete Methode, wobei   eine Zweiterpotenz ist. Eine Umkehrung wird häufig genutzt um die Elemente zu verteilen.[5][6][7]

 
Eine Visualisierung des Algorithmus mit   und Addition als Reduktions-Operator
for   to   do
for   to   do in parallel
if   is active then
if bit   of   is set then
set   to inactive
else if  
 

Der binäre Operator für Vektoren ist elementweise definiert, sodass  . Der Algorithmus beruht außerdem auf den Annahmen, dass am Anfang   für alle   gilt und dass die Kerne   genutzt werden. In jeder Iteration wird die Hälfte der Kerne inaktiv, diese tragen nicht mehr zur Berechnung bei. Die Animation zeigt eine Visualisierung des Algorithmus mit Addition als Operator. Senkrechte Linien stellen die Kerne dar, in welchen die Berechnung der Elemente auf der Linie berechnet werden. Unten sind die acht Elemente der Eingabe dargestellt. Jeder Schritt in der Animation entspricht einem parallelen Schritt in der Ausführung des Algorithmus. Ein aktiver Kern   wendet den Operator auf ein für ihn lokal verfügbares Element   sowie   an, wobei   der kleinste Index mit   ist, sodass im aktuellen Schritt   inaktiv wird.   und   sind nicht notwendigerweise Teil der Eingabe, da diese Speicherstellen überschrieben und für vorher berechnete Ausdrücke wiederverwendet werden. Um die Kerne untereinander zu koordinieren ohne weiteren Aufwand durch Kommunikation zwischen ihnen zu ursachen, macht sich der Algorithmus die Indexierung der Kerne durch   bis   zunutze. Jeder Kern macht von seinem  -ten least significant bit abhängig, ob er inaktiv wird oder den Operator auf sein eigenes Element sowie das Element mit dem Index, bei welchem das  -te last significant bit nicht gesetzt ist, anwendet. Das zugrundeliegende Schema hierfür ist ein Bionomial-Baum, daher der Name des Algorithmus.

Am Ende das Algorithmus liegt das Ergebnis nur   vor. Für eine Allreduce-Operation muss das Ergebnis allen Kernen vorliegen, was durch einen anschließenden Broadcast ermöglicht wird. Die Anzahl der Kerne   sollte eine Zweiterpotenz sein, ansonsten kann die Anzahl bis zur nächsten Zweierpotenz aufgefüllt werden. Es gibt Algorithmen, welche speziell auf diesen Fall zugeschnitten sind.[8]

Laufzeitanalyse
edit

Die äußerste Schleife wird   Mal ausgeführt. Die Zeit für jeden parallelen Durchlauf liegt in  , da jeder Kern entweder zwei Vektoren kombiniert oder inaktiv wird. Daher gilt für die parallele Zeit  . Um Schreib-Lese-Konflikte zu vermeiden, kann Exclusive Read, Exclusive Write verwendet werden. Für den Speedup gilt  , daher gilt für die Effizienz  . Die Effizienz leidet unter der Tatsache, dass in jedem Schritt die Hälfte aller Kerne inaktiv wird, d.h. im Schritt   sind   Kerne aktiv.

Verteilte Speicher Algorithmen

edit

Im Gegensatz zu den PRAM-Algorithmen, teilen sich die Kerne hier keinen gemeinsamen Speicher. Daher müssen die Daten explizit zwischen den Kernen ausgetauscht werden, wie der folgende Algorithmus zeigt.

for   to   do
for   to   do in parallel
if   is active then
if bit   of   is set then
send   to  
set   to inactive
else if  
receive  
 

Der einzige Unterschied zu der PRAM Version von oben liegt in der Verwendung von expliziten Primitiven für die Kommunikation. Das Prinzip bleibt jedoch das gleiche.

Laufzeitanalyse
edit

Die Kommunikation zwischen den Kernen verursacht etwas Overhead. Eine einfache Analyse des Algorithmus nutzt das BSP-Modell und beachtet die notwendige Zeit  , um einen Datenaustausch zu initiieren sowie die notwendige Zeit  , um ein Byte Daten zu senden. Die resultierende Laufzeit ist dann  , wobei   Elemente eines Vektors die Größe   haben.

Pipeline Algorithmus

edit
 
Visualization of the pipeline-algorithm with p = 5, m = 4 and addition as the reduction operator.

Für die verteilte Speicher Modelle kann es Sinn ergeben, die Daten in Form einer Pipeline auszutauschen. Dies gilt insbesondere, wenn   klein im Vergleich zu   ist. Normalerweise teilen lineare Pipelines die Daten in kleinere Teile auf und verarbeiten diese stufenweise. Im Gegensatz zu den Bionomial-Baum Algorithmen macht sich der Pipeline Algorithmus die Tatsache zunutze, dass Vektoren nicht untrennbar sind: Der Operator kann auch auf einzelne Elemente anwendet werden.[9]

for   to   do
for   to   do in parallel
if  
send   to  
if  
receive   from  
 

Es ist wichtig, dass das Senden und Empfangen gleichzeitig ausgeführt wird, damit der Algorithmus korrekt funktioniert. Das Ergebnis befindet sich am Ende in  . Die Animation zeigt die Ausführung des Algorithmus auf Vektoren der Größe 4 mit 5 Kernen. Zwei Schritte in der Animation entsprechen einem Schritt in der parallelen Ausführung.

Runtime analysis

edit

Die Anzahl der Schritt in der parallelen Ausführung beträgt  , es braucht   Schritte bis der letzte Kern sein erstes Element erhält und weitere   Schritte, bis alle Elemente angekommen sind. Im BSP-Modell beträgt die Laufzeit daher  , wobei   die Größe eines Vektors in Bytes ist.

Auch wenn   ein fester Wert ist, so ist es möglich, Elemente von Vektoren logisch zu gruppieren und dadurch   zu reduzieren. Zum Beispiel kann eine Probleminstanz mit Vektoren der Länge vier gelöst werden, indem die Vektoren in ihre ersten und letzten beiden Elemente aufgeteilt werden, welche dann immer gemeinsam gesendet und verrechnet werden. In diesem Fall werden in jedem Schritt doppelt so viele Daten gesendet, allerdings hat sich die Anzahl der Schritte etwa auf die Hälfte verringert.   ist also halbiert, während die Größe in Bytes   gleich bleibt. Die Laufzeit   für diesen Ansatz hängt also von   ab, was optimiert werden kann, wenn   und   bekannt sind. Es ist optimal für  , wobei angenommen wird, dass dies in einem kleineren   resultiert, welches das ursprüngliche teilt.

Anwendungen

edit

Reduktion ist eine der wichtigsten kollektiven Operationen im Message Passing Interface, wo die Leistung des genutzen Algorithmus wichtig ist und ständig für verschiedene Anwendungsfälle ausgewertet wird.[10] Operatoren können als Parameter für MPI_Reduce und MPI_Allreduce verwendet werden, wobei der Unterschied darin liegt, ob das Ergebnis am Ende in allen oder nur einem Kern vorliegt. Für MapReduce sind effiziente Reduktions-Algorithmen wichtig, um große Datensätze zu verarbeiten, auch in großen Clustern.[11][12]

Manche parallele Sortieralgorithmen nutzen Reduktionen um große Datensätze zu verarbeiten.[13]

Literatur

edit
  • Chandra, Rohit (2001). Parallel Programming in OpenMP. Morgan Kaufmann. pp. 59–77. ISBN 1558606718.
  • Solihin, Yan (2016). Fundamentals of Parallel Multicore Architecture. CRC Press. p. 75. ISBN 978-1-4822-1118-4.
edit

Category:Computer science

Einzelnachweise

edit
  1. ^ Reduction Clause
  2. ^ a b c Solihin
  3. ^ Chandra p. 59
  4. ^ Cole, Murray (2004). "Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming". Parallel computing. 30: 393.
  5. ^ Bar-Noy, Amotz; Kipnis, Shlomo (1994). "Broadcasting multiple messages in simultaneous send/receive systems". Discrete Applied Mathematics. 55 (2): 95–105. doi:10.1016/0166-218x(94)90001-9.
  6. ^ Santos, Eunice E. (2002). "Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines". Journal of Parallel and Distributed Computing. 62 (4): 517–543. doi:10.1006/jpdc.2000.1698.
  7. ^ Slater, P.; Cockayne, E.; Hedetniemi, S. (1981-11-01). "Information Dissemination in Trees". SIAM Journal on Computing. 10 (4): 692–701. doi:10.1137/0210052. ISSN 0097-5397.
  8. ^ Rabenseifner, Rolf; Träff, Jesper Larsson (2004-09-19). More Efficient Reduction Algorithms for Non-Power-of-Two Number of Processors in Message-Passing Parallel Systems. Lecture Notes in Computer Science. Vol. 3241. Springer, Berlin, Heidelberg. pp. 36–46. doi:10.1007/978-3-540-30218-6_13. ISBN 9783540231639. {{cite book}}: |journal= ignored (help)
  9. ^ Bar-Noy, A.; Kipnis, S. (1994-09-01). "Designing broadcasting algorithms in the postal model for message-passing systems". Mathematical Systems Theory. 27 (5): 431–452. doi:10.1007/BF01184933. ISSN 0025-5661.
  10. ^ Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E.; Gabriel, Edgar; Dongarra, Jack J. (2007-06-01). "Performance analysis of MPI collective operations". Cluster Computing. 10 (2): 127–143. doi:10.1007/s10586-007-0012-0. ISSN 1386-7857.
  11. ^ Lämmel, Ralf (2008). "Google's MapReduce programming model — Revisited". Science of Computer Programming. 70 (1): 1–30. doi:10.1016/j.scico.2007.07.001.
  12. ^ Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar A. C.; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício A.B. (2016-06-10). "BSP cost and scalability analysis for MapReduce operations". Concurrency and Computation: Practice and Experience. 28 (8): 2503–2527. doi:10.1002/cpe.3628. ISSN 1532-0634.
  13. ^ Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2014-10-24). "Practical Massively Parallel Sorting". Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. pp. 13–23. arXiv:1410.6754. doi:10.1145/2755573.2755595.