Performance prediction of fast Fourier transform algorithms on loosely coupled multiprocessors

[摘要] In this study we examine the effects of implementing the Radix 2, the Radix 4 and the Prime Factor Fast Fourier Transform algorithms on two instances of message-based multiprocessor architectures. The machines we use are a 16 node Intel iPSC Hypercube, running the Intel operating system version 3.1 and the Crystalline operating system version III, and the distributed V System implemented on a group of Sun 2/50 workstations. We find that although the radix 2 algorithm has the highest computational complexity of the three algorithms, it is the most amenable to efficient parallelization on message based architectures of the type we studied. Another part of the thesis deals with modeling the execution of the three algorithms on the two message-based architectures using the Rice Parallel Processing Testbed (RPPT). This was done to validate the working of the RPPT. The execution times predicted by the RPPT simulation models for the FFT algorithms are confirmed by comparing them against measured times obtained from the systems being modeled.

[发布机构] Rice University

[效力级别] Electrical engineering