A global, dynamic register allocation and binding for a data path synthesis system

ABSTRACT

We developed a new algorithm for efficient register allocation and binding used in data path synthesis. Our algorithm determines both the number of registers and the mapping from variables to registers simultaneously during data path allocation so that the cost, i.e., area, of the registers and connections to/from the registers can be minimized. The algorithm selects the “best” register for each input and/or output variable of operations. This register allocation/binding algorithm is used with a data path allocation algorithm that exploits trade-off among all kinds of hardware elements. We present experimental results of our algorithm.

REFERENCES

• HiTh83: Charles Y. Hitchcock, III , Donald E. Thomas, A method of automatic data path synthesis, Proceedings of the 20th conference on Design automation, p.484-489, June 27-29, 1983, Miami Beach, Florida, United States
• Hitc83: C. Hitchcock, "Automated Synthesis of Data Paths," SRC TR No. 006, CMU, Ja. 1983.
• KuPa87: 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]
• McFa86: Michael C. McFarland, Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.474-480, July 1986, Las Vegas, Nevada, United States
• PaKn86: 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
• Pang88: 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
• PaPi86: Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
• PoRa89: M. Potkonjack , J. Rabaey, A scheduling and resource allocation algorithm for hierarchical signal flow graphs, Proceedings of the 26th ACM/IEEE conference on Design automation, p.7-12, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74385]
• TsSi86: C-J Tseng, D. Siewiorek, "Automated Synthesis of Data Paths in Digital Systems," IEEE Trans. on CAD, V.CAD-5, N.3, pp. 379-395, July 1986.
• TsWe88: Chia-Jeng Tseng , Ruey-Sing Wei , Steven G. Rothweiler , Michael M. Tong , Ajoy K. Bose, Bridge: a versatile behavioral synthesis system, Proceedings of the 25th ACM/IEEE conference on Design automation, p.415-420, June 12-15, 1988, Atlantic City, New Jersey, United States
• WoSh89: N.-S. Woo , H. Shin, A technology-adaptive allocation of functional units and connections, Proceedings of the 26th ACM/IEEE conference on Design automation, p.602-605, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74485]
• Woo90a: N-S Woo, "SAM: A Dal:a Path Allocation System," Proc. of 1990 Custom Integrated Circuits Conference, May 1990.
• Woo90b: N-S Woo, "A Global, Dynamic Register Allocation and Binding for a Data Path Synthesis System," Technical Memo, AT&T Bell Lab., March 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

General Terms:
Algorithms, Design