Unordered parallel distance-1 and sitance-2 FFT algorithms of radix 2 and (4-2)
Mahn-Ling Woo, Rosemary Anne Renaut · 1994
Algorithms for unordered Parallel Fast Fourier transform (PFFT) pairs with radices 2 and mixed radix (4-2) for distributed memory machines are presented.Distributed memory versions using distance one and distance two communications are derived.Theoretical estimates of the computation costs in each case demonstrate that the higher-radix FFT is more efficient for parailel implementation.Furthermore, distance-two communication strategies can minimize communication cost when certain architecture dependent parameters are satisfied.Introduction.In this paper, power-of-two (PO2) Fast Fourier transforms are considered for implementation on the power-of-two topology hypercube.PO2 FFTs can be classified into two groups: unordered and ordered.The unordered P02 PFFT algorithms produce an output data sequence which is the bit-reverse of the input data sequence.The ordered PO2 PFFT algorithms generate identical input and output data sequences.In this paper we focus on PO2 unordered PFFT algorithms, and, in particular, unordered PFFT pairs consisting of a forward and inverse transform.It has already been demonstrated by Woo and Renaut [6] that the most efficient radix-2 PFFT algorithms minimize the number of communications, the communication distance, and the data packet size.It is known that, in scalar mode, radix-2 FFT algorithms require more computation than radix-4 and mixed-radix (4-2) FFT algorithms.Is this still the case in parallel mode?Furthermore, as commonly assumed, is distance two communication required?Here we show that indeed higher radix has the potential to be more efficient and further can be implemented in distance one.The definition of scalar FFT can be found in many text books and papers such as [1,3].Parallel implementations are designed with the aid of the sequence to processor map which is explained in the following section.Distance-1 algorithms and their time complexities are explained and compared in the later sect-ions.Conclusions follow at the e.nd.