Practical Structured Parallelism Using BMF
David Crooke
Graduated Ph.D. July 1999
Abstract
This thesis concerns the use of the Bird-Meertens Formalism as a mechanism to control parallelism in an imperative programming language.
One of the main reasons for the failure of parallelism to enter mainstream computing is the difficulty of developing software and the lack of the portability and
performance predictability enjoyed by sequential systems. A key objective should be to minimize costs by abstracting much of the complexity away from the
programmer.
Criteria for a suitable parallel programming paradigm to meet this goal are defined. The Bird-Meertens Formalism, which has in the past been shown to be a suitable
vehicle for expressing parallel algorithms, is used as the basis for a proposed imperative parallel programming paradigm which meets these criteria.
A programming language is proposed which is an example of this paradigm, based on the BMF Theory of Lists and the sequential language C. A concurrent operational
semantics is outlined, with the emphasis on its use as a practical tool for increasing confidence in program correctness, rather than on full and rigorous formality.
A prototype implementation of a subset of this language for a distributed memory, massively parallel computer is produced in the form of a C subroutine library.
Although not offering realistic absolute performance, it permits measurements of scalability and relative performance to be undertaken.
A case study is undertaken which implements a simple but realistic algorithm in the language, and considers how well the criteria outlined at the start of the project are
met. The prototype library implementation is used for performance measurements.
A range of further possibilities is examined, in particular ways in which the paradigm language might be extended, and the possibility of using alternative BMF-like
type theories. Pragmatic considerations for achieving performance in a production implementation are discussed.
Last modified: Wed Oct 6 17:10:18 BST 1999
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.
