Analytical computation of Ehrhart polynomials: enabling more compiler analyses and optimizations

ABSTRACT

Many optimization techniques, including several targeted specifically at embedded systems, depend on the ability to calculate the number of elements that satisfy certain conditions. If these conditions can be represented by linear constraints, then such problems are equivalent to counting the number of integer points in (possibly) parametric polytopes. It is well known that this parametric count can be represented by a set of Ehrhart polynomials. Previously, interpolation was used to obtain these polynomials, but this technique has several disadvantages. Its worst-case computation time for a single Ehrhart polynomial is exponential in the input size, even for fixed dimensions. The worst-case size of such an Ehrhart polynomial (measured in bits needed to represent the polynomial) is also exponential in the input size. Under certain conditions this technique even fails to produce a solution.Our main contribution is a novel method for calculating Ehrhart polynomials analytically. It extends an existing method, based on Barvinok's decomposition, for counting the number of integer points in a non-parametric polytope. Our technique always produces a solution and computes polynomially-sized Ehrhart polynomials in polynomial time (for fixed dimensions).

REFERENCES

• 1: A. Barvinok and J. Pommersheim. An algorithmic theory of lattice points in polyhedra. New Perspectives in Algebraic Combinatorics, (38):91--147, 1999.
• 2: A. I. Barvinok. A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. In 34th Annual Symposium on Foundations of Computer Science, pages 566--572. IEEE, Nov. 1993.
• 3: K. Beyls. Software Methods to Improve Data Locality and Cache Behavior. PhD thesis, Ghent University, 2004.
• 4: A. J. C. Bik. Compiler Support for Sparse Matrix Computations. PhD thesis, University of Leiden, The Netherlands, 1996.
• 5: Bernard Boigelot , Louis Latour, Counting the solutions of Presburger equations without enumerating them, Theoretical Computer Science, v.313 n.1, p.17-29, 16 February 2004 [doi>10.1016/j.tcs.2003.10.002]
• 6: V. Braberman, D. Garbervetsky, and S. Yovine. On synthesizing parametric specifications of dynamic memory utilization. Technical report, Oct. 2003.
• 7: M. Brion and M. Vergne. Residue formulae, vector partition functions and lattice points in rational polytopes. J. Amer. Math. Soc., 10:797--833, 1997.
• 8: R. Buck. Partition of space. American Mathematical Monthly, 50(9):541--544, 1943.
• 9: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 10: Philippe Clauss , Vincent Loechner, Parametric Analysis of Polyhedral Iteration Spaces, Journal of VLSI Signal Processing Systems, v.19 n.2, p.179-194, July 1998 [doi>10.1023/A:1008069920230]
• 11: P. D'Alberto, A. Veidembaum, A. Nicolau, and R. Gupta. Static analysis of parameterized loop nests for energy efficient use of data caches. In Workshop on Compilers and Operating Systems for Low Power (COLP01), Sept. 2001.
• 12: J. De Loera, D. Haws, R. Hemmecke, P. Huggins, B. Sturmfels, and R. Yoshida. Short rational functions for toric algebra and applications, July 2003. http://arxiv.org/abs/math.CO/0307350.
• 13: J. A. De Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, and R. Yoshida. A user's guide for latte v1.1, Nov. 2003. software package LattE is available at http://www.math.ucdavis.edu/~latte/.
• 14: J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida. Effective lattice point counting in rational convex polytopes, Mar. 2003. http://www.math.ucdavis.edu/~latte/theory.html.
• 15: E. Ehrhart. Polynômes arithmétiques et méthode des polyédres en combinatoire. International Series of Numerical Mathematics, 35, 1977.
• 16: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 17: Björn Franke , Michael O'boyle, Array recovery and high-level transformations for DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.132-162, May 2003 [doi>10.1145/643470.643472]
• 18: Free Software Foundation, Inc. GMP. Available from ftp://ftp.gnu.org/gnu/gmp.
• 19: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 20: N. Halbwachs, D. Merchat, and C. Parent-Vigouroux. Cartesian factoring of polyhedra in linear relation analysis. In Static Analysis Symposium, SAS'03, San Diego, June 2003. LNCS 2694, Springer Verlag.
• 21: Frank Hannig , Jürgen Teich, Design Space Exploration for Massively Parallel Processor Arrays, Proceedings of the 6th International Conference on Parallel Computing Technologies, p.51-65, September 03-07, 2001
• 22: W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega calculator and library. Technical report, University of Maryland, Nov. 1996.
• 23: B. Lisper. Fully automatic, parametric worst-case execution time analysis. In J. Gustafsson, editor, Proc. Third International Workshop on Worst-Case Execution Time (WCET) Analysis, pages 77--80, Porto, July 2003.
• 24: V. Loechner. Polylib: A library for manipulating parameterized polyhedra. Technical report, ICPS, Université Louis Pasteur de Strasbourg, France, Mar. 1999.
• 25: Vincent Loechner , Benoît Meister , Philippe Clauss, Precise Data Locality Optimization of Nested Loops, The Journal of Supercomputing, v.21 n.1, p.37-76, January 2002 [doi>10.1023/A:1013535431127]
• 26: Vincent Loechner , Doran K. Wilde, Parameterized polyhedra and their vertices, International Journal of Parallel Programming, v.25 n.6, p.525-549, Dec. 1997 [doi>10.1023/A:1025117523902]
• 27: B. Nootaert. Een verbeterde methode voor de berekening van Ehrhart-polynomen. Master's thesis, Ghent University, 2004.
• 28: E. Parker and S. Chatterjee. An automata-theoretic algorithm for counting solutions to Presburger formulas. In Compiler Construction 2004, volume 2985 of Lecture Notes in Computer Science, pages 104--119, Apr. 2004.
• 29: William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
• 30: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 31: V. Shoup. NTL. Available from http://www.shoup.net/ntl/.
• 32: Alexandru Turjan , Bart Kienhuis , Ed Deprettere, A Compile Time Based Approach for Solving Out-of-Order Communication in Kahn Process Networks, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.17, July 17-19, 2002
• 33: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.517-521, Oct., 2000 [doi>10.1109/92.894155]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

General Terms:
Algorithms, Performance

Keywords:
Barvinok's decomposition, Ehrhart polynomial, compiler analysis, parametric polytope, polyhedral model, quasi-polynomial, signed unimodular decomposition