Programming with Divide-and-Conquer Skeletons: A Case Study of FFT

摘要

We demonstrate an approach to parallel programming, based on skeletons-parameterized program schemas with efficient implementations over diverse architectures. The contribution of the paper is tow-fold: (1)we classify divide-and-conquer (DC) algorithms and provide a family of provably correct parallel implemen- tations for a particular DC skeleton, called DH (distiributable homommorphism); (2) we adjust the mathematical specification of he Fast Fourier Transform (FFT) to the DH skeleton and, thereby, obtain a generic SPMD pro- gram, well suited for implementation under MPI. The generic program includes the efficient FFT solutions used in practice-the binary-exchange and the 2D- and 3D-transpose implementations-as special cases.