Memory optimization by counting points in integer transformations of parametric polytopes

ABSTRACT

Memory size reduction and memory accesses optimization are crucial issues for embedded systems. In the context of affine programs, these two challenges are classically tackled by array linearization, cache access optimization and memory size computation. Their formalization in the polyhedral model reduce to solving the following problem: count the number of solutions of a Presburger formula.In this paper we propose a novel algorithm that answers this question. We solve the Presburger formula whose solution is a union of parametric Z-polytopes and we propose an algorithm to count points in such a union of parametric Z-polytopes. These algorithms were implemented and we compare them to other existing methods.

REFERENCES

• 1: A. I. Barvinok. Computing the Ehrhart polynomial of a convex lattice polytope. Discrete Comput. Geom., 12:35--48, 1994.
• 2: 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]
• 3: Pierre Boulet , Xavier Redon, Communication Pre-evaluation in HPF, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.263-272, September 01-04, 1998
• 4: 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]
• 5: P. Dálberto, 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.
• 6: G. B. Dantzig and B. C. Eaves. Fourier-Motzkin elimination and its dual. J. Comb. Theory, Ser. A, 14(3):288--297, 1973.
• 7: J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida. Effective lattice point counting in rational convex polytopes. Journal of Symbolic Computation, 38(4):1273--1302, 2004.
• 8: E. Ehrhart. Polynômes arithmétiques et méthode des polyèdres en combinatoire. International Series of Numerical Mathematics, 35, 1977.
• 9: P. Feautrier. Parametric integer programming. Operationnelle/Operations Research, 22(3):243--268, 1988.
• 10: P. Feautrier, J. Collard, and C. Bastoul. Solving systems of affine (in)equalities. Technical report, PRiSM, Versailles University, 2002.
• 11: 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]
• 12: P. Held. Hipars:a tool for automatic conversion of nested loop programs into single assignment programs. Technical report, Dept. Electrical Engineering, Delft University of Technology, 1994.
• 13: W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Library. Technical report, Institue for advanced computer studies, University of Maryland, College Park, 1996.
• 14: V. Loechner. Polylib:A library for manipulating parameterized polyhedra. Technical report, LSIIT - ICPS UMR7005 Univ. Louis Pasteur-CNRS, Mar. 1999.
• 15: 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]
• 16: B. Meister. Projecting periodic polyhedra for loop nest analysis. In Proceedings of the 11th Workshop on Compilers for Parallel Computers (CPC 04), Kloster Seeon, Germany, pages 13--24, July 2004.
• 17: B. Meister. Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization. PhD thesis, December 2004.
• 18: S. P. K. Nookala and T. Risset. A library for Z-polyhedral operations. Technical report, 1330, Irisa, 2000.
• 19: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 20: 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.
• 21: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 22: 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
• 23: William Pugh , David Wonnacott, Experiences with Constraint-based Array Dependence Analysis, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.312-325, May 02-04, 1994
• 24: P. Quinton, S. Rajopadhye, and T. Risset. On manipulating Z-polyhedra using a canonical representation. Parallel Processing Letters, 7(2):181--194, 1997.
• 25: J. Ramanujam , Jinpyo Hong , Mahmut Kandemir , A. Narayan, Reducing memory requirements of nested loops for embedded systems, Proceedings of the 38th conference on Design automation, p.359-364, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378523]
• 26: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 27: R. Seghir and V. Loechner. Minimizing memory strides using integer transformations of parametric polytopes. Technical report, LSIIT-ICPS UMR7005 ULP-CNRS, oct 2006. http://icps. u-strasbg. fr.
• 28: Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Solving Out-of-Order Communication in Kahn Process Networks, Journal of VLSI Signal Processing Systems, v.40 n.1, p.7-18, May 2005 [doi>10.1007/s11265-005-4935-5]
• 29: S. Verdoolaege, K. Beyls, M. Bruynooghe, and F. Catthoor. Experiences with enumeration of integer projections of parametric polytopes. In R. Bodik, editor, Compiler Construction:14th International Conference, volume 3443, pages 91--105, Edinburgh, 3 2005. Springer.
• 30: Sven Verdoolaege , Rachid Seghir , Kristof Beyls , Vincent Loechner , Maurice Bruynooghe, Analytical computation of Ehrhart polynomials: enabling more compiler analyses and optimizations, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023868]
• 31: S. Verdoolaege and K. Woods. Counting with rational generating functions, 2005. http://arxiv. org/abs/math/0504059.
• 32: 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]
• 33: Hongwei Zhu , Ilie I. Luican , Florin Balasa, Memory size computation for multimedia processing applications, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118483]

INDEX TERMS

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

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

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

General Terms:
Algorithms, Performance

Keywords:
array linearization, cache access optimization, counting lattice points in polytopes, exact memory size computation, polytope model