Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

Zoltán Mann; András Orbán; Viktor Farkas

doi:10.2478/v10006-007-0022-3

Abstract

In recent years, several heuristics have been proposed for the hardware/software partitioning problem. One of the most promising directions is the adaptation of the Kernighan-Lin algorithm. The Kernighan-Lin heuristic was originally developed for circuit partitioning, but it has been adapted to other domains as well. Moreover, numerous improvements have been suggested so that now several variants of the original algorithm exist. The aim of this paper is to systematically evaluate the possibilities of applying the Kernighan-Lin heuristic to hardware/software partitioning. It is investigated in detail which versions of the heuristic work well in this context. Since hardware/software partitioning also has several formulations, it is also discussed how the problem formulation affects the applicability of this heuristic. Furthermore, possibilities of efficient implementations of the algorithm—by using appropriate data structures—are also presented. These investigations are accompanied by numerous empirical test results.

References

Abdelzaher T.F. and Shin K.G. (2000): Period-based load partitioning and assignment for large real-time applications. — IEEE Trans. Comput., Vol. 49, No. 1, pp. 81-87.10.1109/12.822566
Search in Google Scholar
Alpert C.J. and Kahng A.B. (1995): Recent developments in netlist partitioning: A survey.—VLSI J., Vol. 19, No. 1-2, pp. 1-81.
Search in Google Scholar
Arató P., Juhász S., Mann Z.Á., Orbán A. and Papp D. (2003a): Hardware/software partitioning in embedded system design. — Proc. IEEE Int. Symp. Intelligent Signal Processing, Budapest, Hungary, pp. 197-202.
Search in Google Scholar
Arató P., Mann Z.Á. and Orbán A. (2003b): Hardware-software co-design for Kohonen's self-organizing map. — Proc. IEEE 7th Int. Conf. Intelligent Engineering Systems, Luxor, Egypt, pp. 173-178.
Search in Google Scholar
Arató P., Mann Z.Á. and Orbán A. (2005a): Algorithmic aspects of hardware/software partitioning. — ACM Trans. Design Autom. Electron. Syst., Vol. 10, No. 1, pp. 136-156.10.1145/1044111.1044119
Search in Google Scholar
Arató P., Mann Z.Á. and Orbán A. (2005b): Time-constrained scheduling of large pipelined datapaths. — J. Syst. Arch. Vol. 51, No. 12, pp. 665-687.10.1016/j.sysarc.2005.02.001
Search in Google Scholar
Arató P., Mann Z.Á. and Orbán A. (2007): Finding optimal hardware/software partitions. — Formal Meth. Syst. Design, (submitted).
Search in Google Scholar
Barros E., Rosenstiel W. and Xiong X. (1993): Hardware/software partitioning with UNITY. — Proc. 2nd Int. Workshop Hardware-Software Codesign, Cambridge, USA.
Search in Google Scholar
Binh N.N., Imai M., Shiomi A. and Hikichi N. (1996): A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts. — Proc. 33rd Design Automation Conference, Las Vegas, USA, pp. 527-532.10.1145/240518.240618
Search in Google Scholar
Chatha K.S. and Vemuri R. (2001): MAGELLAN: Multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs. — Proc. 9-th Int. Symp. Hardware/Software Codesign, Copenhagen, Denmark, pp. 42-47.10.1145/371636.371671
Search in Google Scholar
Cormen Th.H., Leiserson Ch.E., Rivest R.L. and Stein C. (2001): Introduction to Algorithms, 2nd Ed. — Cambridge: MIT Press.
Search in Google Scholar
Dasdan A. and Aykanat C. (1997): Two novel multiway circuit partitioning algorithms using relaxed locking. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 16, No. 2, pp. 169-177.10.1109/43.573831
Search in Google Scholar
de Berg M., Schwarzkopf O., van Kreveld M. and Overmars M. (2000): Computational Geometry: Algorithms and Applications, 2nd Ed. — Berlin: Springer.10.1007/978-3-662-04245-8
Search in Google Scholar
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. Aided Des. Integ. Circ. Syst., Vol. 17, No. 10, pp. 920-935.10.1109/43.728914
Search in Google Scholar
Eles P., Peng Z., Kuchcinski K. and Doboli A. (1996): Hardware/software partitioning of VHDL system specifications. — Proc. European Design Automation Conference, Geneva, Switzerland, pp. 434-439.10.1109/EURDAC.1996.558240
Search in Google Scholar
Eles P., Peng Z., Kuchcinski K. and Doboli A. (1997): System level hardware/software partitioning based on simulated annealing and tabu search. — Des. Autom. Emb. Syst., Vol. 2, No. 1, pp. 5-32.10.1023/A:1008857008151
Search in Google Scholar
Ernst R., Henkel J. and Benner T. (1993): Hardware/software cosynthesis for microcontrollers. — IEEE Des. Test Comput., Vol. 10, No. 4, pp. 64-75.10.1109/54.245964
Search in Google Scholar
Fiduccia C.M. and Mattheyses R.M. (1982): A linear-time heuristic for improving network partitions. — Proc. 19th Design Automation Conference, Piscataway, USA, pp. 175-181.
Search in Google Scholar
Grode J., Knudsen P.V. and Madsen J. (1998): Hardware resource allocation for hardware/software partitioning in the LYCOS system. — Proc. Conf. Design Automation and Test in Europe, DATE, Paris, France, pp. 22-27.10.1109/DATE.1998.655832
Search in Google Scholar
Gupta R.K. and de Micheli G. (1993): Hardware-software cosynthesis for digital systems. — IEEE Des. Test Comput., Vol. 10, No. 3, pp. 29-41.10.1109/54.232470
Search in Google Scholar
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. — Proc. IEEE 4th Ann. Workshop Workload Characterization, Austin, USA, pp. 3-14.
Search in Google Scholar
Hagen L., Huang J.H. and Kahng A.B. (1997): On implementation choices for iterative improvement partitioning algorithms. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 16, No. 10, pp. 1199-1205.10.1109/43.662682
Search in Google Scholar
Henkel J. and Ernst R. (2001): An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. — IEEE Trans. VLSI Syst., Vol. 9, No. 2, pp. 273-289.10.1109/92.924041
Search in Google Scholar
Hoffmann A.G. (1994): The dynamic locking heuristic - a new graph partitioning algorithm. — Proc. IEEE Int. Symp. Circuits and Systems, London, UK, pp. 173-176.10.1109/ISCAS.1994.408783
Search in Google Scholar
Kalavade A. (1995): System-level codesign of mixed hardware-software systems.—Ph.D. thesis, University of California, Berkeley, CA, USA.
Search in Google Scholar
Kalavade A. and Lee E.A. (1997): The extended partitioning problem: hardware/software mapping, scheduling and implementation-bin selection. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 125-164.10.1023/A:1008872518365
Search in Google Scholar
Kalavade A. and Subrahmanyam P.A. (1998): Hardware/software partitioning for multifunction systems. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 17, No. 9, pp. 819-837.10.1109/43.720318
Search in Google Scholar
Kernighan B.W. and Lin S. (1970): An efficient heuristic procedure for partitioning graphs. — Bell Syst. Techn. J., Vol. 49, No. 2, pp. 291-307.10.1002/j.1538-7305.1970.tb01770.x
Search in Google Scholar
Krishnamurthy B. (1984): An improved min-cut algorithm for partitioning VLSI networks. — IEEE Trans. Comput., Vol. 33, No. 5, pp. 438-446.10.1109/TC.1984.1676460
Search in Google Scholar
Lopez-Vallejo M., Grajal J. and Lopez J.C. (2000): Constraint-driven system partitioning. — Proc. Design, Automation and Test in Europe Conference and Exhibition, Paris, France, pp. 411-416.10.1145/343647.343811
Search in Google Scholar
Lopez-Vallejo M. and Lopez J.C. (1998): A knowledge based system for hardware-software partitioning. — Proc. Design Automation and Test in Europe, DATE, Paris, France, pp. 914-915.10.1109/DATE.1998.655967
Search in Google Scholar
Lopez-Vallejo M. and Lopez J.C. (2003): On the hardware-software partitioning problem: system modeling and partitioning techniques. — ACM Trans. Des. Autom. Electron. Syst., Vol. 8, No. 3, pp. 269-297.10.1145/785411.785412
Search in Google Scholar
Madsen J., Grode J., Knudsen P.V., Petersen M.E. and Haxthausen A. (1997): LYCOS: The Lyngby co-synthesis system. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 195-236.10.1023/A:1008884219274
Search in Google Scholar
Mann Z.Á. and Orbán A. (2003): Optimization problems in system-level synthesis. — Proc. 3rd Hungarian-Japanese Symp. Discrete Mathematics and Its Applications, Tokyo, Japan, pp. 222-231.
Search in Google Scholar
Mei B., Schaumont P. and Vernalde S. (2000): A hardware/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. — Proc. 11-th ProRISC Workshop Circuits, Systems and Signal Processing, Veldhoven, Netherlands, pp. 405-411.
Search in Google Scholar
Niemann R. (1998): Hardware/Software Co-Design for Data Flow Dominated Embedded Systems. — Norwell: Kluwer.10.1007/978-1-4757-2803-3
Search in Google Scholar
Niemann R. and Marwedel P. (1997): An algorithm for hardware/software partitioning using mixed integer linear programming. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 165-193.10.1023/A:1008832202436
Search in Google Scholar
O'Nils M., Jantsch A., Hemani A. and Tenhunen H. (1995): Interactive hardware-software partitioning and memory allocation based on data transfer profiling. — Proc. Int. Conf. Recent Advances in Mechatronics, Istanbul, Turkey, pp. 447-452.
Search in Google Scholar
Qin S. and He J. (2000): An algebraic approach to hardware/software partitioning. — Tech. Rep., No. 206, The United Nations University, International Institute for Software Technology.
Search in Google Scholar
Quan G., Hu X. and Greenwood G. (1999): Preference-driven hierarchical hardware/software partitioning. — Proc. IEEE/ACM Int. Conf. Computer Design, Austin, USA, pp. 652-657.
Search in Google Scholar
Sanchis L.A. (1989): Multiple-way network partitioning. — IEEE Trans. Comp. Vol. 38, No. 1, pp. 62-81.10.1109/12.8730
Search in Google Scholar
Srinivasan V., Radhakrishnan S. and Vemuri R. (1998): Hardware software partitioning with integrated hardware design space exploration. — Proc. Design Automation and Test in Europe, DATE, Paris, France, pp. 28-35.10.1109/DATE.1998.655833
Search in Google Scholar
Stitt G., Lysecky R. and Vahid F. (2003): Dynamic hardware/software partitioning: A first approach. — Proc. IEEE/ACM 40th Design Automation Conference, Anaheim, USA, pp. 250-255.10.1145/775832.775896
Search in Google Scholar
Vahid F. (1997): Modifying min-cut for hardware and software functional partitioning. — Proc. Int. Workshop Hardware-Software Codesign, Braunschweig, Germany, pp. 43-48.10.1109/HSC.1997.584577
Search in Google Scholar
Vahid F. (2002): Partitioning sequential programs for CAD using a three-step approach. — ACM Trans. Des. Autom. Electron. Syst., Vol. 7, No. 3, pp. 413-429.10.1145/567270.567273
Search in Google Scholar
Vahid F. and Gajski D. (1995): Clustering for improved system-level functional partitioning. — Proc. 8th Int. Symp. System Synthesis, Cannes, France, pp. 28-33.10.1109/ISSS.1995.520609
Search in Google Scholar
Vahid F. and Le T.D. (1997): Extending the Kernighan/Linheuristic for hardware and software functional partitioning. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 237-261.10.1023/A:1008836303344
Search in Google Scholar
Wolf W.H. (1997): An architectural co-synthesis algorithm for distributed embedded computing systems. — IEEE Trans. VLSI Syst., Vol. 5, No. 2, pp. 218-229.10.1109/92.585225
Search in Google Scholar
Wolf W. (2003): A decade of hardware/software codesign. — IEEE Comp., Vol. 36, No. 4, pp. 38-43.10.1109/MC.2003.1193227
Search in Google Scholar
Yeh C.W., Cheng C.-K. and Lin T.-T.Y. (1994): A general purpose, multiple-way partitioning algorithm. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 13, No. 12, pp. 1480-1487.
Search in Google Scholar

Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

Abstract

Paradigm

My account