The design of a prototyping programming language for parallel and sequential algorithms

by Nyland, Lars Siegfried, Ph.D., Duke University, 1991, 336 pages; AAT 9127499

Abstract (Summary)

Prototyping of computer programs is an exploration process. The specifications, whether written down or merely imagined, are often incomplete, and answers must be found to complete the specification. The prototyping process is used for the express purpose of gaining knowledge to complete the specifications.

This thesis is a presentation of a programming language for prototyping sequential and parallel algorithms. The language is called CPL, which stands for a Common Prototyping Language. The goals of a prototyping language are to allow a programmer to quickly explore an algorithm, be it sequential or parallel. Several programming styles are examined, the programming language is described in detail, and then an examination of how the language fits particular styles is made. Several examples of modern algorithms are described, showing the effectiveness of CPL and prototyping (two of the algorithms required repairs).

The distinguishing characteristics of the language are many. A strong data model is supported that includes set-theoretic constructs such as sets, sequences, and maps, as well as support for objects. All data are first-class objects, allowing freedom in handling. A unique characteristic of the language is its ability to describe many different models of parallel computing. These include the Parallel Random-Access Machine (PRAM), communicating sequential processes, data-level parallelism, and distributed computing. The language has a supportive variable typing system, variables need not be declared, and are freely typed, unless the programmer specifies otherwise. Much of the notation in the language does not distinguish between notation for statements or expressions, simplifying the language. The language allows statements to be treated as values and stored. This facilitates the automatic generation of multiple concurrent streams of execution. These characteristics of the language give it a unique ability to describe parallel algorithms at a very high level.

The programming styles examined include imperative, mathematical, object-oriented, functional, PRAM and other forms of parallel computing, search and translation. The model of parallelism chosen is shown to be effective through stylistic arguments as well as by diverse programming examples.

The programming examples show that the language described is applicable to many different styles of programming, that the language is consistent, and that it is usable. The examples include recent algorithms on tree-search problems in parallel, scan algorithms for data-parallel machines, sorting on distributed systems, and a theoretical, parallel graph-connectivity algorithm. Clarifications of the not-quite-correct algorithms have been made, showing that the algorithms are indeed effective and perform as expected.

Indexing (document details)