Lattice-based memory allocation

ABSTRACT

We investigate the problem of memory reuse, for reducing the necessary memory size, in the context of compilation of dedicated processors. Memory reuse is a well-known concept when allocating registers (i.e., scalar variables). Its (recent) extension to arrays was studied mainly by Lefebvre and Feautrier (for loop parallelization) and by Quilleré and Rajopadhye (for circuit synthesis based on recurrence equations). Both consider affine mappings of indices to data, with modulo expressions in the first and (mainly) projections in the second. We develop a mathematical framework based on (integral) critical lattices that subsumes all previous approaches and gives new insights into the problem. Our technique consists first in building an abstract representation of conflicting indices (equivalent in a multi-dimensional space to the interference graph for register allocation), then in defining an integral lattice, admissible for the set of differences of conflicting indices, used to build a valid modular allocation. We also show the link with critical lattices, successive minima, and basis reduction, and we analyze various strategies for lattice-based memory allocation.

REFERENCES

• 1: Shail Aditya , Michael S. Schlansker, ShiftQ: a bufferred interconnect for custom loop accelerators, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502243]
• 2: A. Darte, M. Dion, and Y. Robert. A characterization of one-to-one modular mappings. Parallel Processing Letters, 5(1):145--157, 1996.
• 3: Alain Darte , Robert Schreiber , B. Ramakrishna Rau , Frédéric Vivien, Constructing and exploiting linear schedules with prescribed parallelism, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.159-172, January 2002 [doi>10.1145/504914.504921]
• 4: Alain Darte , Yves Robert , Frederic Vivien, Scheduling and Automatic Parallelization, Birkhauser Boston, 2000
• 5: C. Dwork. Lattices and their application to cryptography. Available as lecture notes http://theory.stanford.edu/~csilvers/cs359/, 1998.
• 6: F. Catthoor. etal. Atomium: A toolbox for optimising memory I/O using geometrical models. http://www.imec.be/design/atomium/.
• 7: P. Feautrier. Data flow analysis of scalar and array references. International Journal of Parallel Programming, 20(1):23--53, 1991.
• 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. M. Gruber. Geometry of numbers. In P. Gruber and J. Wills, editors, Handbook of Convex Geometry, volume~B, chapter 3.1, pages 739--763. Elsevier Science Publishers B.V., 1993.
• 10: P. M. Gruber and C. G. Lekkerkerker. Geometry of Numbers. North Holland, second edition, 1987.
• 11: L. Hafer. The generalized basis reduction algorithm (annotated). http://www.cs.sfu.ca/~lou/MITACS/grb.pdf, June 2000.
• 12: 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]
• 13: Bart Kienhuis , Edwin Rijpkema , Ed Deprettere, Compaan: deriving process networks from Matlab for embedded signal processing architectures, Proceedings of the eighth international workshop on Hardware/software codesign, p.13-17, May 2000, San Diego, California, United States [doi>10.1145/334012.334015]
• 14: Jeffrey C. Lagarias, Point lattices, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 15: 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]
• 16: L. Lovász. An Algorithmic Theory of Numbers, Graphs, and Convexity, volume 50 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, 1986.
• 17: 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]
• 18: M. Newman. Integral Matrices. Academic Press, 1972.
• 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: P. Quinton, S. Rajopadhye, T. Risset, et al. Alpha homepage: A language dedicated to the synthesis of regular architectures. http://www.irisa.fr/cosi/.
• 21: 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
• 22: 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
• 23: A. Turjan and B. Kienhuis. Storage management in process networks using the lexicographically maximal preimage. In 14th International Conference on Application-specific Systems, Architectures and Processors (ASAP'03), The Hague, The Netherlands, June 2003. IEEE Computer Society Press.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization; Automatic synthesis

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
admissible lattice, critical determinant, memory allocation, program transformation, successive minima