Parallel Programming with PEI

Eric Violard

A wide range of research works on the static analysis of programs and forms the foundations of parallelization techniques. They greatly benefit from methods for automatic synthesis of VLSI systolic circuits from recurrence equations.

These methods are based on geometrical transformations either of the iteration space or of the index domain of arrays. In some sense, it shows that beside a classical functional point of view on programs, geometrical issues in parallel programming or parallelizing compilation have to be considered of main importance. The recent developments on the so-called Data Parallel programming model reinforces this idea.

PEI was born of this approach and was introduced to express and transform parallel programs. It enables to define and apply pointwise operations on the basic objects of the language, called data fields - a kind of parallel variables. Abstract reference domains are also defined. Conformity of data fields or hypotheses on their domains have to be checked in order to apply operations or to transform programs. This requires PEI to be a strongly typed language in which the types of data fields, definition domains of partial functions on Z^n, can be inferred. The type system any correct PEI expression must solve is defined by induction on the syntactic constructs of the language through inference rules. It can be expressed in a normal form by applying confluent rules and then be solved.

The typechecking algorithm has been implemented by using the Omega library which evaluates Presburger formulae and it works for a wide range of data field expressions.