loading...
Parametric Analysis of Polyhedral Iteration Spaces
Chicago, IL August 19-August 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ASAP.1996.5428331996 IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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 an automatic method for computing the number of integer points contained in a convex polytope or in a union of convex polytopes. The procedure consists of first, computing the parametric vertices of a polytope defined by a set of parametric linear constraints, and then computing the Ehrhart polynomial, i.e. a parametric expression of the number of integer points. The paper is illustrated with the computation of the maximum available parallelism of a given loop nest.
Index Terms:
automatic parallelization, nested loops, convex polyhedra, parametric vertices, parametric counting, Ehrhart polynomials
Citation:
Ph. Clauss, V. Loechner, "Parametric Analysis of Polyhedral Iteration Spaces," asap, pp.415, 1996 IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'96), 1996
Usage of this product signifies your acceptance of the Terms of Use.