The Bird-Meertens formalism (BMF) of higher order functions over lists has become popular for the calculational derivation of algorithms from specifications. This paper reports results of a case study on the systematic use of BMF in the process of parallel program development. We develop a parallel program for polynomial multiplication, starting with a straight-forward mathematical specification and arriving at an SPMD processor topology together with a program for each processor of it. The development process is based on formal transformations in BMF; design decisions concerning data partitioning, processor interconnections, etc. are governed by a type analysis and by performance considerations. The target implementation is parameterized for an arbitrary number of processors; the choice of number either makes the target program cost-optimal or enables logarithmic time complexity. We compare our results with systolic solutions to polynomial multiplication.
Ulrike Peiker, Martin Griebl