A formal model for architecture-independent parallel software engineering
David C. DiNucci · 1990
In the absence of a unifying model to describe parallel algorithms, existing architectures have served as the models. The resulting algorithms, expressed as sets of sequential processes which communicate via shared memory or message passing, are non-portable, and the component processes cannot be implemented according to an input-output specification alone. Determining the set of computations represented by such an algorithm often requires no less than simulating their execution. This dissertation develops a model, F-Nets, for expressing parallel algorithms in a manner which avoids many of these difficulties. Both high- and low-latency communication are efficiently accomodated, and processes can be implemented in any deterministic language. The possible effects of each process is completely determined by the input-output mapping it implements. Computations are defined as partial orderings of these process executions, and algorithms are represented graphically as folded computations. A formal axiomatic semantics is provided for unfolding algorithms into computations, as is an operational semantics which is used to describe efficient implementations of the model on various architectures. Some final observations and predictions are made for future work based on the model.