Deadlock free algorithmic parallelism : analysis, implementation and performance

It is proven in the first section of this thesis that a simplified communication scheme, denned as the MP parallel programming language[30], is deadlock free. This key result is established using the process calculus CSP[15], providing a precise description of the components which would otherwise be liable to subtle ambiguities of interpretation if presented in seemingly 'plain English'. In particular, it is shown that the CSP design adopted here guarantees freedom from deadlock, provided that all input and output operations are performed simultaneously and an infinitely readable 'external input' is provided. A library which closely follows the CSP design has been implemented and is presented in detail. This presentation describes both the construction of the library and the syntax required for its use. The correctness of the implementation is then demonstrated using illustrative ex­amples. An exhaustive analysis of a common sorting algorithm is presented which is sufficiently simple that the flow of data in the program may be traced in detail. The second, more complic­ated example is drawn from an important problem commonly occuring in atomic, molecular and nuclear physics, and which is a significant consumer of computational resources worldwide; the Hartree-Fock approximation. The atomic Hartree-Fock method is investigated using the mpkern parallel programming library in both task parallel and data parallel forms. An analysis is also performed which examines the efficient distribution of the most computationally intensive tasks in the Hartree-Fock method across a heterogeneous network of nodes.