A Hybrid MIMD/DF Compiler for Parallel Processing

PhD Thesis, 1992

Nory Nakhaee

(Founded ALPHA DATA Parallel Systems Ltd)

Abstract

A new parallel detection algorithm is devised based on the automatic construction and execution of Petri nets for sequential source programs. The algorithm forms part of a hybrid data-flow and MIMD compiler written in POP-l1 and accepts Pascal-S source code.

During the compilation process a Petri net model of the input program is constructed. Execution of the resulting net generates a multi-layered code to reveal the full parallelism inherent in the source program. Each layer consists of several independent parallel statements, which are statically allocated to available processing nodes. The allocator optimizes the communication overhead by using a novel static load balancing technique. Both medium and fine grain parallelism are exploited. Fine grain parallelism is implemented by introducing the co-processor concept.

The implementation offers several other novel features including table-driven analysers (potentially adaptable for different source languages), an algorithm for manipulating symbol tables, and combining parallelism detection and scheduling to eliminate the multiple assignment problem.

Full description of all algorithms including many examples is provided.