Compilation of Nested Loop Programs into Process Networks.

Researchers: Bart Kienhuis
Advisor:Edward A. Lee

Novel high-performance, domain specific, embedded architectures are often composed of a microprocessor, some memory, and a number of dedicated coprocessors. On these embedded architectures, real-time applications will be executed that belong to the domains of multi-media processing, mobile communication, and adaptive array processing. These applications are often written in the C or Matlab language and contain parts that have a specific structure, referred to as a nested loop program.

The C and Matlab languages realize an imperative model of computation. Although this model of computation is well accepted to specify applications, it does not reveal parallelism due to its inherent sequential nature. But many applications contain alot of parallelism. Compilers exist that are able to extract instruction level parallelism from the original specifications at a very fine level of granularity. They are, however, unable to exploit coarse-grained parallelism offered by the coprocessors of the architectures. A better specification format would be to use an inherently parallel model of computation like process networks.

This research focuses on the automatic transformation of nested loop programs into process network specifications. The transformation consists of a number of steps.

  1. Extraction of a parameterized dependence graph from the nested loop program using parametric integer programming (PIP) [1]. The dependence graph expresses the available parallelism in the nested loop program.
  2. Conversion of the parameterized dependence graph into a polyhedral reduced dependence graph model. This model is based on polytopes, making the dependence graph more amenable to further mathematical manipulation.
  3. Manipulation of the polytope model. Various techniques are used like Ehrhart polynomials [2], Fourier/Motzkin, and various projection techniques to further manipulate polytopes and (re)construct missing polytopes [3].
  4. Generation of the network and the individual process network actors from the polyhedral reduced dependence graph model.
The resulting process network model is presented in the Ptolemy II system. This allows the combination of the derived process network description with other domains, thus enabling the description and simulation of more complex systems. Also, by attributing the process network model with power and latency numbers, various kinds of design space exploration can be done.

This work is done in cooperation with Delft University of Technology.

P. Feautrier, "Dataflow Analysis of Arrays and Scalar Reference" Recherche Operationelle; Operations Research. 1991
Ph. Clauss and V. Loechner, "Parametric Analysis of Polyhedral Iteration Spaces". Journal of VLSI Signal Processing. 1998
Patrice Quinton, Sanjay Rajopadhye, and Tanguy Risset, "On Manipulating Z-polyhedra", Tech. Rep., Institut de Recherche en Informatique et Systemes Aleatoires. 1996

Last updated 11/05/99