Translating affine nested-loop programs with dynamic loop bounds into Polyhedral Process Networks
- 1 October 2010
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2010 8th IEEE Workshop on Embedded Systems for Real-Time Multimedia
Abstract
The Process Network (PN) is a suitable parallel model of computation (MoC) used to specify embedded streaming applications in a parallel form facilitating the efficient mapping onto embedded parallel execution platforms. Unfortunately, specifying an application using a parallel MoC is very difficult and highly error-prone task. To overcome the associated difficulties, an automated procedure exists for derivation of a specific polyhedral process networks (PPN) from static affine nested loop programs (SANLPs). This procedure is implemented in the pn complier. However, there are many applications, e.g., multimedia applications (MPEG coders/decoders, smart cameras, etc.) that have adaptive and dynamic behavior which can not be expressed as SANLPs. Therefore, in order to handle more dynamic multimedia applications, in this paper we address the important question whether we can relax some of the restrictions of the SANLPs while keeping the ability to perform compile-time analysis and to derive PPNs. Achieving this would significantly extend the range of applications that can be parallelized in an automated way. The main contribution of this paper is a first approach for automated translation of affine nested loops programs with dynamic loop bounds into input-output equivalent polyhedral process networks.Keywords
This publication has 10 references indexed in Scilit:
- Trace-based KPN composability analysis for mapping simultaneous applications to MPSoC platformsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- pn: A Tool for Improved Derivation of Process NetworksEURASIP Journal on Embedded Systems, 2007
- Translating affine nested-loop programs to process networksPublished by Association for Computing Machinery (ACM) ,2004
- Automatic synthesis of system on chip multiprocessor architectures for process networksPublished by Association for Computing Machinery (ACM) ,2004
- Guaranteeing the Quality of Services in Networks on ChipPublished by Springer Science and Business Media LLC ,2003
- Multiprocessor mapping of process networksPublished by Association for Computing Machinery (ACM) ,2002
- Termination detection in parallel loop nests with while loopsParallel Computing, 1999
- Array SSA form and its use in parallelizationPublished by Association for Computing Machinery (ACM) ,1998
- Automatic parallelization in the polytope modelPublished by Springer Science and Business Media LLC ,1996
- Dataflow analysis of array and scalar referencesInternational Journal of Parallel Programming, 1991