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.
Complete list of metadatas

https://hal.inria.fr/inria-00582388
Contributor : Vincent Loechner <>
Submitted on : Friday, April 1, 2011 - 12:17:10 PM
Last modification on : Wednesday, April 3, 2019 - 1:23:11 AM

Links full text

Identifiers

Collections

Citation

Rachid Seghir, Vincent Loechner, Benoit Meister. Integer Affine Transformations of Parametric Z-polytopes and Applications to Loop Nest Optimization. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2012, 9 (2), pp.8.1-8.27. ⟨10.1145/2207222.2207224⟩. ⟨inria-00582388⟩

Share

Metrics

Record views

169