FROM TRANSFORMATIONS TO METHODOLOGY IN PARALLEL PROGRAM-DEVELOPMENT -A CASE-STUDY

The Bird-Meertens formalism (BMF) of higher-order functions over lists is a mathematical framework supporting formal derivation of algorithm s from functional 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 multiplicat ion, starting with a straight-forward mathematical specification and a rriving at the target processor topology together with a program for e ach processor of it. The development process is based on formal transf ormations; design decisions concerning data partitioning, processor in terconnections, etc. are governed by formal type analysis and performa nce estimation rather than made ad hoc. The parallel target implementa tion is parameterized for an arbitrary number of processors; for the p articular number, the target program is both time and cost-optimal. We compare our results with systolic solutions to polynomial multiplicat ion.