A Structured Approach to Parallel Programming

Abstract. Parallel programming continues to be difficult, despite substantial and ongoing research aimed at making it tractable. Especially dismaying is the gulf between theory and the practical programming. We propose a structured approach to developing parallel programs for problems whose specifications are like those of sequential programs, such that much of the work of development, reasoning, and testing and debugging can be done using familiar sequential techniques and tools. The approach takes the form of a simple model of parallel programming, a methodology for transforming programs in this model into programs for parallel machines based on the ideas of semantics-preserving transformations and programming archetypes (patterns), and an underlying operational model providing a unified framework for reasoning about those transformations that are difficult or impossible to reason about using sequential techniques. This combination of a relatively accessible programming methodology and a sound theoretical framework to some extent bridges the gulf between theory and practical programming. This paper sketches our methodology and presents our programming model and its supporting framework in some detail.