Partitioning sequential programs for CAD using a three-step approach

ABSTRACT

Many computer-aided design problems involve solutions that require the partitioning of a large sequential program written in a language such as C or VHDL. Such partitioning can improve design metrics such as performance, power, energy, size, input/output lines, and even CAD tool run-time and memory requirements, by partitioning among hardware modules, hardware and software processors, or even among time-slices in reconfigurable computing devices. Previous partitioning approaches typically preselect the granularity at which the program is partitioned. In this article, we define three distinct partitioning steps: procedure determination, preclustering, and N-way partitioning, with the first two steps focusing on granularity selection. Using three steps instead of one can provide for a more thorough design space exploration and for faster partitioning. We emphasize the first two steps in this article since they represent the most novel aspects. We illustrate the approach on an example, provide results of several experiments, and point to the need for future research that more fully automates the three-step approach.

REFERENCES

• 1: Matthew Arnold , Stephen Fink , Vivek Sarkar , Peter F. Sweeney, A comparative study of static and profile-based heuristics for inlining, ACM SIGPLAN Notices, v.35 n.7, p.52-64, July 2000
• 2: A. Balboni , W. Fornaciari , D. Sciuto, Partitioning and Exploration Strategies in the TOSCA Co-Design Flow, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.62, March 18-20, 1996
• 3: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 4: Cooper, K., Hall, M., and Kennedy, K. 1993. A methodology for procedure cloning. Comput. Lang. 19, 2.
• 5: Petru Eles , Zebo Peng1 , Krzysztof Kuchcinski , Alexa Doboli, Hardware/Software Partitioning with Iterative Improvement Heuristics, Proceedings of the 9th international symposium on System synthesis, p.71, November 06-08, 1996
• 6: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 7: Gajski, D. D., Vahid, F., Narayan, S., and Gong, J. 1998. SpecSyn: An environment supporting the specify-explore-refine paradigm for hardware/software system design. IEEE Trans. VLSI Syst. 6, 1, 84--100.
• 8: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 9: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 10: Jörg Henkel, A low power hardware/software partitioning approach for core-based embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.122-127, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309896]
• 11: Jörg Henkel , Rolf Ernst, A hardware/software partitioner using a dynamically determined granularity, Proceedings of the 34th annual conference on Design automation, p.691-696, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266323]
• 12: Enoch Hwang , Frank Vahid , Yu-Chin Hsu, FSMD functional partitioning for low power, Proceedings of the conference on Design, automation and test in Europe, p.7-es, January 1999, Munich, Germany [doi>10.1145/307418.307432]
• 13: Asawaree Kalavade , Edward A. Lee, A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 14: Peter Voigt Knudsen , Jan Madsen, PACE: A Dynamic Programming Algorithm for Hardware/Software Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.85, March 18-20, 1996
• 15: Lagnese, E. and Thomas, D. 1991. Architectural partitioning for system level synthesis of integrated circuits. IEEE Trans. Comput-Aid. Des. 10 (July), 847--860.
• 16: Erik Ruf , Daniel Weise, Using types to avoid redundant specialization, ACM SIGPLAN Notices, v.26 n.9, p.321-333, Sept. 1991
• 17: Greg Stitt , Frank Vahid, Energy Advantages of Microprocessor Platforms with On-Chip Configurable Logic, IEEE Design & Test, v.19 n.6, p.36-43, November 2002 [doi>10.1109/MDT.2002.1047742]
• 18: Frank Vahid, Procedure exlining: a transformation for improved system and behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.84-89, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224506]
• 19: 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]
• 20: Vahid, F. 1999b. Techniques for minimizing and balancing i/o during functional partitioning. IEEE Trans. CAD 18, 1 (Jan.), 69--75.
• 21: Frank Vahid , Thuy Dm Le , Yu-Chin Hsu, Functional partitioning improvements over structural partitioning for packaging constraints and synthesis: tool performance, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.2, p.181-208, April 1998 [doi>10.1145/290833.290841]
• 22: Wan, M., Ichikawa, Y., Lidsky, D., and Rabaey, J. 1998. An Energy conscious methodology for early design exploration of heterogeneous DSP's. In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC), 111--117.
• 23: Wayne H. Wolf, An architectural co-synthesis algorithm for distributed, embedded computing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.2, p.218-229, June 1997 [doi>10.1109/92.585225]
• 24: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]

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

General Terms:
Design, Languages, Performance

Keywords:
Partitioning, behavioral partitioning, functional partitioning, hardware/software partitioning, system level partitioning