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

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.

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