title: Parallel Graph Rewriting on Loosely Coupled Machine Architectures
authors: M.C.J.D. van Eekelen, M.J. Plasmeijer, J.E.W. Smetsers
Graph rewriting models are very suited to serve as the basic computational
model for functional languages and their implementation. Graphs are used to
share computations which is needed to make efficient implementations of
functional languages on sequential hardware possible. When graphs are
rewritten (reduced) on parallel loosely coupled machine architectures,
subgraphs have to be copied from one processor to another such that sharing
is lost. In this paper we introduce the notion of lazy copying. With lazy
copying it is possible to duplicate a graph without duplicating work. Lazy
copying can be combined with simple annotations which control the order of
reduction. In principle, only interleaved execution of the individual
reduction steps is possible. However, a condition is deduced under which
parallel execution is allowed. When only certain combinations of lazy
copying and annotations are used it is guarantied that this so-called
non-interference condition is fulfilled. Abbreviations for these
combinations are introduced. Now complex process behaviours, such as process
communication on a loosely coupled parallel machine architecture, can be
modelled. This also includes a special case: modelling multiprocessing on a
single processor. Arbitrary process topologies can be created. Synchronous
and asynchronous process communication can be modelled. The implementation
of the language Concurrent Clean, which is based on the proposed graph
rewriting model, has shown that complicated parallel algorithms which can go
far beyond divide-and-conquer like applications can be expressed.