Integer Affine Transformations of Parametric Z-polytopes and Applications to Loop Nest Optimization

Abstract : The polyhedral model is a well-known compiler optimization framework for the analysis and transformation of affine loop nests. We present a new method concerning a difficult geometric operation that is raised by this model: the integer affine transformation of parametric Z-polytopes. The result of such a transformation is given by a worst-case exponential union of Z-polytopes. We also propose a polynomial algorithm (for fixed dimension), to count points in arbitrary unions of a fixed number of parametric Z-polytopes. We implemented these algorithms and compared them to other existing algorithms, for a set of applications to loop nest analysis and optimization.
Document type :
Reports
[Research Report] 2010, pp.30
Liste complète des métadonnées

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/inria-00534686
Contributor : Vincent Loechner <>
Submitted on : Wednesday, November 10, 2010 - 12:15:52 PM
Last modification on : Thursday, January 11, 2018 - 6:23:13 AM
Document(s) archivé(s) le : Friday, February 11, 2011 - 2:57:54 AM

Files

rapport.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00534686, version 1

Collections

Citation

Rachid Seghir, Vincent Loechner, Benoit Meister. Integer Affine Transformations of Parametric Z-polytopes and Applications to Loop Nest Optimization. [Research Report] 2010, pp.30. 〈inria-00534686〉

Share

Metrics

Record views

285

Files downloads

301