Benutzer:Manuel Karl/Fox-Algorithmus
Der Fox-Algorithmus (nach seinem Erfinder Geoffrey C. Fox) ist ein Algorithmus zur parallel, auf p Prozessoren, ausgeführten Matrizenmultiplikation. Der Algorithmus richtet sich an Maschinen mit MIMD Architektur, verteiltem Speicher und mindestens einer zweidimensionale Topologie der Prozessoren.
Der Algorithmus wurde 1985 von Geoffrey C. Fox, Steve W. Otto und Tony Hey veröffentlicht.
Algorithmus
Bei diesem Algorithmus werden zwei n x n Matrizen A und B auf p Prozessoren verteilt, sodass jeder Prozessor initial (n / √p) x (n / √p) Blöcke der Matrizen A und B erhält. Während des Algorithmus werden die Elemente von A mittels Broadcast in den Prozessorreihen verteilt und die Elemente von B spaltenweise nach oben weitergereicht. Initial werden die Diagonalblöcke Ai,i ausgewählt und B ist normal auf die Prozessoren verteilt (siehe Grafik 1).
Der Algorithmus besteht aus folgenden Schritten:
1 Pipelineartiger Broadcast der Diagonalblöcke von A in horizontaler Richtung, sodass alle Prozessoren der ersten Reihe eine Kopie von A00 habe, die zweite Reihe eine Kopie von A11 und so weiter. 2 Multiplikation des kopierten Blocks von A mit dem derzeit im Prozessor vorhandenen Block von B 3 Alle Blöcke von B vertikal um eine Stelle rotieren 4 Horizontaler Broadcast der Blöcke auf der Diagonalen + 1 5 Multiplikation der kopierten Blöcke von A mit den derzeit in den Prozessoren vorhandenen Blöcken von B
Dieses Muster setztz sich fort bis die Blöcke von B wieder in der Ausgangsstellung sind und alle Nebendiagonalen von A verwendet wurden.
Das Muster Broadcast-Multiplikation-Rotation wird √p-mal wiederholt. Insgesamt hat der Algorithmus eine Berechnungszeit von
T = √p(2m3tflop + 2m2tcomm + (√p - 1)tstart)
Diese setzt sich zusammen aus:
1 Der Zeit für den Broadcast von A: m2tcomm 2 Der Zeit für die Rotation von B: m2tcomm 3 Die Zeit für die Multiplikation der Submatrizen: 2m3tflop
Hierbei ist tcomm die Zeit, um eine Gleichkommazahl zwischen Prozessoren zu übergeben, tstart die Startzeit um die Pipeline zu befüllen und tflop die Zeit für eine Multiplikation oder Addition von Gleichkommazahlen.
Pseudocode
1 //PE(i,j)
2 a := aij;
3 b := bij;
4 cij := 0;
5
6 for (l := 0; l < √p; l++) {
7 PE(i, (i+l) mod √p) broadcasts a to PE(i,j) for j ∈ {0..√p} ∧ j ≠ (i+l) mod √p;
8 cij := cij + a * b;
9 concurrently {
10 send b to PE((i+1) mod √p, j);
11 } with {
12 receive b' from PE((i-1) mod √p, j);
13 }
14 b := b';
15 }
Beispiel
Literatur
Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., 1994, ISBN 0805331700, 9780805331707(?!).
- Vipin Kumar: Introduction to parallel computing: design and analysis of algorithms. Benjamin/Cummings Pub. Co., 1994, Vorlage:ISBN.
- G.C Fox, S.W Otto, A.J.G Hey: Matrix algorithms on a hypercube I. Matrix multiplication. In: Parallel Computing. 4/1987, Nr. 1, 1987, ISSN 0167-8191, S. 17-31 ([1]).
