Complexity-constrainted partitioning of sequential programs for efficient behavioral synthesis

ABSTRACT

This paper proposes a behavioral level partitioning method for efficient behavioral synthesis from a large sequential program consisting of a set of functions. Our method optimally determines functions to be inlined into the main module and ones to be synthesized into sub modules in such a way that the overall datapath is minimized while the complexity of individual modules is lower than a certain level. The partitioning problem is formulated as an integer programming problem. Experimental results show the effectiveness of the proposed method.

REFERENCES

• 1: 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
• 2: Frank Vahid, Partitioning sequential programs for CAD using a three-step approach, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.413-429, July 2002 [doi>10.1145/567270.567273]
• 3: Sumit Gupta , Rajesh Kumar Gupta , Nikil D. Dutt , Alexandru Nicolau, Coordinated parallelizing compiler optimizations and high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.441-470, October 2004 [doi>10.1145/1027084.1027087]
• 4: M. Nishimura, K. Nishiguchi, N. Ishiura, H. Kanbara, H. Tomiyama, Y. Takatsukasa, and M. Kotani, "High-Level Synthesis of Variable Accesses and Function Calls in Software Compatible Hardware Synthesizer CCAP," SASIMI, 2006.
• 5: Yuko Hara , Hiroyuki Tomiyama , Shinya Honda , Hiroaki Takada, Function Call Optimization in Behavioral Synthesis, Proceedings of the 9th EUROMICRO Conference on Digital System Design, p.522-529, August 30-September 01, 2006 [doi>10.1109/DSD.2006.56]
• 6: Frank Vahid, Procedure cloning: a transformation for improved system-level functional partitioning, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.1, p.70-96, Jan. 1999 [doi>10.1145/298865.298871]
• 7: F. Vahid, "Techniques for Minimizing and Balancing I/O during Functional Partitioning," IEEE Trans. CAD, vol. 18, no. 1, Jan. 1999.
• 8: Gagan Raj Gupta , Madhur Gupta , Preeti Ranjan Panda, Rapid estimation of control delay from high-level specifications, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147029]
• 9: Y Explorations, Inc., http://www.yxi.com/.
• 10: Xilinx, http://www.xilinx.com/.

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: Optimization

General Terms:
Design

Keywords:
behavioral synthesis, function calls, integer programming problem