skip to main content
10.1145/1023833.1023868acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
Article

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

Published: 22 September 2004 Publication History

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]
B. Boigelot and L. Latour. Counting the solutions of Presburger equations without enumerating them. Theoretical Computer Science, (313):17--29, 2004.]]
[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]
S. Chatterjee, E. Parker, P. J. Hanlon, and A. R. Lebeck. Exact analysis of the cache behavior of nested loops. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, pages 286--297. ACM Press, 2001.]]
[10]
P. Clauss and V. Loechner. Parametric Analysis of Polyhedral Iteration Spaces. Journal of VLSI Signal Processing, 19(2):179--194, July 1998.]]
[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]
J. Ferrante, V. Sarkar, and W. Thrash. On estimating and enhancing cache effectiveness. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, volume 589 of Lecture Notes in Computer Science, pages 328--343. Springer-Verlag, Aug. 1991.]]
[17]
B. Franke and M. O'Boyle. Array recovery and high-level transformations for DSP applications. ACM Transactions on Embedded Computing Systems, 2(2):132--162, May 2003.]]
[18]
Free Software Foundation, Inc. GMP. Available from ftp://ftp.gnu.org/gnu/gmp.]]
[19]
S. Ghosh, M. Martonosi, and S. Malik. Cache miss equations: a compiler framework for analyzing and tuning memory behavior. ACM Transactions on Programming Languages and Systems, 21(4):703--746, 1999.]]
[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]
F. Hannig and J. Teich. Design space exploration for massively parallel processor arrays. In Proceedings of the Sixth International Conference on Parallel Computing Technologies, volume 2127 of Lecture Notes in Computer Science, pages 51--65, 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]
V. Loechner, B. Meister, and P. Clauss. Precise data locality optimization of nested loops. J. Supercomput., 21(1):37--76, 2002.]]
[26]
V. Loechner and D. K. Wilde. Parameterized polyhedra and their vertices. International Journal of Parallel Programming, 25(6):525--549, Dec. 1997.]]
[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]
W. Pugh. Counting solutions to Presburger formulas: How and why. In SIGPLAN Conference on Programming Language Design and Implementation (PLDI'94), pages 121--134, 1994.]]
[30]
A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1986.]]
[31]
V. Shoup. NTL. Available from http://www.shoup.net/ntl/.]]
[32]
A. Turjan, B. Kienhuis, and E. Deprettere. A compile time based approach for solving out-of-order communication in Kahn Process Networks. In IEEE 13th International Conference on Aplication-specific Systems, Architectures and Processors (ASAP'2002), July 2002.]]
[33]
Y. Zhao and S. Malik. Exact memory size estimation for array computations. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 8(5):517--521, October 2000.]]

Cited By

View all
  • (2023)When ties are possible: Weak Condorcet winners and Arrovian rationalityMathematical Social Sciences10.1016/j.mathsocsci.2023.03.004Online publication date: Mar-2023
  • (2023)A Society Can Always Decide How to Decide: A ProofGroup Decision and Negotiation10.1007/s10726-023-09826-032:5(987-1023)Online publication date: 11-May-2023
  • (2022) BullsEye : Scalable and Accurate Approximation Framework for Cache Miss CalculationACM Transactions on Architecture and Code Optimization10.1145/355800320:1(1-28)Online publication date: 17-Nov-2022
  • Show More Cited By

Index Terms

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

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems
        September 2004
        324 pages
        ISBN:1581138903
        DOI:10.1145/1023833
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 22 September 2004

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. Barvinok's decomposition
        2. Ehrhart polynomial
        3. compiler analysis
        4. parametric polytope
        5. polyhedral model
        6. quasi-polynomial
        7. signed unimodular decomposition

        Qualifiers

        • Article

        Conference

        CASES04

        Acceptance Rates

        Overall Acceptance Rate 52 of 230 submissions, 23%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)7
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 16 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2023)When ties are possible: Weak Condorcet winners and Arrovian rationalityMathematical Social Sciences10.1016/j.mathsocsci.2023.03.004Online publication date: Mar-2023
        • (2023)A Society Can Always Decide How to Decide: A ProofGroup Decision and Negotiation10.1007/s10726-023-09826-032:5(987-1023)Online publication date: 11-May-2023
        • (2022) BullsEye : Scalable and Accurate Approximation Framework for Cache Miss CalculationACM Transactions on Architecture and Code Optimization10.1145/355800320:1(1-28)Online publication date: 17-Nov-2022
        • (2022)Inconsistent weighting in weighted voting gamesPublic Choice10.1007/s11127-021-00951-5191:1-2(75-103)Online publication date: 25-Jan-2022
        • (2021)Majority properties of positional social preference correspondencesTheory and Decision10.1007/s11238-021-09828-xOnline publication date: 15-Jun-2021
        • (2020)Dummy Players and the Quota in Weighted Voting GamesGroup Decision and Negotiation10.1007/s10726-020-09705-yOnline publication date: 21-Sep-2020
        • (2020)The Effect of Closeness on the Election of a Pairwise Majority Rule WinnerEvaluating Voting Systems with Probability Models10.1007/978-3-030-48598-6_4(75-95)Online publication date: 19-Dec-2020
        • (2020)From Gehrlein-Fishburn’s Method on Frequency Representation to a Direct Proof of Ehrhart’s extended ConjectureEvaluating Voting Systems with Probability Models10.1007/978-3-030-48598-6_16(367-398)Online publication date: 19-Dec-2020
        • (2018)Locality analysis through static parallel samplingACM SIGPLAN Notices10.1145/3296979.319240253:4(557-570)Online publication date: 11-Jun-2018
        • (2018)Locality analysis through static parallel samplingProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192402(557-570)Online publication date: 11-Jun-2018
        • Show More Cited By

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media