Parallel implementation and benchmarking in cluster architectures of one-dimensional discrete fourier transforms: A comparison using the row-column algorithm versus a novel formulation based on the bluestein/pseudocirculant algorithm

This Thesis presents the formulation and benchmarking of a novel parallel one-dimensional DFT (Discrete Fourier Transform) algorithm suitable for implementation in distributed memory environments and/or "multicore" architectures. The focus will be on the comparison of this novel formulation, based on the Bluestein/Pseudocirculant algorithm, versus the well known implementation of a one-dimensional DFT through the Row-Column algorithm. The Bluestein/Pseudocirculant algorithm maps a 1D DFT to a 1D Cyclic Convolution using the Bluestein Algorithm, then uses the Block Pseudocirculant Matrix Algorithm for a parallel implementation of the cyclic Convolution. The sequence length required by the new algorithm has to be even and it should be divisible by the square root of the number of processors available, or to be used, in the computing platform. This algorithm requires initial and final all-to-all communication stages among r-cores and two partial communication stages. The Row-Column algorithm computes a one dimensional DFT through a two dimensional DFT, this algorithm requires three all-to-all communication and the sequence length should be divisible by the square of the number of parallel cores available, or to be used, in the computing platform. In both implementations the last all-to-all communication stage can be omitted if a final ordered result is not required. Scalability studies and benchmarks were made for both implementations using up to 64 cores. The proposed formulation appears to have less performance, less accuracy and to use more computing cores than the former (or alternatively needs to have cores with comparatively larger memory), but it can tackle in parallel signal lengths that cannot be tackled by the Row-Column approach.