An example: the maximum parallelism

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

Indonesian noodles - indomie mi goreng at eFoodDepot.com

 

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