Incremental Program Transformation Using Abstract Parallel Machines

Parallel processing is a key area of high-performance computing, providing the processing power to meet the needs of computation-intensive problems. Much research effort has therefore been invested in this area and it is growing. However, there are still several challenges that hinder its widespread use. In particular, parallel programs can be difficult to write because of the increase in the number of details to keep track of and design decisions to be made. Portability is also an important issue because the efficiency of a program depends heavily on the target machine. Another challenge arises when the issue of correctness is considered as the increased complexity and nondeterminism of parallel systems makes reasoning about them hard and renders traditional methods of testing unreliable. This thesis presents a methodology for developing parallel programs that addresses these issues. In it, executable parallel programs are derived incrementally from high-level specifications. A specification is given initially in mathematical notation and changed into an abstract functional specification. This is then transformed through a series of stages, during which additional information is given about the program, the target architecture and the parallelism. Finally it is transformed into the target language to produce an executable parallel program. This thesis uses C-f-MPI as an example target language, but many languages are possible. This methodology addresses several of the challenges of parallel programming. In particular, its incremental framework allows decisions about the program and its parallelism to be made one at a time, instead of all at once, easing the burden on the programmer and simplifying the decisions. Reasoning about the program is also made possible through the use of a pure functional language, such as Haskell, for intermediate versions of the program, as the program can then be transformed using equational reasoning, a correctness-preserving technique. The methodology is based on previous work on Abstract Parallel Machines and program derivation, which this thesis develops. It presents the basic infrastructure needed in the methodology, and therefore investigates how parallel systems can be modelled and manipulated in Haskell, and how the resultant programs can be transformed. It augments the basic methodology with the ability to introduce and reason about some key parallel programming features, including data distributions and program optimisations. The work is supported and demonstrated through two case studies