Abstraction and performance in the design of parallel programs: an overview of the SAT approach

SAT stands for Stages And Transformations and is the name of an approach to the high-level, performance-directed design of parallel programs. The targ et programs obtained with this approach are sequences of internally paralle l stages, i.e., they fall within the SPMD model. Formal program transformat ions are used for deriving each parallel stage and optimizing the combinati on of several stages. The main advantage of the SAT approach is the comparatively high level of a bstraction at which performance-relevant design decisions can be made. One consequence is that choices become much clearer than at the code level, enh ancing comparability; another is that there is an increased potential for a utomation of the programming process. This paper summarizes the approach and assesses its usefulness, with emphas is on one basic parallel programming pattern, the list homomorphism, which captures the divide-and-conquer paradigm. We survey the transformational th eory, provide a range of practical examples, and discuss the potential for automation and also the demands made on application programmers and impleme nters.