An Overview of the Compilation Process for a New Parallel Architecture

Inderjit Dhillon, Narendra Karmarkar, K. Ramakrishnan

Abstract:   This paper discuss the design of a compiler for a new parallel machine. In a first version of the parallel machine, we concentrate on scientific applications that involve several numerical iterations on the same symbolic structure of the problem. The traditional compilation process is a 2-phase process, i.e., compilation followed by execution. In order to speed up later numerical iterations, we propose a 3-phase process. In the first phase, the precompilation phase, a higher level language representation of the computation, along with the symbolic structure of the input data is converted to an intermediate representation. A data flow graph (DFG), that captures the data flow of the symbolic instance of the computation. In the second phase, the computer takes a DFG as input and produces machine code for execution on the parallel machine. The compiler maps the data onto the memory modules and schedules the operations onto the processors in a conflict free manner, in order to achieve maximum efficiency. The final phase, the numerical execution phase. Execution of the machine code given numerical input data results in several numerical iterations. For some important sparse matrix operations, we have designed a bypass compiler which directly produces machine code for the particular computation given symbolic input data. We have designed a compiler for a novel architecture where the interconnection between the processors and memory modules is based on finite projective geometries [KAR90, KAR91]. Properties of the geometry enable the compiler to efficiently detect conflict-free operations, partition the data among the memory modules, and balance the load equally among the processors. Our simulation experiments show that high efficiency (>90%) can be achieved for matrix-vector multiply routines on a parallel machine based on two dimensional projective geometries.

Download: pdf


  • An Overview of the Compilation Process for a New Parallel Architecture (pdf, software)
    I. Dhillon, N. Karmarkar, K. Ramakrishnan.
    Supercomputing Symposium, pp. 471-486, June 1991.