6.4 Matrizenmultiplikation im Gitter

Gegeben zwei n × n -Matrizen A,B . Gesucht ist die Matrix C : = A * B mit

c_ij : = $$\sum_{k=0}^{n - 1}$$a_ik · b_kj .

Eine Partition von A und B in jeweils p Teilmatrizen der Größe n/$\sqrt{p}$ × n/$\sqrt{p}$ erlaubt die Produktberechnung durch Multiplizieren und Addieren der korrespondierenden Teilmatrizen. Die beiden Matrizen seien gespeichert in einem quadratischen wraparound-Gitter mit p Prozessoren, d.h., jeder Prozessor speichert 2 Blöcke der Größe n/$\sqrt{p}$ × n/$\sqrt{p}$ , genannt A' und B' . Zur initialen Aufstellung wird die i -te Zeile von A i -mal zyklisch nach links geshiftet, die j -te Spalte von B j -mal zyklisch nach oben geshiftet. In jeder Iteration werden dann die Teilmatrizen multipliziert, aufaddiert und zyklisch weitergeschoben, d.h., jeder Prozessor durchläuft folgendes Programm von Cannon:

S := 0;
FOR i := 1 TO $\sqrt{p}$ DO
     S := S + A'*B';
     sende altes A' nach links;
     empfange neues A' von rechts;
     sende altes B' nach oben;
     empfange neues B' von unten;
END

Anschließend verfügt jeder Prozessor über eine Teilmatrix der Ergebnismatrix C .

Initiale Aufstellung zweier 6 × 6 -Matrizen; gezeigt ist Zeile 1 von Matrix A und Spalte 3 von Matrix B .

Die initiale Aufstellung erfordert ${\frac{n^2}{p}}$ · $\sqrt{p}$ Kommunikationszeit. In jeder der $\sqrt{p}$ Iterationen wird an Rechenzeit (${\frac{n}{\sqrt{p}}}$)³ Schritte verbraucht, an Kommunikationszeit O(${\frac{n^2}{p}}$) . Daraus folgt als Gesamtzeit

Somit beträgt der Overhead

Zu gegebener Effizienz von 50 % ergibt sich die Isoeffizienzfunktion als n ³ = n ² · $\sqrt{p}$
$\Rightarrow$ n = $\sqrt{p}$ , d.h., wächst p um den Faktor 4 , so muß n um den Faktor 2 wachsen.