A CONCURRENT IMPLEMENTATION OF THE PRIME FACTOR ALGORITHM ON HYPERCUBE

Abstract

The prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm, where a one-dimensional DFT is turned into a multidimensional DFT, consisting of a few short DFT's whose lengths are mutually prime and then an efficient algorithm is exploited for the short DFT's. The data sequences in the Cooley-Tukey algorithm are in order, easily manageable, and well suited for vector processors and any parallel machine. On the contrary, the PFA works on DFT's of different lengths and heavily shuffles the updated data for computing of subsequent order DFT's. That poses a challenging problem for a distributed memory machine. We have implemented the PFA on hypercube using CrOS III communication routines, taking 120 ms to compute the DFT of 5040 complex points using 32 nodes of Caltech-JPL MARKIII Hypercube. It took 105 ms to do a DFT of 4096 complex points using the Cooley-Tukey algorithm with the same hardware configuration. We analyze the performance of hypercubes MARK III, NCUBE, and iPSC and the relative importance of communication and calculation. With the current communication speed the Cooley-Tukey algorithm performs fast on a massively concurrent processor and the PFA is advantageous when the number of processors is less than 64 or so. Our experience in PFA also serves as a useful guide to a multidimensional FFT implementation using any algorithm.