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

    loading  Checking for direct PDF access through Ovid

Abstract

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 two-fold: (1) we classify divide-and-conquer (DC) algorithms and provide a family of provably correct parallel implementations for a particular DC skeleton, called DH (distributable homomorphism); (2) we adjust the mathematical specification of the Fast Fourier Transform (FFT) to the DH skeleton and, thereby, obtain a generic SPMD program, 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.

    loading  Loading Related Articles