Parametric Analysis of Polyhedral Iteration Spaces

Abstract : In the area of automatic parallelization of programs, analyzing and transforming loop nests with parametric affine loop bounds requires fundamental mathematical results. The most common geometrical model of iteration spaces, called the polytope model, is based on mathematics dealing with convex and discrete geometry, linear programming, combinatorics and geometry of numbers. In this paper, we present automatic methods for computing the parametric vertices and the Ehrhart polynomial, i.e., a parametric expression of the number of integer points, of a polytope defined by a set of parametric linear constraints. These methods have many applications in analysis and transformations of nested loop programs. The paper is illustrated with exact symbolic array dataflow analysis, estimation of execution time, and with the computation of the maximum available parallelism of given loop nests.
Type de document :
Article dans une revue
Journal of VLSI Signal Processing / J VLSI Sign Process Syst Sign Image Video Technol, Kluwer Academic Publishers, 1998, 19 (2), pp.179-194. 〈10.1023/A:1008069920230〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00534840
Contributeur : Vincent Loechner <>
Soumis le : mercredi 10 novembre 2010 - 15:56:10
Dernière modification le : jeudi 11 janvier 2018 - 06:22:09

Identifiants

Collections

Citation

Philippe Clauss, Vincent Loechner. Parametric Analysis of Polyhedral Iteration Spaces. Journal of VLSI Signal Processing / J VLSI Sign Process Syst Sign Image Video Technol, Kluwer Academic Publishers, 1998, 19 (2), pp.179-194. 〈10.1023/A:1008069920230〉. 〈inria-00534840〉

Partager

Métriques

Consultations de la notice

36