Pipeline optimizations of the prime factor algorithm
R. Albrizio, A. Mazzone, Nicola Veneziani, Paul C. Messina, Giovanni Aloisio, Mario A. Bochicchio · Concurrency Practice and Experience · 1995
Abstract The prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm used when the sequence length can be decomposed into mutually prime factors. Following our previous results on PFA decomposition carried out at Caltech on hypercube machines, we present in the paper a pipeline PFA implementation suitable for multiprocessor systems with distributed memory. This implementation achieves high values of efficiency and speed‐up when processing multiple sequences of data. The paper shows how an optimized structure can be obtained when the concurrency among computation and communications is exploited at each node of the pipe. Experimental results obtained on transputer‐based structures and on the IntelTouchstoneDelta system are also reported.