ABSTRACT PARALLEL MACHINES

Abstract

Any parallel programming language provides a model of parallelism, which is accepted implicitly when programming directly in the language.  We propose a more flexible approach to models of parallelism: in our methodology, the program is derived in a sequence of steps, where the algorithm version in each step incorporates just one decision and is based on a specific model of parallelism called an abstract parallel machine chosen to be suitable for that step. Each version of the algorithm is proved equivalent to the previous one.  An abstract parallel machine is described by a set of parallel operations describing its behavior, and is related to similar abstract parallel machines by transformation theorems.  In this paper we present the formalism for abstract parallel machines and illustrate the derivation process with two case studies.