Scratchpad allocation for data aggregates in superperfect graphs

ABSTRACT

Existing methods place data or code in scratchpad memory, i.e., SPM by either relying on heuristics or resorting to integer programming or mapping it to a graph coloring problem.

In this work, the SPM allocation problem is formulated as an interval coloring problem. The key observation is that in many embedded applications, arrays (including structs as a special case) are often related in the following way: For any two arrays, their live ranges are often such that one is either disjoint from or contains the other. As a result, array interference graphs are often superperfect graphs and optimal interval colorings for such array interference graphs are possible. This has led to the development of two new SPM allocation algorithms. While differing in whether live range splits and spills are done sequentially or together, both algorithms place arrays in SPM based on examining the cliques in an interference graph. In both cases, we guarantee optimally that all arrays in an interference graph can be placed in SPM if its size is no smaller than the clique number of the graph. In the case that the SPM is not large enough, we rely on heuristics to split or spill a live range until the graph is colorable. Our experiment results using embedded benchmarks show that our algorithms can outperform graph coloring when their interference graphs are superperfect or nearly so although graph coloring is admittedly more general and may also be effective to applications with arbitrary interference graphs.

REFERENCES

• 1: Christian Andersson. Register allocation by optimal graph coloring. In CC'03: Proceedings of the 12th International Conference on Compiler Construction. Springer-Verlag, 2003.
• 2: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 3: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 4: Giuseppe Confessore , Paolo Dell'Olmo , Stefano Giordani, An approximation result for the interval coloring problem on claw-free chordal graphs, Discrete Applied Mathematics, v.120 n.1-3, p.73-90, 15 August 2002 [doi>10.1016/S0166-218X(01)00282-7]
• 5: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 6: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 7: Janet Fabri, Automatic storage optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.83-91, August 06-10, 1979, Denver, Colorado, United States
• 8: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 11: Jordan Gergov, Algorithms for compile-time memory optimization, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.907-908, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland Publishing Co., Amsterdam, The Netherlands, 2004
• 13: Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in ssa-form. In CC'06: Proceedings of the 15th International Conference on Compiler Construction. Springer-Verlag, 2006.
• 14: Qingguang Huang, Jingling Xue, and Xavier Vera. Code tiling for improving the cache performance of PDE solvers. In International Conference on Parallel Processing, pages 615--625, 2003.
• 15: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 16: H. A. Kierstead, A polynomial time approximation algorithm for Dynamic Storage Allocation, Discrete Mathematics, v.87 n.2-3, p.231-237, Jan. 31 1991
• 17: Lian Li , Lin Gao , Jingling Xue, Memory Coloring: A Compiler Approach for Scratchpad Memory Management, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.329-338, September 17-21, 2005 [doi>10.1109/PACT.2005.27]
• 18: Sriram V. Pemmaraju , Sriram Penumatcha , Rajiv Raman, Approximating interval coloring and max-coloring in chordal graphs, Journal of Experimental Algorithmics (JEA), 10, 2005 [doi>10.1145/1064546.1180619]
• 19: Fernando Magno Quintão Pereira and Jens Palsberg. Register allocation via coloring of chordal graphs. In APLAS'05: Proceedings of the 3rd Asia Symposium on Programming Languages and Systems, pages 315--329, 2005.
• 20: Rajiv A. Ravindran , Pracheeti D. Nagarkar , Ganesh S. Dasika , Eric D. Marsman , Robert M. Senger , Scott A. Mahlke , Richard B. Brown, Compiler Managed Dynamic Instruction Placement in a Low-Power Code Cache, Proceedings of the international symposium on Code generation and optimization, p.179-190, March 20-23, 2005 [doi>10.1109/CGO.2005.13]
• 21: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, 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.502221]
• 22: Michael D. Smith , Norman Ramsey , Glenn Holloway, A generalized algorithm for graph-coloring register allocation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 23: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, 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.951747]
• 24: Manish Verma , Lars Wehmeyer , Peter Marwedel, Dynamic overlay of scratchpad memory for energy minimization, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016748]
• 25: Thomas Zeitlhofer , Bernhard Wess, List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures, Signal Processing, v.83 n.7, p.1411-1425, July 2003 [doi>10.1016/S0165-1684(03)00089-6]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Primary memory

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

General Terms:
Algorithms, Performance

Keywords:
SPM, SPM allocation, interval coloring, scratchpad memory, superperfect graph