Back to search

University of Southampton

Deadlock free algorithmic parallelism : analysis, implementation and performance

Abstract

dc:description.abstract

<p>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.</p> <p>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.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2003

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Simpson, D.P

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Simpson, D.P. Deadlock free algorithmic parallelism : analysis, implementation and performance. doctoral thesis, University of Southampton, 2003.