EHRHART POLYNOMIALS FOR PRECISE PROGRAM ANALYSIS

Optimizing compilers need to be able to analyse nested loop programs with parametric affine loop bounds, in order to derive efficient programs. The iteration spaces of nested loop programs can be modeled by polyhedra and systems of linear constraints. Using this model, important program analysis such as computing:

• The number of flops executed by a loop,
• The number of memory locations or cache lines touched by a loop,
• The amount of processor to processor communication needed during the execution of a loop,
• The maximum parallelism induced by a loop from a given time-schedule,
• The number of processors needed from a given mapping function,
• The amount of communications from a given loop and data partitioning,
• The number of cache misses from a given loop and data partitioning,
• The execution step of an iteration according to the lexicographic order,
• The last iteration updating an array element before a given use of it (exact symbolic array dataflow analysis),
• ....

The resulting information can be used to:

• Estimate the execution time of a code segment,
• Compare the memory bandwidth requirements vs. the flop counts of a code segment,
• Determine which loops will flush the cache, and then calculate the cache miss rate,
• Determine if a loop is load balanced (i.e., performs the same amount of computation in each iteration), or if not balanced,
• Determine number of iterations to assign each processor in order to balance the work load (balanced chunk-scheduling),
• Exploit maximum parallelism,
• Optimize the number of needed processors,
• Optimize loop and data partitioning,
• Improve parallelism,
• ....

We have developped a method for deriving a closed-form symbolic formula for the number of integer points contained in a polyhedral region in terms of size parameters. If the set of integer points to be counted lies inside a union of rational convex polytopes, then the number of points can be formulated by a special kind of polynomial called Ehrhart polynomial. The procedure consists of first, computing the parametric vertices of a polytope defined by a set of parametric linear constraints, and then solving for an Ehrhart polynomial which gives the exact formula for the number of integer points in the polytope.

We have also proposed an extension to the counting of integer points in linear and non-linear mappings of polytopes.

We are now trying to handle countings for non-linearly parameterized constraints, here is the 1st research report on the subject.

More about EHRHART POLYNOMIALS

• An example: the maximum parallelism

  • Problem description
  • The parametric vertices
  • Ehrhart polynomials and maximum parallelism

• Related publications and research reports

  • Ph. Clauss and V. Loechner, Parametric Analysis of Polyhedral Iteration Spaces, extended version, Journal of VLSI Signal Processing, Vol. 19, No. 2, p. 179-194, Kluwer Academic Pub., July 1998.

  • Ph. Clauss, Advances in parameterized linear diophantine equations for precise program analysis, [ICPS RR 98-02], September 1998.

  • Ph. Clauss, Counting Solutions to Linear and Nonlinear Constraints through Ehrhart polynomials: Applications to Analyze and Transform Scientific Programs, research report ICPS 96-03, 10th ACM Int. Conf. on Supercomputing, ICS'96, May 1996.

  • Ph. Clauss, V. Loechner, Parametric Analysis of Polyhedral Iteration Spaces, research report ICPS 96-04, IEEE Int. Conf. on Application Specific Array Processors, ASAP'96, Chicago, Illinois, August 1996.

  • Ph. Clauss, V. Loechner and D.K. Wilde, Deriving Formulae to Count Solutions to Parameterized Linear Systems using Ehrhart Polynomials: Applications to the Analysis of Nested-Loop Programs, ICPS RR 97-05, April 1997.

  • V. Loechner, D. K. Wilde, Parameterized polyhedra and their vertices, ICPS RR 96-09, July 1996.

  • Ph. Clauss, Handling Memory Cache Policy with Integer Points Countings, research report ICPS 97-02, january 1997. Here is the reduced version that appears in the proceedings of Euro-Par'97.

  • Ph. Clauss, The Volume of a Lattice Polyhedron to Enumerate Processors and Parallelism, research report ICPS 95-11. Here is a more math version of this paper

  • Ph. Clauss and B. Meister, Automatic Memory Layout Transformation to Optimize Spatial Locality in Parameterized Loop Nests, ACM SIGARCH, Computer Architecture News, Vol. 28, No. 1, p.11-19, March 2000.

• Persons involved in the project

  • Philippe Clauss
  • Vincent Loechner
  • Doran K. Wilde

• Related links

  • A tribute to Eugène Ehrhart
  • Eugène Ehrhart's publications 1947-1996
  • Some nice drawings by Eugène Ehrhart himself !
  • A poem that Eugène Ehrhart wrote when he was about 14 years old (in french of course)

• Other related projects

  • The Polyhedral Library by Doran Wilde
  • The Omega Project by W. Pugh
  • LattE : first ever implementation of Barvinok's algorithm for computing the rational generating function of a polytope by Jesus A. De Loera and his group
  • barvinok : a program computing the Ehrhart polynomial of a parameterized polytope based on Barvinok's algorithm by Sven Verdoolaege

• Some works using Ehrhart polynomials

  • Compilation of Matlab to Process Networks (Compaan) by Ed F. Deprettere, Edwin Rijpkema, Paul Lieverse and Bart Kienhuis
  • Exact Analysis of the Cache Behavior of Nested Loops by Siddhartha Chatterjee
  • Cache Miss Equations: An Analytical Representation of Cache Misses by Somnath Ghosh
  • Volume Driven Selection of Loop and Data Transformation for Cache-Coherent Parallel Processors by Adrian Slowik
  • Probabilistic Memory Disambiguation and its Application to Data Speculation by Jean-François Collard
  • SPPoC: Symbolic Parameterized Polyhedral Calculator by Pierre Boulet, Xavier Redon