next up previous contents
Nächste Seite: Laufzeitergebnisse Aufwärts: Parallele 2D-FFT Algorithmen Vorherige Seite: Algorithmus 1: Realisierung durch   Inhalt

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


\begin{displaymath}
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}
\end{displaymath} (17)


\begin{displaymath}
= \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
\end{displaymath}


\begin{displaymath}
= \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}
\end{displaymath}


\begin{displaymath}
= \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}
\end{displaymath}


\begin{displaymath}
= \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}
\end{displaymath}


\begin{displaymath}
= \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}
\end{displaymath}


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{displaymath}
\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}\end{displaymath} (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$).
\begin{figure}\vbox{
\centerline{\psfig{figure=graph9.70b.ps}}\vspace{1cm}
\centerline{\psfig{figure=graph10.70b.ps}}}
\end{figure}

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$).
\begin{figure}\vbox{
\centerline{\psfig{figure=graph11.70b.ps}}\vspace{1cm}
\centerline{\psfig{figure=graph12.70b.ps}}}
\end{figure}

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$).
\begin{figure}\vbox{
\centerline{\psfig{figure=graph13.70b.ps}}\vspace{1cm}
\centerline{\psfig{figure=graph14.70b.ps}}}
\end{figure}

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


next up previous contents
Nächste Seite: Laufzeitergebnisse Aufwärts: Parallele 2D-FFT Algorithmen Vorherige Seite: Algorithmus 1: Realisierung durch   Inhalt
Jörg Haeger 2001-05-07