Algorithmus 2: Basis 4 2D-FFT

Ein anderer Ansatz überträgt das Vorgehen bei der Entwicklung des 1D-FFT Algorithmus. Für $j = 0, \dots, n-1$ ergibt sich

$$y_{2j_1, 2j_2} = \sum_{k_1=0}^{N-1} \sum_{k_2=0}^{N-1} x_{k_1, k_2} \omega_{N}^{2j_2 k_2 + 2j_1 k_1}$$ (17)

$$= \sum_{k_1=0}^{N-1} ( \sum_{k_2=0}^{N-1} x_{k_1, k_2} \omega_{N}^{2j_2 k_2} ) \omega_{N}^{2j_1 k_1} \nonumber$$

$$= \sum_{k_1=0}^{N-1} ( \sum_{k_2=0}^{n-1} (x_{k_1, k_2} + x_{k_1, n+k_2}) \omega_{n}^{j_2 k_2} ) \omega_{N}^{2j_1 k_1}$$

$$= \sum_{k_1=0}^{n-1} ( \sum_{k_2=0}^{n-1} (x_{k_1, k_2} + x_... ... x_{n+k_1, n+k_2}) \omega_{n}^{j_2 k_2} ) \omega_{n}^{j_1 k_1}$$

$$= \sum_{k_1=0}^{n-1} ( \sum_{k_2=0}^{n-1} (x_{k_1, k_2} + x_... ... x_{n+k_1, n+k_2}) \omega_{n}^{j_2 k_2} ) \omega_{n}^{j_1 k_1}$$

$$= \sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-1} (x_{k_1, k_2} + x_{k... ...n+k_1, k_2} + x_{n+k_1, n+k_2}) \omega_{n}^{j_2 k_2 + j_1 k_1}$$

Die Berechnung der Matrix $(y_{2j_1,2j_2})_{0 \leq j_1,j_2 < n-1}$ wird also auf die Berechnung der DFT der $n \times n$-Matrix $(x_{j_1,j_2} + x_{n+j_1,n+j_2})_{0 \leq j_1,j_2 < n-1}$ zurückgeführt. Die Werte $y_{2j_1, 2j_2+1}$, $y_{2j_1+1, 2j_2}$ und $y_{2j_1+1, 2j_2+1}$ ergeben sich analog unter Berücksichtigung der auftretenden Gewichte.

Die Datenflußstruktur dieses 2D-FFT Algorithmus läßt sich durch einen $\log_4 N^2$-dimensionalen Butterfly-Graph zur Basis 4 (Abbildung ) beschreiben, wenn die Eingangsmatrix wie folgt auf die Knoten verteilt wird

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

und in den Knoten folgende Funktionen

$$\begin{array}{c} g_1(a, b, c, d) = f_1( f_1(a, c), f_1(b, d)... ... )\\ g_4(a, b, c, d) = f_2( f_2(a, c), f_2(b, d) ) \end{array}$$ (18)

für folgende Bereiche

$g_1$	$g_2$
$g_3$	$g_4$

verwendet werden, wobei $f_1$ und $f_2$ durch Gleichung gegeben sind.

Abbildung: Algorithmus 2, Ansatz: $\log_4 N^2$-dimensionaler Butterfly-Graph zur Basis 4 (Kanten des 1. Schrittes nur exemplarisch, $N^2 = 16$).
Abbildung: Algorithmus 2, Schritt 1: ${\mbox{ld}\,}N^2$-dimensionaler Butterfly-Graph zur Basis 2 ($N^2 = 16$).

Abbildung: Algorithmus 2, Schritt 2: Skalierung auf $2P$ Prozessoren ($N^2 = 16$ und $P = 4$).
Abbildung: Algorithmus 2, Schritt 3: Butterfly-Graph mit ${\mbox{ld}\,}2P$ globalen Schritten ($P = 4$).

Abbildung: Algorithmus 2, Schritt 4: durch Permutation homogenisierter iterierter de Bruijn-Graph mit ${\mbox{ld}\,}2P$ Schritten ($P = 4$).
Abbildung: Algorithmus 2, Ergebnis: Einbettung in den Kommunikationsgraph des Zielsystems ($N^2 = 16$ und $P = 4$).

Die Entwicklung eines parallelen Algorithmus für $P$ Prozessoren, der der Struktur dieses Butterfly-Graphen entspricht, verläuft wie folgt

• jeder Schritt im Basis 4 Butterfly-Graph wird in 2 Schritte zerlegt, wobei im ersten ein Spalten- und im zweiten ein Zeilentransformationsschritt durchgeführt wird (Abbildung )

• der entstandene Basis 2 Butterfly-Graph mit ${\mbox{ld}\,}N^2$ Ebenen wird durch Einbetten in einen Butterfly-Graph der Dimension ${\mbox{ld}\,}2P$ auf $2P$ Prozessoren skaliert (Abbildung )

• die letzten ${\mbox{ld}\,}N^2 - {\mbox{ld}\,}2P$ Schritte lassen sich durch einen beliebigen iterativen 2D-FFT Algorithmus lokal auf den einzelnen Prozessoren berechnen (Abbildung )

• im Butterfly-Graph der Dimension ${\mbox{ld}\,}2P$ werden mit jedem der ${\mbox{ld}\,}2P$ Schritte die Knoten Shuffle-permutiert ( $\sigma_{{\mbox{ld}\,}2P,0}$), so daß ein homogener iterierter de Bruijn-Graph entsteht (Abbildung )

• der de Bruijn-Graph wird in einen de Bruijn-Graph der Dimension ${\mbox{ld}\,}P$ eingebettet, so daß Funktionen, die identische Daten benötigen, sich auf demselben Prozessor befinden (Abbildung )