Publication | Closed Access
A Generic MPI Implementation for a Data-Parallel Skeleton: Formal Derivation and Application to FFT
21
Citations
0
References
1998
Year
Generic Mpi ImplementationEngineeringComputer ArchitectureParallel ImplementationComputer-aided DesignFast Fourier TransformParallel SoftwareSystems EngineeringParallel ComputingCompilersComputational GeometryDh FormatMassively-parallel ComputingComputer EngineeringComputer ScienceSignal ProcessingParallel ProcessingData-parallel SkeletonParallel ProgrammingData-level ParallelismFormal DerivationGeneric Spmd Implementation
We derive a provably correct, architecture-independent family of parallel implementations for a class of data-parallel algorithms, called DH (distributable homomorphisms). The implementations are well-structured SPMD programs with group-wise personalized all-to-all exchange, directly realizable in MPI. As a case study, we systematically adjust the mathematical specification of the Fast Fourier Transform (FFT) to the DH format and, thereby, obtain a generic SPMD implementation for FFT. The target program includes FFT solutions used in practice – the binary-exchange and the 2D- and SD-transpose – as special cases.