Bee+Cl@k: an implementation of lattice-based array contraction in the source-to-source translator rose

ABSTRACT

We build on prior work on intra-array memory reuse, for which a general theoretical framework was proposed based on lattice theory. Intra-array memory reuse is a way of reducing the size of a temporary array by folding, thanks to affine mappings and modulo operations, reusing memory locations when they contain a value not used later. We describe the algorithms needed to implement such a strategy. Our implementation has two parts. The first part, Bee, uses the source-to-source transformer ROSE to extract from the program all necessary information on the lifetime of array elements and to generate the code after memory reduction. The second part, Cl@k, is a stand-alone mathematical tool dedicated to optimizations on polyhedra, in particular the computation of successive minima and the computation of good admissible lattices, which are the basis for lattice-based memory reuse. Both tools are developed in C++ and use linear programming and polyhedra manipulations. They can be used either for embedded program optimizations, e.g., to limit memory expansion introduced for parallelization, or in high-level synthesis, e.g., to design memories between communicating hardware accelerators.

REFERENCES

• 1: Florin Balasa , Francky Catthoor , Hugo de Man, Exact evaluation of memory size for multi-dimensional signal processing systems, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.669-672, November 07-11, 1993, Santa Clara, California, United States
• 2: F. Balasa , P. G. Kjeldsberg , M. Palkovic , A. Vandecappelle , F. Catthoor, Loop Transformation Methodologies for Array-Oriented Memory Management, Proceedings of the IEEE 17th International Conference on Application-specific Systems, Architectures and Processors (ASAP'06), p.205-212, September 11-13, 2006 [doi>10.1109/ASAP.2006.42]
• 3: P. Clauss, F.J. Fernandez, D. Gabervetsky, and S. Verdoolaege. Symbolic polynomial maximization over convex sets and its application to memory requirement estimation. T.R. ICPS number 06-04, Université L. Pasteur, Oct. 2006.
• 4: Jean-François Collard , Denis Barthou , Paul Feautrier, Fuzzy array dataflow analysis, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.92-101, July 19-21, 1995, Santa Barbara, California, United States
• 5: Alain Darte , Guillaume Huard, New Complexity Results on Array Contraction and Related Problems, Journal of VLSI Signal Processing Systems, v.40 n.1, p.35-55, May 2005 [doi>10.1007/s11265-005-4937-3]
• 6: Alain Darte , Rob Schreiber , Gilles Villard, Lattice-based memory allocation, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951749]
• 7: Alain Darte , Robert Schreiber , Gilles Villard, Lattice-Based Memory Allocation, IEEE Transactions on Computers, v.54 n.10, p.1242-1257, October 2005 [doi>10.1109/TC.2005.167]
• 8: Eddy De Greef , Francky Catthoor , Hugo De Man, Memory size reduction through storage order optimization for embedded parallel multimedia applications, Parallel Computing, v.23 n.12, p.1811-1837, Dec. 1997 [doi>10.1016/S0167-8191(97)00089-6]
• 9: P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22(3):243--268, 1988.
• 10: P. Feautrier. Data flow analysis of scalar and array references. International Journal of Parallel Programming, 20(1):23--53, 1991.
• 11: GNU Free Software. GLPK (GNU Linear Programming Kit). http://www.gnu.org/software/glpk.
• 12: P.M. Gruber and C.G. Lekkerkerker. Geometry of Numbers. North Holland, second edition, 1987.
• 13: Vinod Kathail , Shail Aditya , Robert Schreiber , B. Ramakrishna Rau , Darren C. Cronquist , Mukund Sivaraman, PICO: Automatically Designing Custom Computers, Computer, v.35 n.9, p.39-47, September 2002 [doi>10.1109/MC.2002.1033026]
• 14: Vincent Lefebvre , Paul Feautrier, Automatic storage management for parallel programs, Parallel Computing, v.24 n.3-4, p.649-671, May, 1998 [doi>10.1016/S0167-8191(98)00029-5]
• 15: László Lovász , Herbert E. Scarf, The generalized basis reduction algorithm, Mathematics of Operations Research, v.17 n.3, p.751-764, Aug. 1992 [doi>10.1287/moor.17.3.751]
• 16: M. Newman. Integral Matrices. Academic Press, 1972.
• 17: PIP/Polylib: http://www.piplib.org.
• 18: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 19: Fabien Quilleré , Sanjay Rajopadhye, Optimizing memory usage in the polyhedral model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.773-815, Sept. 2000 [doi>10.1145/365151.365152]
• 20: D.J. Quinlan. ROSE: Compiler support for object-oriented frameworks. Parallel Proc. Letters, 10(2/3):215--226, 2000.
• 21: 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]
• 22: Georges-André Silber , Alain Darte, the NESTOR Library: A Tool for Implementing FORTRAN Source Transformations, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.653-662, April 12-14, 1999
• 23: Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Improving Data Locality by Array Contraction, IEEE Transactions on Computers, v.53 n.9, p.1073-1084, September 2004 [doi>10.1109/TC.2004.62]
• 24: Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Beth Simon, Schedule-independent storage mapping for loops, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.24-33, October 02-07, 1998, San Jose, California, United States
• 25: William Thies , Frédéric Vivien , Jeffrey Sheldon , Saman Amarasinghe, A unified framework for schedule and storage optimization, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.232-242, June 2001, Snowbird, Utah, United States
• 26: Remko Tronçon , Maurice Bruynooghe , Gerda Janssens , Francky Catthoor, Storage Size Reduction by In-place Mapping of Arrays, Revised Papers from the Third International Workshop on Verification, Model Checking, and Abstract Interpretation, p.167-181, January 21-22, 2002
• 27: Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Translating affine nested-loop programs to process networks, 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.1023864]
• 28: Sumesh Udayakumaran , Angel Dominguez , Rajeev Barua, Dynamic allocation for scratch-pad memory using compile-time decisions, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.2, p.472-511, May 2006 [doi>10.1145/1151074.1151085]
• 29: S. Verdoolaege, H. Nikolov, and T. Stefanov. Improved derivation of process networks. In Workshop on Opt. for DSP and Embedded Systems (ODES-4), Mar. 2006.
• 30: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 31: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310074]
• 32: 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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
lattices, memory reduction, program analysis, source-to-source transformations