Date of Award


Document Type


Degree Name

Master of Science


Department of Electrical and Computer Engineering

First Advisor

David M. Gallagher, PhD


The traditional approach to parallel processing has been to use Massively Parallel Processors (MPPs). An alternative design is commercial-off-the-shelf (COTS) workstations connected to high-speed networks. These networks of workstations (NOWs) typically have faster processors, heterogeneous environments, and most importantly, offer a lower per node cost. This thesis compares the performance of MPPs and NOWs for the two-dimensional fast Fourier transform (2-D FFT). Three original, high-performance, portable 2-D FFTs have been implemented: the vector-radix, row-column and pipeline. The performance of these algorithms was measured on the Intel Paragon, IBM SP2 and the AFIT NOW, which consists of 6 Sun Ultra workstations connected via the Myrinet switch. Three important conclusions have been made. First, the pipeline was the best algorithm on all platforms by approximately 30%. Second, the NOW was nearly equal to the SP2 in runtime, while the Paragon did not outperform a single Ultra workstation. As a result, NOWs are a competitive platform for this application. Finally, only limited speedup was achieved on the SP2 (2.9) with 32 processors, and AFIT NOW (1.9) with 5 processors. It appears that the changing communication-to-computation ratio has made the 2-D FFT a less viable candidate for parallelization, given its high communication overhead.

AFIT Designator


DTIC Accession Number