Parallel power-of-two fast Fourier transforms on a hypercube
Mahn-Ling Woo · 1992
The popular applications of Fast Fourier Transforms (FFTs) and the invention of powerful parallel machines make the development of parallel Fast Fourier Transform (PFFT) algorithms very intriguing. This thesis explores how efficiency is affected by the distance and radix of an algorithm. First, 19 new power-of-two PFFT algorithms are presented. Algorithms, both ordered and unordered, with radices 2, 4, or mixed (4-2) over distances 1 or 2 are given. A theoretical estimate of the time complexity, both computational and communicational, is derived for each algorithm. These results suggest that higher radix PFFT algorithms are more efficient. Machine dependent criteria are derived which indicate whether the distance two algorithms are more efficient or not. These criteria have been evaluated on the Intel iPSC systems. Also the performance of communication commands and some suggestions for developing an efficient parallel algorithm on Intel iPSC/i860 are discussed. One of the above algorithms, an unordered distance-1 radix-2 PO2 PFFT algorithm, was implemented, and its results were compared with the results of an algorithm given by Swarztrauber as well as with one given by Chamberlain. In both theory and implementation on the Intel iPSC1 and iPSC/i860 (using up to 64 nodes and 1024 data points), this algorithm proved to be more efficient than those of Chamberlain and Swarztrauber. In addition, the computational complexity of the scalar radix-2$\sp{r}$ FFT is derived. The derivation indicates that a more efficient scalar radix-2$\sp{r}$ FFT algorithm can be obtained by applying the higher-radix FFT to implement the 2$\sp{r}$ Fourier Transform term of FFT. The derivation also gives a possible future direction in the derivation of parallel radix-2$\sp{r}$ FFT algorithms.