A rigorous examination of sequentially expressed algorithms to reveal their concurrency hierarchies

Thesis



The methods of Scott-Strachey semantics are applied to the problem of writing programs for parallel computers, using serial languages such as are in common use, with compilers which attempt to discover and exploit potential parallelism in independent sections of program.

A mathematical model of a parallel computer is first developed in detail, and in chapters 1 and 2 three basic conditions are derived which together ensure determinacy of operation in a parallel machine, first in purely semantic terms, then in a form more related to the syntactic structure of a language.

The remaining chapters apply these basic conditions to three actual languages, showing how the conditions can be reduced to purely syntactic (hence compiler evaluable) tests. Chapter 3 uses a very simple language to introduce the techniques required. Chapter 4 adds procedures, with all the complexity they involve. Chapter 5 considers the rather more fruitful area of arrays and loops.

The result, in all but the most trivial cases, is a rather complicated set of conditions which, while they produce the desired effect, suggest that today's commonly used languages are not the most suitable method of exploiting parallel computers.

Authors: Jones, C; Jones, C. M.

• Publication date: 1977
• DOI: 10.5287/ora-bmqgpmj4x
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Algorithms; Parallel processing (Electronic computers)