6.5 Matrizenmultiplikation im Hypercube

Sei n = 2^k. Zwei n × n -Matrizen A,B können in einem Hypercube mit n ³ = 2^3k Prozessoren multipliziert werden nach der Idee von Dekel, Nassimi und Sahni (DNS) in Anlehnung an den CREW PRAM-Algorithmus aus Kapitel 2.5:

FOR ALL 0 $\leq$ i, j, k $\leq$ n - 1 DO IN PARALLEL
     P_ijk : tmp [i,j,k] := a[i,k] * b[k,j]
END
FOR ALL 0 $\leq$ i, j $\leq$ n - 1 DO IN PARALLEL
     P_{ij *} : c[i,j] := $\sum_{k = 0}^{n - 1}$ tmp [i,j,k]
END

Die Bestimmung vom tmp [i,j,k] verursacht einen Schritt, das Aufaddieren des Vektors tmp [i,j,*] verursacht log n Schritte.
Zur Realisierung im Hypercube wird ein logisches 2^k × 2^k × 2^k-Prozessorgitter gemäß Einbettungsidee aus Kapitel 3.3.2 mit Kantenstreckung 1 in einen Hypercube der Dimension 3k eingebettet. Der Hypercube hat n Ebenen, zu Beginn befinden sich die Matrizen A,B in Ebene 0, d.h., P_ij0 speichert a[i,j] und b[i,j].
Ziel ist es, Zeile i der Matrix A und Spalte j der Matrix B in die Prozessorvertikale P_{ij *} zu bekommen, genauer P_ijk soll a[i,k] und b[k,j] erhalten.

Vertikale im Prozessorwürfel zur Aufnahme von a[i,*] bzw. b[*,j]

Hierzu wird zunächst jede Spalte k von A auf die Ebene k kopiert, d.h., a[i,k] wandert von P_ik0 nach P_ikk . Danach findet auf jeder Ebene k ein One-to-All Broadcast dieser Spalte statt, d.h., Prozessoren P_{i * k} erhalten Kopien von a[i,k] von P_ikk . Somit verfügt P_ijk über a[i,k]. Analog wird die Matrix B verteilt, indem jeweils die Zeilen nach oben wandern und dann ebenenweise durch Broadcast verteilt werden. Somit verfügt P_ijk über b[k,j].

Nach der Multiplikation tmp[i,j,k] := a[i,k] * a[k,j] muß jede Prozessorvertikale ihre Produkte tmp [i,j,*] aufaddieren und das Ergebnis nach P_ij0 bringen.
Alle Phasen (Lift der Matrizen A,B , Broadcast in einer Ebene, Aufsummieren) finden in n -elementigen Subwürfeln des Hypercubes statt und benötigen daher log n Schritte. Die Gesamtlaufzeit für n ³ Prozessoren beträgt daher O(log n) .