Stages and transformations in parallel programming
Sergei Petrovich Gorlatch · 1997
. An approach, called SAT (Stages And Transformations), is introduced to support the derivation of parallel distributed-memory programs. During the design, a program is viewed as a single thread of stages, with parallelism concentrated within stages; the target program is of the SPMD format. The design process is based on the transformation rules of the Bird-Meertens formalism of higher-order functions over lists. The approach is illustrated by three case studies which include: a systematic method of constructing list homomorphisms, a scalable, load-balanced implementation of divide-and-conquer based on a specialized topology and a formal derivation of a time and cost optimal parallel algorithm for straightforward polynomial multiplication. 1 Introduction The main problem with parallel and distributed systems today seems not to be how to build them, but how to make them work efficiently. The enormous diversity of architectures, together with the specific problems of parallelism, not e...