Practical PRAM Programming with Fork95

Christoph W. Kessler

With the existence of the SB-PRAM architecture, the PRAM model of parallel computation gains practical importance. We present the PRAM programming language Fork95. A superset of ANSI C, Fork95 offers language constructs to control different levels of relaxed exact synchronicity and shared address subspaces according to a hierarchical group concept.

Fork95 supports many important parallel algorithmic paradigms, including data parallelism, parallel divide-and-conquer, and pipelining. It turns out that explicit new language constructs (``skeletons'') are not required to implement these paradigms in Fork95.

A compiler for Fork95 is operational and available on the WWW, together with a simulator for the SB-PRAM, documentation, source code, and example programs. (http://www.informatik.uni-trier.de/~kessler/fork95)

We introduce a new language construct, the join statement, which allows to easily express synchronous parallel critical sections and provides a flexible means to switch from asynchronous to synchronous mode of program exectuion. We visualize its semantics by an excursion bus analogy, and exemplify how it can be applied in practice to speed up e.g. parallel shared heap memory allocation.