Algorithmic aspects of hardware/software partitioning

ABSTRACT

One of the most crucial steps in the design of embedded systems is hardware/software partitioning, that is, deciding which components of the system should be implemented in hardware and which ones in software. Most formulations of the hardware/software partitioning problem are NP-hard, so the majority of research efforts on hardware/software partitioning has focused on developing efficient heuristics.This article considers the combinatorial structure behind hardware/software partitioning. Two similar versions of the partitioning problem are defined, one of which turns out to be NP-hard, whereas the other one can be solved in polynomial time. This helps in understanding the real cause of complexity in hardware/software partitioning. Moreover, the polynomial-time algorithm serves as the basis for a highly efficient novel heuristic for the NP-hard version of the problem. Unlike general-purpose heuristics such as genetic algorithms or simulated annealing, this heuristic makes use of problem-specific knowledge, and can thus find high-quality solutions rapidly. Moreover, it has the unique characteristic that it also calculates lower bounds on the optimum solution. It is demonstrated on several benchmarks and also large random examples that the new algorithm clearly outperforms other heuristics that are generally applied to hardware/software partitioning.

REFERENCES

• 1: Tarek F. Abdelzaher , Kang G. Shin, Period-Based Load Partitioning and Assignment for Large Real-Time Applications, IEEE Transactions on Computers, v.49 n.1, p.81-87, January 2000 [doi>10.1109/12.822566]
• 2: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: Arató, P., Juhász, S., Mann, Z. Á., Orbán, A., and Papp, D. 2003a. Hardware/software partitioning in embedded system design. In Proceedings of the IEEE International Symposium on Intelligent Signal Processing.
• 4: Arató, P., Mann, Z. Á., and Orbán, A. 2003b. Hardware-software co-design for Kohonen's self-organizing map. In Proceedings of the IEEE 7th International Conference on Intelligent Engineering Systems.
• 5: Barros, E., Rosenstiel, W., and Xiong, X. 1993. Hardware/software partitioning with UNITY. In Proceedings of the 2nd International Workshop on Hardware-Software Codesign.
• 6: Nguyen Ngoc Bình , Masaharu Imai , Akichika Shiomi , Nobuyuki Hikichi, A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts, Proceedings of the 33rd annual conference on Design automation, p.527-532, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240618]
• 7: Karam S. Chatha , Ranga Vemuri, MAGELLAN: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs, Proceedings of the ninth international symposium on Hardware/software codesign, p.42-47, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371671]
• 8: Cherkassky, B. V. and Goldberg, A. V. 1997. On implementing push-relabel method for the maximum flow problem. Algorithmica 19, 4, 390--410.
• 9: Dasdan, A. and Aykanat, C. 1997. Two novel multiway circuit partitioning algorithms using relaxed locking. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 16, 2 (Feb.), 169--177.
• 10: Dick, R. P. and Jha, N. K. 1998. MOGAC: A multiobjective genetic algorithm for hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 10, 920--935.
• 11: P. Eles , K. Kuchcinski , Z. Peng , A. Doboli, Hardware/software partitioning of VHDL system specifications, Proceedings of the conference on European design automation, p.434-439, September 1996, Geneva, Switzerland
• 12: Eles, P., Peng, Z., Kuchcinski, K., and Doboli, A. 1997. System level hardware/software partitioning based on simulated annealing and tabu search. Des. Automat. Embedd. Syst. 2, 1 (Jan.), 5--32.
• 13: 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]
• 14: 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
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 17: J. Grode , P. V. Knudsen , J. Madsen, Hardware resource allocation for hardware/software partitioning in the LYCOS system, Proceedings of the conference on Design, automation and test in Europe, p.22-27, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 18: 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]
• 19: Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 1997. MiBench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization.
• 20: 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]
• 21: Asawaree Prabhakar Kalavade , Edward A. Lee, System-level codesign of mixed hardware-software systems, 1995
• 22: Kalavade, A. and Lee, E. A. 1997. The extended partitioning problem: Hardware/Software mapping, scheduling and implementation-bin selection. Des. Automat. Embedd. Syst. 2, 2, 125--164.
• 23: Kalavade, A. and Subrahmanyam, P. A. 1998. Hardware/software partitioning for multifunction systems. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 17, 9 (Sept.), 819--837.
• 24: Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Techn. J. 49, 2, 291--307.
• 25: 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]
• 26: 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
• 27: Marisa López-Vallejo , Juan Carlos López, On the hardware-software partitioning problem: System modeling and partitioning techniques, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.269-297, July 2003 [doi>10.1145/785411.785412]
• 28: Madsen, J., Grode, J., Knudsen, P. V., Petersen, M. E., and Haxthausen, A. 1997. LYCOS: The Lyngby co-synthesis system. Des. Automat. Embedd. Syst. 2, 2, 195--236.
• 29: Mann, Z. Á. and Orbán, A. 2003. Optimization problems in system-level synthesis. In Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications.
• 30: Mei, B., Schaumont, P., and Vernalde, S. 2000. A hardware/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. In Proceedings of ProRISC.
• 31: Ralf Niemann, Hardware/Software CO-Design for Data Flow Dominated Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 32: Niemann, R. and Marwedel, P. 1997. An algorithm for hardware/software partitioning using mixed integer linear programming. Des. Automat. Embedd. Syst. Special Issue: Partitioning Methods for Embedded Systems 2, 165--193.
• 33: O'Nils, M., Jantsch, A., Hemani, A., and Tenhunen, H. 1995. Interactive hardware-software partitioning and memory allocation based on data transfer profiling. In Proceedings of the International Conference on Recent Advances in Mechatronics.
• 34: Qin, S. and He, J. 2000. An algebraic approach to hardware/software partitioning. Tech. rep. 206, UNU/IIST.
• 35: Garrison Greenwood, Preference-Driven Hierarchical Hardware/Software Partitioning, Proceedings of the 1999 IEEE International Conference on Computer Design, p.652, October 10-13, 1999
• 36: Youssef G. Saab, A Fast and Robust Network Bisection Algorithm, IEEE Transactions on Computers, v.44 n.7, p.903-913, July 1995 [doi>10.1109/12.392848]
• 37: 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
• 38: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 39: Stone, H. 1977. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Softw. Eng. 3, 1 (Jan.), 85--93.
• 40: 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
• 41: 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]
• 42: 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]
• 43: Vahid, F. and Le, T. D. 1997. Extending the Kernighan/Lin heuristic for hardware and software functional partitioning. Des. Automat. Embedd. Syst. 2, 237--261.
• 44: 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)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design

Keywords:
Hardware/software partitioning, graph algorithms, graph bipartitioning, hardware/software codesign, optimization