Reduktions-Operator

In der Informatik bezeichnet ein Reduktions-Operator (englisch: Reduction Clause) 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. 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

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 notwendigen 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 und
• das finale Ergebnis aus den Teilergebnissen erhalten werden kann.

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 $\oplus$ kann in konstanter Zeit auf eine Menge

$V=\left\{v_{0}={\begin{pmatrix}e_{0}^{0}\\\vdots \\e_{0}^{m-1}\end{pmatrix}},v_{1}={\begin{pmatrix}e_{1}^{0}\\\vdots \\e_{1}^{m-1}\end{pmatrix}},\dots ,v_{p-1}={\begin{pmatrix}e_{p-1}^{0}\\\vdots \\e_{p-1}^{m-1}\end{pmatrix}}\right\}$

von $p$ Vektoren mit jeweils $m$ Elementen angewendet werden. Das Ergebnis $r$ der Operation ist die Kombination der Elemente

$r={\begin{pmatrix}e_{0}^{0}\oplus e_{1}^{0}\oplus \dots \oplus e_{p-1}^{0}\\\vdots \\e_{0}^{m-1}\oplus e_{1}^{m-1}\oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix}}={\begin{pmatrix}\bigoplus _{i=0}^{p-1}e_{i}^{0}\\\vdots \\\bigoplus _{i=0}^{p-1}e_{i}^{m-1}\end{pmatrix}}$

und muss nach der Ausführung bei einem designierten Prozessor gespeichert werden. Wenn das Ergebnis $r$ 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 $(p-1)\cdot m$ Schritte benötigt. Sequenzielle Algorithmen sind nicht schneller als Linearzeit-Algorithmen, parallele Algorithmen hingegen können die Laufzeit verkürzen.

Beispiel

Gegeben sei ein Array $[2,3,5,1,7,6,8,4]$. 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:

$((((((2+3)+5)+1)+7)+6)+8)+4=36$

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 $(2+3)$, $(5+1)$, $(7+6)$ und $(8+4)$ berechnet werden. Daraufhin können zwei Kerne $(5+6)$ und $(13+12)$ berechnen und am Ende berechnet ein einzelner Kern $(11+25)=36$. Mit 4 Kernen kann die Summe also in $\log _{2}8=3$ statt $7$ Schritten berechnet werden, wie es bei dem seriellen Algorithmus der Fall ist. Der Algorithmus berechnet $((2+3)+(5+1))+((7+6)+(8+4))$, 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

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 Matrixmultiplikation 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

Binomial-Baum Algorithmen

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

Dieser Algorithmus nutzt eine weit verbreitete Methode, wobei $p$ eine Zweierpotenz ist. Eine Umkehrung wird häufig genutzt um die Elemente zu verteilen.

Eine Visualisierung des Algorithmus mit $p=8,m=1$ und Addition als Reduktions-Operator

for $k\gets 0$ to $\lceil \log _{2}p\rceil -1$ do

for $i\gets 0$ to $p-1$ do in parallel

if $p_{i}$ is active then

if bit $k$ of $i$ is set then

set $p_{i}$ to inactive

else if $i+2^{k}<p$

$x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}$

Der binäre Operator für Vektoren ist elementweise definiert, sodass

${\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}$.

Der Algorithmus beruht außerdem auf den Annahmen, dass am Anfang $x_{i}=v_{i}$ für alle $i$ gilt und dass die Kerne $p_{0},p_{1},\dots p_{n-1}$ 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 $p_{i}$ wendet den Operator auf ein für ihn lokal verfügbares Element $x_{i}$ sowie $x_{j}$ an, wobei $j$ der kleinste Index mit $j>i$ ist, sodass im aktuellen Schritt $p_{j}$ inaktiv wird. $x_{i}$ und $x_{j}$ 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 verursachen, macht sich der Algorithmus die Indexierung der Kerne durch $0$ bis $p-1$ zunutze. Jeder Kern macht von seinem $k$-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 $k$-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 $p_{0}$ 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 $p$ sollte eine Zweierpotenz sein, ansonsten kann die Anzahl bis zur nächsten Zweierpotenz aufgefüllt werden. Es gibt Algorithmen, welche speziell auf diesen Fall zugeschnitten sind.

Laufzeitanalyse

Die äußerste Schleife wird $\lceil \log _{2}p\rceil$ Mal ausgeführt. Die Zeit für jeden parallelen Durchlauf liegt in ${\mathcal {O}}(m)$, da jeder Kern entweder zwei Vektoren kombiniert oder inaktiv wird. Daher gilt für die parallele Zeit $T(p,m)={\mathcal {O}}(\log(p)\cdot m)$. Um Schreib-Lese-Konflikte zu vermeiden, kann Exclusive Read, Exclusive Write verwendet werden. Für den Speedup gilt

$S(p,m)\in {\mathcal {O}}\left({\frac {T_{\text{seq}}}{T(p,m)}}\right)={\mathcal {O}}({\frac {p}{\log(p)}})$,

daher gilt für die Effizienz

$E(p,m)\in {\mathcal {O}}\left({\frac {S(p,m)}{p}}\right)={\mathcal {O}}\left({\frac {1}{\log(p)}}\right)$.

Die Effizienz leidet unter der Tatsache, dass in jedem Schritt die Hälfte aller Kerne inaktiv wird, d. h. im Schritt $i$ sind ${\frac {p}{2^{i}}}$ Kerne aktiv.

Verteilte Speicher Algorithmen

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 $k\gets 0$ to $\lceil \log _{2}p\rceil -1$ do

for $i\gets 0$ to $p-1$ do in parallel

if $p_{i}$ is active then

if bit $k$ of $i$ is set then

send $x_{i}$ to $p_{i-2^{k}}$

set $p_{k}$ to inactive

else if $i+2^{k}<p$

receive $x_{i+2^{k}}$

$x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}$

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

Die Kommunikation zwischen den Kernen verursacht etwas Overhead. Eine einfache Analyse des Algorithmus nutzt das BSP-Modell und beachtet die notwendige Zeit $T_{\text{start}}$, um einen Datenaustausch zu initiieren sowie die notwendige Zeit $T_{\text{byte}}$, um ein Byte Daten zu senden. Die resultierende Laufzeit ist dann $\Theta ((T_{\text{start}}+n\cdot T_{\text{byte}})\cdot \log(p))$, wobei $m$ Elemente eines Vektors die Größe $n$ haben.

Pipeline Algorithmus

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 $T_{\text{start}}$ klein im Vergleich zu $T_{\text{byte}}$ 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.

for $k\gets 0$ to $p+m-3$ do

for $i\gets 0$ to $p-1$ do in parallel

if $i\leq k<i+m\land i\neq p-1$

send $x_{i}^{k-i}$ to $p_{i+1}$

if $i-1\leq k<i-1+m\land i\neq 0$

receive $x_{i-1}^{k+i-1}$ from $p_{i-1}$

$x_{i}^{k+i-1}\gets x_{i}^{k+i-1}\oplus x_{i-1}^{k+i-1}$

Es ist wichtig, dass das Senden und Empfangen gleichzeitig ausgeführt wird, damit der Algorithmus korrekt funktioniert. Das Ergebnis befindet sich am Ende in $p_{p-1}$. 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.

Laufzeitanalyse

Die Anzahl der Schritt in der parallelen Ausführung beträgt $p+m-2$, es braucht $p-1$ Schritte, bis der letzte Kern sein erstes Element erhält und weitere $m-1$ Schritte, bis alle Elemente angekommen sind. Im BSP-Modell beträgt die Laufzeit daher $T(n,p,m)=(T_{\text{start}}+{\frac {n}{m}}T_{\text{byte}})(p+m-2)$, wobei $n$ die Größe eines Vektors in Bytes ist.

Auch wenn $m$ ein fester Wert ist, so ist es möglich, Elemente von Vektoren logisch zu gruppieren und dadurch $m$ 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. $m$ ist also halbiert, während die Größe in Bytes $n$ gleich bleibt. Die Laufzeit $T(p)$ für diesen Ansatz hängt also von $m$ ab, was optimiert werden kann, wenn $T_{\text{start}}$ und $T_{\text{byte}}$ bekannt sind. Es ist optimal für

$m={\sqrt {\frac {n\cdot (p-2)T_{\text{byte}}}{T_{\text{start}}}}}$,

wobei angenommen wird, dass dies in einem kleineren $m$ resultiert, welches das ursprüngliche teilt.

Anwendungen

Reduktion ist eine der wichtigsten kollektiven Operationen im Message Passing Interface, wo die Leistung des genutzten Algorithmus wichtig ist und ständig für verschiedene Anwendungsfälle ausgewertet wird. 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.

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

Literatur

• Rohit Chandra: Parallel Programming in OpenMP. Morgan Kaufmann, 2001, ISBN 1-55860-671-8, S. 59–77. 
• Yan Solihin: Fundamentals of Parallel Multicore Architecture. CRC Press, 2016, ISBN 978-1-4822-1118-4, S. 75. 

Weblinks

• Reduction Clause, Reference to reduction clause