Scalable interprocedural register allocation for high level synthesis

ABSTRACT

The success of classical high level synthesis has been limited by the complexity of the applications it can handle, typically not large enough to necessitate the departure from the industrial standard, register transfer level design methodology. Recent advances of micro-architecture model enabled the use of stacked based controller, allowing complex algorithms with multiple procedures to be implemented directly in hardware. Nevertheless, design optimizations across procedure boundaries have not been fully explored. In this paper, we address the problem of interprocedural register allocation in the context of high level synthesis. In contrast to a recently proposed interprocedural register allocation algorithm, which processes an expensive, global, graph representation of the conflict relation of all values to achieve near optimality, we introduce a new method, called color palette propagation (CPP). The key idea behind our method, is to propagate the use of colors, whose number is significantly smaller than the size of the conflict relation, across different procedures. With a complexity comparable to intraprocedural register allocation, we show that our method can scale to very large C programs. For those benchmarks that can be handled by conventional global methods, our method produced nearly the same number of registers, while providing an average speedup factor of 90.

REFERENCES

• 1: Partitioning a Design in Structural Synthesis, 1987.
• 2: R. Beidas and J. Zhu. Scalable register allocation for high level synthesis. Technical Report TR-01-11-04, Electrical and Computer Engineering, University of Toronto, November 2004.
• 3: R. Camposano , L. F. Saunders , R. M. Tabet, VHDL as Input for High-Level Synthesis, IEEE Design & Test, v.8 n.1, p.43-49, January 1991 [doi>10.1109/54.75662]
• 4: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 5: F. C. Chow, Minimizing register usage penalty at procedure calls, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.85-94, June 20-24, 1988, Atlanta, Georgia, United States
• 6: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 7: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 8: K. Gopinath. Register allocation. The Compiler Design Handbook, September 2002.
• 9: Khushwinder Jasrotia , Jianwen Zhu, Stacked FSMD: A Power Efficient Micro-Architecture for High Level Synthesis, Proceedings of the 5th International Symposium on Quality Electronic Design, p.425-430, March 22-24, 2004
• 10: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 11: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: G.-Y. Lueh. Issues in register allocation by graph coloring. Technical Report CMU-CS-96-171, School of Computer Science, Carnegie Mellon University, November 1996.
• 13: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 14: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
• 16: L. Ramachandran, S. Narayan, F. Vahid, and D. Gajski. Synthesis of functions and procedures in behavioral VHDL. In Proceedings of the European Design Automation Conference, 1993.
• 17: SPEC2000. Standard Performance Evaluation Corporation. http://www.specbench.org/cpu2000/.
• 18: D. L. Springer and D. E. Thomas. Exploiting the special structure of conflict and compatibility graphs in high-level synthesis. In Proceedings of the International Conference on Computer-Aided Design, November 1990.
• 19: Peter A. Steenkiste , John L. Hennessy, A simple interprocedural register allocation algorithm and its effectiveness for LISP, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.1-32, Jan. 1989 [doi>10.1145/59287.59289]
• 20: Frank Vahid, Procedure exlining: a new system-level specification transformation, Proceedings of the conference on European design automation, p.508-513, September 18-22, 1995, Brighton, England
• 21: Ranga Vemuri , Srinivas Katkoori , Meenakshi Kaul , Jay Roy, An efficient register optimization algorithm for high-level synthesis from hierarchical behavioral specifications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.189-216, January 2002 [doi>10.1145/504914.504923]
• 22: Nam-Sung Woo, A global, dynamic register allocation and binding for a data path synthesis system, Proceedings of the 27th ACM/IEEE conference on Design automation, p.505-510, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123384]