Functional Parallel Computing

Stephen Eriksson-Bique, Elena Trichina

An obstacle in programming multiprocessor networks is that a programmer must be aware of, and explicitly maintain, the degree of physical parallelism as well as the communication and configuration structure of the hardware. This degrades not only the portability of programs, but also the efficiency of software development. One approach to address both issues is to use a higher-order functional language (so called Bird-Meertens formalism [1]) as a computation model that is universal over four important classes of parallel architectures, namely SIMD computers, tightly coupled (shared memory) MIMD computers, hypercuboid an d constant-valence MIMD computer [2]. The details of the implementation of each of the higher-order functions on a particular architecture form what may be seen as a basis for a family of "parallelizing compilers." We are investigating the development of such a compiler for constant-valence MIMD computers. Transputer networks [3] have been chosen as a representative of that class. The language we want to compile higher-order functions into must be implementable in a way that harnesses the potential power of the architecture. One such language is occam 2 [4]; its design has been closely associated with the development of the transputer and yet it is an abstract language that has the dual role of being an implementation language and a design formalism.

Ideally, we would like to be able to translate a functional program written in a form of equations in the Bird-Meertens formalism to occam 2 at the language syntax level; that is, apply a finite number of syntactic transformations to a functional program to obtain an equivalent occam 2 version. This is a nontrivial research issue and is beyond the scope of our work. Where both languages share common ground is at a data-flow graph description level [5]. A functional program has a natural interpretation as a data-flow graph, where nodes represent functions, and edges denote data dependencies between functions. Similarly, the main interpretation of an occam 2 program is that it consists of a finite number of communicating sequential processes, which can be abstracted as a process graph, where nodes represent processes, and edges represent communication channels between processes. Essentially, data-flow edges map to occam channels, and data-flow nodes to ocamm processes. This relationship can be developed formally; both dynamic and static flow have natural translations into occam 2, which preserve the data-flow semantics and concurrency [5].

We consider an implementation of the set of higher-order functions typical for the Bird-Meertens formalism based on a data-flow model. This process involves three steps. First, a data-flow analysis of each of the second-order functions results in a corresponding data-flow graph (or rather a family of data-flow graphs) capturing the semantics of the function. The second step represents a straightforward translation of a graph into an occam 2 code implementing the process described by this graph. Third, we consider a few possibilities of efficient implementation of different compositions of higher-order functions.

To assess our compilation scheme we derive occam 2 programs for some of the so-called Cowichan Problems [6].

REFERENCES

Click research in parallel computing at the University of Joensuu.