3.3.4 Reduce- und All-Reduce Operationen

Bildung von Ergebnissen über Daten aller Prozesse (z.B. $s = \sum\limits_{i=0}^{p-1} a_i$). Das Ergebnis steht am Ende einem Root-Prozeß (bei Reduce) bzw. allen Prozessen (bei All-Reduce) zur Verfügung.

$\bullet$ Reduce : Es wird die Tree-Topologie mit Root $=\,000$ verwendet.

 

Abbildung 3.14: Reduce-Operation im binären Baum

Abfolge a), b), c): a) = Link 3, b) = Link 2, c) = Link 1
$s_4 := a_4$, $s_6 := a_6$, $s_5 := a_5$, $s_7 := a_7$
$s_2 := (a_2+a_6)$, $s_3 := (a_3+a_7)$
$s_1 := [(a_1+a_5)+(a_3+a_7)]$
$s_0 := [(a_0+a_4)+(a_2+a_6)]\,+\,[(a_1+a_5)\,+\,(a_3+a_7)] \,=\, \sum\limits_{i=0}^{p-1} a_i$

Somit besitzt am Ende nur Prozeß $000$ das richtige Ergebnis, alle anderen Prozesse verfügen nur über Teilergebnisse.

Programmrealisierung über die Function TREE/SMALL>_UPDO($n$,$X$,$Y$,$H$,$VtOp$), welche auch mit Vektoren arbeitet und Operation auf diesen in $VtOp$ spezifiziert (Hier mittels CALL Tree_UpDo(1,S,A,AuxArray,VdPlus)).


$\bullet$ All-Reduce

Variante a): Kombination von Reduce- mit einer Scatter-Operation.
$\left.{\begin{array}{l} \mbox{{\sc Tree\_UpDo}} \\ \mbox{{\sc Tree\_Down}}\;\;... ...ree\_Do}}\begin{smallmatrix}I \\ D \\ ensuremath{\mathbb{R} }\end{smallmatrix}$


Variante b): Akkumulation im Hypercube (Cubeakkumulation)
Bei der Cubeakkumulation tauscht nCube-mal die eine Hälfte der Prozesse (nCube-1 Cube) Daten mit der anderen Hälfte aus.

 

Abbildung 3.15: All-Reduce im Hypercube

Zeitliche Abfolge: a) b) c), jeweils den Links 3, 2 und 1 zugeordnet.

Ergebnis:

$s_0 = [(a_0+a_4)+(a_2+a_6)]\,+\,[(a_1+a_5)+(a_3+a_7)]$
$\;\;\; \vdots$
$s_7 = [(a_0+a_4)+(a_2+a_6)]\,+\,[(a_1+a_5)+(a_3+a_7)]$
$\;\;\; \Downarrow$
$s_i = \sum\limits_{i=0}^{p-1} a_i \;\;\; \forall i=0,p-1$



Programmrealisierung über die Function

Vergleich der Varianten a) und b)

	CUBE/SMALL>_DO	TREE/SMALL>_DO
$\bullet$	Gleicher arithmetischer Aufwand
$\bullet$	nCube bidirektionale Kommunikationen oder 2$\ast$ nCube unidirektionale Kommunikationen	2$\ast$ nCube unidirektionale Kommunikationen
$\bullet$	Gleiche Linkbelastung	Sinkende Linkbelastung mit wachsender/fallender Linknummer
$\bullet$	Ideal bei gleicher Bandbreite aller Links	Auswahl des im Hypercube eingebetteten Baumes nach der Bandbreite der Links
$\bullet$	Ideal im physischen Hypercube, z.B. NCUBE2	Bei größeren Systemen können technologisch bedingte geringere Bandbreiten bei einigen Links auftreten, siehe Bsp. POWER-GC

Bsp.: Links im POWER-GC 

Im POWER-GC der Firma PARSYTEC (ab 64 Prozessoren lieferbar) sind folgende Relationen bzgl. der Bandbreite gegeben :

Links 1-4	:	Bandbreite $a$
Links 5-6	:	Bandbreite $b$
Links 7-8	:	Bandbreite $c$

mit $a > b > c$. Da die höheren Links eine geringere Bandbreite aufweisen, sollten sie bei den TREE/SMALL>_..-Operation im optimalen Baum nahe am Root-Prozeß benutzt werden. Dort kommunizieren nur wenige Prozesse miteinander.
Entsprechende Tests auf dem POWER-GC mit 128 Prozessoren an der TU Chemnitz (Dr.M.Pester) erbrachten ein signifikant besseres Laufzeitverhalten ( $\Leftarrow$ Kommunikationszeit) der entsprechend gewählten TREE/SMALL>_DO-Routinen gegenüber den äquivalenten CUBE/SMALL>_DO-Routinen.

Das hinderliche Problem der unterschiedlichen Bandbreiten in der CUBE/SMALL>_DO-Routine hängt zusammen mit der Bisektionsbandweite :  
Bandweite, wenn die eine Hälfte der Prozessoren mit der anderen Hälfte kommuniziert.

In obigem Beispiel ist diese Bisektionsbandweite anisotrop, d.h. sie hängt davon ab welche Teile der Maschine miteinander kommunizieren. In der Origin2000 tritt dieses Problem ab 128 Prozessoren auf ([SGI97], Seite 34ff).
Bei einem idealen System wächst die Bisektionsbandweite mit der Anzahl der Prozessoren.


Aufgabe :

  Ändern Sie den Algorithmus für TREE/SMALL>_DOWN auf Seite  so um, daß die Links mit höheren Nummern möglichst wenige Daten transportieren müssen.