| Computing one-dimensional (1-D) Fast Fourier Transform (FFT) using the classical four-step FFT algorithm on parallel computers requires intensive all-to-all communication. This all-to-all communication significantly reduces the performance of the FFT. In this dissertation, new methods are proposed that allow for more efficient implementations of the 1D FFT on parallel computers. The proposed methods not only reduce the computational time of the four-step FFT algorithm by reducing the number of arithmetic operations, but they also reduce the overhead associated with the communication between processors. The dissertation conducts performance analysis of the proposed methods and provides simulation results based mainly on two parallel systems: a symmetric multiprocessor (SMP) system and a cluster of workstations. The following is a summary of the proposed methods.; First, two parallel algorithms are presented based on the tree and the three-step FFT algorithms. Then three implementations of the three-step FFT algorithm are presented. These implementations are based on the transpose, the butterfly, and the hybrid MPI/Pthread structures, respectively.; Second, the 2-step-no-communication and 3-step-no-communication algorithms are presented that are parallel algorithms for four-step FFT without inter-processor communication. If the cost of extra computation required by these no-communication algorithms is outweighed by that of the all-to-all communication required by the four-step FFT algorithm, then they will outperform the four-step FFT algorithm.; Finally, two parallel algorithms are presented for implementing the six-step 1-D FFT without inter-processor communication, at the expense of extra computation as opposed to the conventional six-step FFT. This dissertation demonstrates the advantages of these two algorithms where the cost of computation tends to be lower than that of the inter-processor communication found with the six-step FFT algorithm in parallel systems. |
