Procedure cloning: a transformation for improved system-level functional partitioning

ABSTRACT

Functional partitioning assigns the functions of a system's program-like specification among system components, such as standard-software and custom-hardware processors. We introduce a new transformation, called procedure cloning, that significantly improves functional partitioning results. The transformation creates a clone of a procedure for sole use by a particular procedure caller, so the clone can be assigned to the caller's processor, which in turn improves performance through reduced communication. Heuristics are used to prevent the exponential size increase that could occur if cloning were done indiscriminately. We introduce a variety of cloning heuristics, highlight experiments demonstrating the improvements obtained using cloning, and compare the various cloning heuristics.

REFERENCES

• 1: S. Antoniazzi , A. Balboni , W. Fornaciari , D. Sciuto, A methodology for control-dominated systems codesign, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 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: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• 4: CHEN, Y., HSU, Y., AND KING, C. 1994. MULTIPAR: Behavioral partition for synthesizing multiprocessor architectures. IEEE Trans. Very Large Scale Integr. Syst. 2, 1 (Mar.), 21-32.
• 5: COOPER, K., HALL, M., AND KENNEDY, K. 1993. A methodology for procedure cloning. Comput. Lang. 19, 2.
• 6: ELES, P., PENG, Z., AND DOBOLI, A. 1992. VHDL system-level specification and partitioning in a hardware/software co-synthesis environment. In Proceedings of the International Workshop on Hardware-Software Co-Design. 49-55.
• 7: 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
• 8: 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]
• 9: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 10: GAJSKI, 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. Very Large Scale Integr. Syst. 6, 1, 84-100.
• 11: 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]
• 12: GUPTA, R. AND DEMICHELI, G. 1990. Partitioning of functional models of synchronous digital systems. In Proceedings of the International Conference on Computer-Aided Design. 216-219.
• 13: 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]
• 14: HWANG, L. AND GAMAL, A. E. 1995. Min-cut replication in partitioned networks. IEEE Trans. CAD 14 (Jan.), 96-106.
• 15: Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240535]
• 16: 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
• 17: KERNIGHAN, B. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (Feb.).
• 18: 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
• 19: Kayhan Kükçakar , Alice C. Parker, CHOP: A constraint-driven system-level partitioner, Proceedings of the 28th conference on ACM/IEEE design automation, p.514-519, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127724]
• 20: E. D. Lagnese , D. E. Thomas, Architectural partitioning for system level design, Proceedings of the 26th ACM/IEEE conference on Design automation, p.62-67, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74394]
• 21: LAGNESE, E. AND THOMAS, D. 1991. Architectural partitioning for system level synthesis of integrated circuits. IEEE Trans. Comput.-Aided Des. 10 (July), 847-860.
• 22: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 23: LIU, L., Kuo, M., Hu, T., AND CHENG, C. 1995. Performance-driven partitioning using a replication graph approach. In Proceedings of the European Conference EURO-DAC '95 with EURO-VHDL '95 on Design Automation (Brighton, UK, Sept. 18-22), G. Musgrave, Ed. IEEE Computer Society Press, Los Alamitos, CA, 206-210.
• 24: Alex Orailoglu , Daniel D. Gajski, Flow graph representation, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.503-509, July 1986, Las Vegas, Nevada, United States
• 25: Erik Ruf , Daniel Weise, Using types to avoid redundant specialization, ACM SIGPLAN Notices, v.26 n.9, p.321-333, Sept. 1991
• 26: Donald E. Thomas , Jay K. Adams , Herman Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test, v.10 n.3, p.6-15, July 1993 [doi>10.1109/54.232468]
• 27: Frank Vahid, I/O and performance tradeoffs with the FunctionBus during multi-FPGA partitioning, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.27-34, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258309]
• 28: Vahid , Le , Hsu, A Comparison of Functional and Structural Partitioning, Proceedings of the 9th international symposium on System synthesis, p.121, November 06-08, 1996
• 29: Frank Vahid , Thuy DM Le, Towards a Model for Hardware and Software Functional Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.116, March 18-20, 1996
• 30: Frank Vahid , Daniel D. Gajski, Incremental hardware estimation during hardware/software functional partitioning, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.459-464, Sept. 1995 [doi>10.1109/92.407006]
• 31: 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]
• 32: F. Vahid , D. D. Gajski, SLIF: a specification-level intermediate format for system design, Proceedings of the 1995 European conference on Design and Test, p.185, March 06-09, 1995
• 33: WOLF, W. 1994. Hardware-software co-design of embedded systems. Proc. IEEE 82, 7 (July), 967-989.
• 34: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• 35: Hannah Honghua Yang , D. F. Wong, New algorithms for min-cut replication in partitioned circuits, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.216-222, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis; Hardware description languages; Optimization

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design

Keywords:
behavioral synthesis, embedded systems, functional partitioning, hardware/software codesign, replication, system-level design, system-on-a-chip, transformations