Clustering for improved system-level functional partitioning

ABSTRACT

Abstract: Partitioning of system functionality for implementation among multiple system components, such as among hardware and software components, is becoming an increasingly important topic. Various heuristics can accomplish such partitioning. We demonstrate that clustering can be used to merge pieces of functionality before applying other heuristics, resulting in reduced runtimes with little or no loss in quality, and often with improvements in quality. In addition, we show that clustering, when used for N-way partitioning, fills the gap between fast heuristics and highly-optimizing heuristics.

REFERENCES

• 1: Peter M. Athanas , Harvey F. Silverman, Processor reconfiguration through instruction-set metamorphosis, Computer, v.26 n.3, p.11-18, March 1993 [doi>10.1109/2.204677]
• 2: R. Camposano and R. Brayton, "Partitioning before logic synthesis," in Proceedings of the International Conference on Computer-Aided Design, 1987.
• 3: M. McFarland and T. Kowalski, "Incorporating bottomup design into hardware synthesis," IEEE Transactions on Computer-Aided Design, pp. 938-950, September 1990.
• 4: E. Lagnese and D. Thomas, "Architectural partitioning for system level synthesis of integrated circuits," IEEE Transactions on Computer-Aided Design, July 1991.
• 5: 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
• 6: R. Gupta and G. DeMicheli, "Partitioning of functional models of synchronous digital systems," in Proceedings of the International Conference on Computer-Aided Design, pp. 216-219, 1990.
• 7: 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]
• 8: Z. Peng and K. Kuchcinski, 'tAn algorithm for partitioning of application specific systems," in Proceedings of the European Conference on Design Automation (EDAC), pp. 316-321, 1993.
• 9: C. Gebotys, 'tAn optimization approach to the synthesis of multichip architectures," IEEE Transactions on Very Large Scale Integration Systems, vol. 2, no. 1, pp. 11-20, 1994.
• 10: Y. Chert, Y. Hsu, and C. King, "MULTIPAR: Behavioral partition for synthesizing multiprocessor architectures," IEEE Transactions on Very Large Scale Integration Systerns, vol. 2, pp. 21-32, March 1994.
• 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: 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]
• 13: T. Ismail, K. O'Brien, and A. Jerraya, "Interactive systemlevel partitioning with Partif," in Proceedings of the European Conference on Design Automation (EDAC), 1994.
• 14: 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
• 15: F. Vahid , D. D. Gajski, Specification partitioning for system design, Proceedings of the 29th ACM/IEEE conference on Design automation, p.219-224, June 08-12, 1992, Anaheim, California, United States
• 16: 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]
• 17: Pravil Gupta , Chih-Tung Chen , J. C. DeSouza-Batista , Alice C. Parker, Experience with image compression chip design using unified system construction tools, Proceedings of the 31st annual conference on Design automation, p.250-256, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196367]
• 18: Petru Eles , Zebo Peng , Alexa Doboli, VHDL system-level specification and partitioning in a hardware/software co-synthesis environment, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 19: 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]
• 20: Frank Vahid , Daniel D. Gajski, Closeness metrics for system-level functional partitioning, Proceedings of the conference on European design automation, p.328-333, September 18-22, 1995, Brighton, England
• 21: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

          Nouns: VHDL

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
N-way partitioning, clustering, fast heuristics, formal specification, hardware components, highly-optimizing heuristics, logic partitioning, merging, multiple system components, quality, reduced runtimes, software components, system-level functional partitioning