6.2 Matrix-Transposition in Gitter und Hypercube

Zur n × n -Matrix A sei A ^T zu bestimmen mit A ^T[i,j] : = A[j,i] für 0 $\leq$ i,j < n . Hierfür eignet sich ein Schachbrettmuster, realisiert durch $\sqrt{p}$ × $\sqrt{p}$ Prozessoren. Jeder Block der Größe n/$\sqrt{p}$ × n/$\sqrt{p}$ wandert zunächst abwärts bzw. aufwärts (siehe Bild 6.1), danach nach links bzw. nach rechts. An ihrem Zielprozessor wird die Teilmatrix lokal transponiert.

Verteilung der Teilmatrizen vor und nach der Transposition. Die Pfeile deuten die initiale Richtung an.

Die Laufzeit wird bestimmt von den beiden diagonal gegenüberliegenden Teilmatrizen, bei denen n ²/p Daten über eine Länge von 2$\sqrt{p}$ transportiert werden müssen. Die lokale Transposition dauert n ²/p Schritte. Daraus resultieren eine Laufzeit von O(n ²/p · $\sqrt{p}$) und Kosten von O(n ² · $\sqrt{p}$) .

Eine Beschleunigung wird durch die rekursive Struktur der Matrixtransposition möglich.

Rekursive Transposition einer 8 × 8 -Matrix in 3 Phasen

Eine Implementierung auf dem Hypercube nutzt die rekursive Struktur der Matrixtransposition aus: Eine n × n -Matrix A kann zunächst als eine 2 × 2 -Matrix, bestehend aus vier n/2 × n/2 Teilmatrizen B₀₀,B₀₁,B₁₀,B₁₁ aufgefaßt werden. Nach dem Tausch von B₀₁ mit B₁₀ werden alle 4 Teilmatrizen rekursiv weiter transponiert.

Sei $\sqrt{p}$ eine 2er-Potenz. Es sei jede der p Teilmatrizen gemäß ihrem laufenden Index einem Hypercubeprozessor zugeordnet. Aufgrund der Hypercubestruktur sind B₀₀,B₀₁,B₁₀,B₁₁ jeweils Subwürfel, deren Adressen folgende Gestalt haben:

0..0.., 0..1.., 1..0.. bzw. 1..1..

Dadurch sind die jeweils auszutauschenden Teilmatrizen nur 2 Kanten entfernt.

Partitionierung des Hypercubes in 4 Subcubes

          0,4  0,5  0,6  0,7    000100  000101  000110  000111
          1,4  1,5  1,6  1,7    001100  001101  001110  001111
          2,4  2,5  2,6  2,7    010100  010101  010110  010111
          3,4  3,5  3,6  3,7    011100  011101  011110  011111

Also entstehen (log $\sqrt{p}$) Phasen, in denen jeweils gleichzeitig Matrizen der Größe n ²/p über 2 Links ausgetauscht werden. Die lokale Transposition benötigt ${\frac{n^2}{p}}$ Schritte. Daraus resultiert eine Laufzeit T_p = O(n ²/p · log $\sqrt{p}$) . Der Overhead beträgt

T₀(W,p) = p · T_p - W = O(n ² · log $$\sqrt{p}$$ - n ²) = O(n ² · log $$\sqrt{p}$$) .