On the hardware-software partitioning problem: System modeling and partitioning techniques

ABSTRACT

This paper presents an in-depth study of several system partitioning procedures. It is based on the appropriate formulation of a general system model, being therefore independent of either the particular co-design problem or the specific partitioning procedure. The techniques under study are a knowledge-based system and three classical circuit partitioning algorithms (Simulated Annealing, Kernighan&Lin and Hierarchical Clustering). The former has been entirely proposed by the authors in previous works while the later have been properly extended to deal with system level issues. We will show how the way the problem is solved biases the results obtained, regarding both quality and convergence rate. Consequently it is extremely important to choose the most suitable technique for the particular co-design problem that is being confronted.

REFERENCES

• 1: Barros, E., Rosenstiel, W., and Xiong, X. 1993. HW/SW Partitioning with UNITY. In Handouts of the 2nd International Workshop on HW-SW Codesign.
• 2: Breuker, J. A. and Van de Velde, W., Eds. 1993. The CommonKADS Library. Netherlands Energy Research Foundation ECN, Swedish Institute of Computer Science, Siemens, Univ. of Amsterdam and Free University of Brussels. Tech. rep., ESPRIT Project P5248.
• 3: C. Carreras , J. C. Lopez , M. L. Lopez , L. Sanchez , C. Delgado-Kloos , N. Martinez, A Co-Design Methodology Based on Formal Specification and High-level Estimation, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.28, March 18-20, 1996
• 4: Dick, R. and Jha, N. 1998. Mogac: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Trans. CAD Int. Circ. Syst. 17, 10 (October), 920--935.
• 5: Eles, P., Peng, Z., Kuchcinski, K., and Doboli, A. 1997. System Level Hardware/Software Partitioning based on Simulated Annealing and Tabu Search. Design Automation for Embedded Systems 2, 1 (January), 5--32.
• 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: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 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: Jörg Henkel , Rolf Ernst, An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.273-290, April 2001 [doi>10.1109/92.924041]
• 10: Huang, M. D., Romeo, F., and Sangiovani-Vincentelli, A. 1986. An Efficient General Cooling Schedule for Simulated Annealing. In Proceedings of the Design Automation Conference. 381--384.
• 11: Kalavade, A. and Lee, E. A. 1997. The Extended Partitioning Problem: Hardware/Software Mapping, Scheduling and Implementation-bin Selection. J. Design Automat. Embedded Syst. 2, 2 (March), 125--164.
• 12: Kernighan, B. W. and Lin, S. 1970. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal. 291--307.
• 13: Kirpatrick, S., Gelatt, C., and Vecchi, M. 1983. Optimization by simulated annealing. Science 220, 4598, 671--680.
• 14: M. L. López-Vallejo , J. Grajal , J. C. López, Constraint-driven system partitioning, Proceedings of the conference on Design, automation and test in Europe, p.411-416, March 27-30, 2000, Paris, France [doi>10.1145/343647.343811]
• 15: M. L. López , C. A. Iglesias , J. C. López, A knowledge-based system for hardware-software partitioning, Proceedings of the conference on Design, automation and test in Europe, p.914-915, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 16: López Vallejo, M. and López, J. C. 2001. Multi-way Clustering Techniques for System Level Partitioning. In Proceedings of the 14th IEEE ASIC/SOC Conference. 242--247.
• 17: Marisa Loisa López-Vallejo , Joan Carlos López , Carlos Argel Iglesias, Hardware-Software Partitioning at the Knowledge Level, Applied Intelligence, v.10 n.2-3, p.173-184, March-April 1999 [doi>10.1023/A:1008323819235]
• 18: López Vallejo, M. L. 1999. Hardware-software partitioning methods for the design of heterogeneous systems. Ph.D. thesis, Universidad Politécnica de Madrid.
• 19: Luenberger, D. G. 1984. Linnear and non-Linear Programming. Addison-Wesley.
• 20: Lyndon B. Johnson Space Center. 1993. Clips's Reference Manual. Volume II, Advanced Programming Guide. CLIPS Version 6.0. Lyndon B. Johnson Space Center, Software Tecnology Branch.
• 21: Madsen, J., Grode, J., and Knudsen, P. 1997. Hardware/software partitioning using the lycos system. Hardware/Software Codesign: Principles and Practices (chapter 9). Kluwer Academic Publishers.
• 22: Giovanni De Micheli, Guest Editor's Introduction: Hardware-Software Codesign, IEEE Micro, v.14 n.4, p.8-9, August 1994
• 23: Newell, A. 1982. The knowledge level. Artificial Intelligence. 87--127.
• 24: Ralf Niemann , Peter Marwedel, Hardware/Software Partitioning using Integer Programming, Proceedings of the 1996 European conference on Design and Test, p.473, March 11-14, 1996
• 25: V. Srinivasan , S. Radhakrishnan , R. Vemuri, Hardware/software partitioning with integrated hardware design space exploration, Proceedings of the conference on Design, automation and test in Europe, p.28-35, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 26: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 27: Frank Vahid, Modifying Min-Cut for Hardware and Software Functional Partitioning, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.43, March 24-26, 1997
• 28: Frank Vahid , Daniel D. Gajski, Clustering for improved system-level functional partitioning, Proceedings of the 8th international symposium on System synthesis, p.28-35, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224492]
• 29: 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
• 30: 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]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
Hardware-software co-design, clustering, cost functions, expert systems, fuzzy logic, general optimization procedures, hardware-software partitioning, system modeling