Fine Grain Concurrent Computations

Citation

Athas, William C., Jr. (1987) Fine Grain Concurrent Computations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/63xc-r308. https://resolver.caltech.edu/CaltechETD:etd-02282008-091326

Abstract

This thesis develops a computational model, a programming notation, and a set of programming principles to further and to demonstrate the practicality of programming fine grain concurrent computers.

Programs are expressed in the computational model as a collection of definitions of autonomous computing agents called objects. In the execution of a program, the objects communicate data and synchronize their actions exclusively by message-passing. An object executes its definition only in response to receiving a message, and its actions may include sending messages, creating new objects, and modifying its own internal state. The number of actions that occur in response to a message is finite; Turing computability is achieved not within a single object, but through the interaction of objects.

A new concurrent programming notation Cantor is used to demonstrate the cognitive process of writing programs using the object model. Programs for numerical sieves, sorting, the eight queens problem, and Gaussian elimination are fully described. Each of these programs involve up to thousands of objects in their exectuion. The general programming strategy is to first partition objects by their overall behavior and then to program the behaviors to be self-organizing.

The semantics of Cantor are made precise through the definition of a formal semantics for Cantor and the object model. Objects are modelled as finite automata. The formal semantics is useful for proving program properties and for building frameworks to capture specific properties of object programs. The mathematical frameworks are constructed for building object graphs independently of program execution and for systematically removing objects that are irrelevant to program execution (garbage collection).

The formal semantics are complemented by experiments that allow one to study the dynamics of the execution of Cantor programs on fine grain concurrent computers. The clean semantics of Cantor suggests simple metrics for evaluating the execution of concurrent programs for an ideal, abstract implementation. Program performance is also evaluated for environments where computing resources are limited. From the results of these experiments, hardware and software architectures for organizing fine grain message- passing computations is proposed, including support for fault tolerance and for garbage collection.

Thesis Files