An efficient register optimization algorithm for high-level synthesis from hierarchical behavioral specifications

ABSTRACT

We address the problem of register optimization that arises during high-level synthesis from modular hierarchical behavioral specifications. Register optimization is the process of grouping carriers such that each group can be safely allocated to a hardware register. Global register optimization by inline expansion involves flattening the module hierarchy and using a heuristic register optimization procedure on the flattened description. Although inline expansion yields a near-optimal number of registers, it is very time consuming due to the large number of carrier compatibility relationships that must be considered. We present an efficient register optimization algorithm that achieves nearly the same effect of inline expansion without actually inline expanding. The distinguishing feature of the proposed algorithm is that it employs a hierarchical optimization phase which effectively exploits the properties of the module call graph and information gathered during local carrier lifecycle analysis of each module. Experimental results on a number of benchmarks show that the proposed algorithm produces nearly the same number of registers as inline expansion based global optimization and is faster by a factor of 7.0.

REFERENCES

• 1: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 2: Raul Camposano , Wayne H. Wolf, High-Level VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1991
• 3: CULLYER, W. J. 1988. Implementing safety critical systems: The VIPER microprocessor, In G. Birtwistle and P. A. Subrahmanyam, (Eds.), VLSI Specification, Verification, and Synthesis, Kluwer Academic, Hingham, Mass.
• 4: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 5: DEVADAS, S. AND NEWTON, A. R. 1989. Algorithms for hardware allocation in data path synthesis. IEEE Trans. Comput.-Aided Des. Circ. Syst. 8, 7 (June), 768-781.
• 6: R. Dutta , J. Roy , R. Vemuri, Distributed design-space exploration for high-level synthesis systems, Proceedings of the 29th ACM/IEEE conference on Design automation, p.644-650, June 08-12, 1992, Anaheim, California, United States
• 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: GEBOTYS, C. H. AND ELMASRY, M. I. 1990. A global optimization approach for architectural synthesis. ITCAD, 258-261.
• 9: John Granacki , David Knapp , Alice Parker, The ADAM advanced design automation system: overview, planner and natural language interface, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.727-730, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317970]
• 10: HAFER, L. J. AND PARKER, A. C. 1982. Automated synthesis of digital hardware. IEEE Comput. C-31, 2 (Feb.), 93-109.
• 11: HAFER, L. J. AND PARKER, A. C. 1983. A Formal method for the specification, analysis and design of register-transfer level digital logic. ITCAD 2, 4-18.
• 12: HAROUN, B. S. AND ELMASRY, M. I. 1988. Automatic synthesis of a multi-bus architecture for DSP. In Proceedings of the International Conference on Computer-Aided Design, 44-47.
• 13: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• 14: Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 15: David C. Ku , Giovanni De Micheli, High level synthesis of ASICs under timing and synchronization constraints, Kluwer Academic Publishers, Norwell, MA, 1992
• 16: 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]
• 17: Feipei Lai , Yung-Kuang Chao , Chia-Jung Hsieh, The complementary relationship of interprocedural register allocation and inlining, International Journal of Parallel Programming, v.22 n.4, p.409-434, Aug. 1994 [doi>10.1007/BF02577739]
• 18: Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
• 19: U. Lauther , Peter Duzy , Petra Michel, The Synthesis Approach to Digital System Design, Kluwer Academic Publishers, Norwell, MA, 1992
• 20: Barry M. Pangre, Splicer: a heuristic approach to connectivity binding, Proceedings of the 25th ACM/IEEE conference on Design automation, p.536-541, June 12-15, 1988, Atlantic City, New Jersey, United States
• 21: 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
• 22: Daniel P. Siewiorek , G. Bell , A. C. Newell, Computer Structures: Principles and Examples, McGraw-Hill, Inc., New York, NY, 1982
• 23: SOUTHARD, J. R. 1983. MacPitts: An approach to silicon compilation. IEEE Computer, 74-82.
• 24: SPRINGER, D. L. AND THOMAS, D. E. 1990. Exploiting the special structure of conflict and compatibility graphs in high-level synthesis. In Proceedings of the International Conference on Computer- Aided Design, 254-257.
• 25: STOK, L. AND BORN, R. V. D. 1988. EASY: Multiprocessor architecture optimization. In Proceedings of the International Workshop on Logic and Architecture Synthesis for Silicon Compilers, 313-328.
• 26: THOMAS, D. E., HITCHCOCK III, C. Y., KOWALSKI, T. J., RAJAN, J. V., AND WALKER, A. 1983. Automated data path synthesis. IEEE Trans. Comput. 59-70.
• 27: Donald E. Thomas , Elizabeth D. Lagnese , John A. Nestor , Jayanth V. Rajan , Robert L. Blackburn , Robert A. Walker, Algorithmic and Register-Transfer Level Synthesis: The System Architect's Workbench, Kluwer Academic Publishers, Norwell, MA, 1989
• 28: Chia-Jeng Tseng , Daniel P. Siewiorek, Facet: A procedure for the automated synthesis of digital systems, Proceedings of the 20th conference on Design automation, p.490-496, June 27-29, 1983, Miami Beach, Florida, United States
• 29: WILSON, T. C., HALLEY, B., DEADMAN, R., AND BANERJI, D. K. 1992. Optimal register allocation and binding in behavioral synthesis. In Proceedings of the Canadian Conference on VLSI.
• 30: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Hardware description languages; Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
Behavioral synthesis, hardware description languages, hierarchical specifications, high-level synthesis, lifecycle analysis, register optimization