cij : = aik · bkj .
Eine Partition von A und B in jeweils p Teilmatrizen der Größe n/ × n/ 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/ × n/ , 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 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 .
Die initiale Aufstellung erfordert
·
Kommunikationszeit.
In jeder der Iterationen wird an Rechenzeit
()3 Schritte verbraucht, an Kommunikationszeit
O() .
Daraus folgt als Gesamtzeit
Somit beträgt der Overhead
Zu gegebener Effizienz von 50 % ergibt sich die Isoeffizienzfunktion
als
n 3 = n 2 ·
n = , d.h., wächst p um den Faktor 4 ,
so muß n um den Faktor 2 wachsen.
Matrizenmultiplikation nach Cannon in einem 4 × 4 -wraparound-Gitter | |
(a) Initiale Verschiebungen für Matrix A | |
(b) Initiale Verschiebungen für Matrix B | |
(c) A und B in initialer Aufstellung. 1. Shift des Cannon-Algorithmus als Pfeile angedeutet. | |
(d) Teilmatrixpositionen nach dem 1. Shift | |
(e) Teilmatrixpositionen nach dem 2. Shift | |
(f) Teilmatrixpositionen nach dem 3. Shift |