Estimation of nested loops execution time by integer arithmetic in convex polyhedra
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 217-221
- https://doi.org/10.1109/ipps.1994.288298
Abstract
Estimating the execution time of nested loops or the vol- ume of data transferred between processors is necessary to make appropriate processor or data allocation. To achieve this goal one need to estimate the execution time of the body and thus the number of nested loop iterations. This work could be a preprocessing step in an automatic poralleliz- ing compilers to enhance the performance of the resulting parallel program. A bounded convex polyhedron can be associated with each loop nest. The number of its integer points corre- sponds to the iteration space size. In this paper, we present an algorithm that approximates this number. The algo- rithm is not restricted to a fixed dimension. The worst case complexity of the algorithm is infrequently reached in our context where the nesting level is rather small and the loop bound expressions are not very complex.Keywords
This publication has 4 references indexed in Scilit:
- Processor allocation and loop scheduling on multiprocessor computersPublished by Association for Computing Machinery (ACM) ,1992
- On Counting Lattice Points in PolyhedraSIAM Journal on Computing, 1991
- On the Complexity of Computing the Volume of a PolyhedronSIAM Journal on Computing, 1988
- Deciding Linear Inequalities by Computing Loop ResiduesJournal of the ACM, 1981