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.
- 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.
- 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.
- 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].
- 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.
- [1]
- P. Feautrier, "Dataflow Analysis of Arrays and Scalar Reference"
Recherche Operationelle; Operations Research. 1991
- [2]
- Ph. Clauss and V. Loechner, "Parametric Analysis of Polyhedral
Iteration Spaces". Journal of VLSI Signal Processing. 1998
- [3]
- 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