Algorithmus 1: Realisierung durch 1D-FFTs

Abbildung: Algorithmus 1, Ansatz: 2-stufiger Butterfly-Graph zur Basis 2 ($N^2 = 16$).
Abbildung: Algorithmus 1, 1. Schritt: Übergang zu einem homogenen Datenflußgraph ($N^2 = 16$).

Abbildung: Algorithmus 1, 2. Schritt: Skalierung auf $P$ Prozessoren ($N^2 = 16$, $P = 4$).
Abbildung: Algorithmus 1, Ergebnis: Einbettung in den Kommunikationsgraph des Zielsystems ($N^2 = 16$ und $P = 4$).

Ein 2D-FFT Algorithmus läßt sich gemäß der Gleichung

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

unter Verwendung des 1D-FFT Algorithmus konstruieren. Zunächst werden die Spalten der Eingabematrix durch die 1D-FFT transformiert. Anschließend werden dann auf gleiche Weise die Zeilen transformiert. Die Datenflußstruktur läßt sich wie bei der 1D-FFT durch einen Butterfly-Graph beschreiben, in dem jedoch jetzt in der ersten Hälfte die Spalten- und in der zweiten die Zeilentransformationen stattfinden. Hieraus ergeben sich andere Gewichte der Knotenfunktionen. Aus der Reihenfolge der Transformationen ergibt folgende Datenverteilung auf die Knoten des Butterfly-Graphen (Abbildung )

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

Ein paralleler 2D-FFT Algorithmus für $P$ Prozessoren auf Basis dieses Butterfly-Graphen läßt sich wie folgt konstruieren

• die Knoten im Butterfly-Graph werden mit jedem Schritt Shuffle-permutiert ( $\sigma_{{\mbox{ld}\,}N^2,0}$), um einen bzgl. der Verbindungen homogenen de Bruijn-Graph zu erhalten (Abbildung )

• der de Bruijn-Graph der Dimension ${\mbox{ld}\,}N^2$ wird in einen de Bruijn-Graph der Dimension ${\mbox{ld}\,}P$ eingebettet, der dem Kommunikationsnetzwerk des Zielsystems entspricht (Abbildungen und )