A new approach for computing multidimensional DFT's on parallel machines and its implementation on the iPSC/860 hypercube

摘要

Proposes a new approach for computing multidimensional DFTs that reduces interprocessor communications and is therefore suitable for efficient implementation on a variety of multiprocessor platforms including MIMD supercomputers and clusters of workstations. Group theoretic concepts are used to formulate a flexible computational strategy that hybrids the reduced transform algorithm (RTA) with the Good-Thomas factorization and can deal efficiently with non-power-of-two sizes without resorting to zero-padding. The RTA algorithm is employed not as a data processing but rather as a bookkeeping tool in order to decompose the problem into many smaller size subproblems (lines) that can be solved independently by the processors. Implementation issues on an Intel iPSC/i860 hypercube are discussed and timing results for large 2D and 3D DFTs with index sets in Z/MP/spl times/Z/KP and Z/N/spl times/Z/MP/spl times/Z/KP respectively are provided, where N, M, K are powers-of-two and P is a small prime number such as 3, 5, or 7. The nonoptimized realizations of the new hybrid RTA approach are shown to outperform by as much as 70% the optimized assembly coded realizations of the traditional row-column method on the iPSC/860.