Derivation of Efficient Data Parallel Programs

This paper considers the expression and derivation of efficient data parallel programs for SIMD and MIMD machines. It is shown that efficient parallel programs must utilise both sequential and parallel computation; these are termed hybrid programs. The Bird--Meertens formalism, a calculus of higher order functions, is used to derive and express programs. Our goal is to derive efficient parallel programs for a variety of machines by: starting with an abstract specification, deriving an abstract algorithm and successively refining this to more efficient and machine dependent algorithms incorporating greater implementation detail. Nested data structures are used to express hybrid algorithms. Using this technique efficient accumulate (scan/parallel prefix) algorithms are derived for SIMD and MIMD machines. 1 Introduction The main reason for parallel programming is to achieve high performance. Unfortunately designing and writing efficient parallel programs, especially for MIMD machines, i..