Parallelism and the Bird-Meertens Formalism

One of the major reasons for the lack of practical use of parallel computers has been the absence of a suitable model of parallel computation. A useful general model must be architecture independent, must realistically reflect execution costs, and must reduce the cognitive overhead of managing massive parallelism. We discuss the merits and problems of proposed models of parallel computation with respect to these criteria and conclude that data parallel models hold the strongest promise. The best way known to construct such models is a categorical construction that not only builds types but much useful ancillary structure. This extra structure makes them extremely useful as parallel models, a claim we illustrate using the Bird-Meertens theory of lists. Keywords: data parallel computation, parallel programming languages, models of parallel computation, parallel program derivation, programming calculi, Bird-Meertens formalism. 1 Introduction There are many interesting problems in the de..