Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

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

International Journal of Applied Mathematics and Computer Science, Tome 17 (2007), p. 249-267 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2007-01-01

Zbl 1126.68002

EUDML-ID : urn:eudml:doc:207835

Bibliographie

[000] 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.

[001] 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. | Zbl 0876.94063

[002] 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.

[003] 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.

[004] 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.

[005] 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.

[006] Arató P., Mann Z.Á. and Orbán A. (2007): Finding optimal hardware/software partions. - Formal Meth. Syst. Design, (submitted). | Zbl 1131.68119

[007] Barros E., Rosenstiel W. and Xiong X. (1993): Hardware/software partitioning with UNITY. - Proc. 2nd Int. Workshop Hardware-Software Codesign, Cambridge, USA.

[008] 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.

[009] 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.

[010] Cormen Th.H., Leiserson Ch.E., Rivest R.L. and Stein C. (2001): Introduction to Algorithms, 2nd Ed. - Cambridge: MIT Press. | Zbl 1047.68161

[011] 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.

[012] de Berg M., Schwarzkopf O., van Kreveld M. and Overmars M. (2000): Computational Geometry: Algorithms and Applications, 2nd Ed. - Berlin: Springer. | Zbl 0939.68134

[013] 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.

[014] Eles P., Peng Z., Kuchcinski K. and Doboli A. (1996): Hardware/software partitioning of VHDL system specifications. - Proc. European Design Automation Conference, Geneva, Swzerland, pp.434-439.

[015] 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.

[016] Ernst R., Henkel J. and Benner T. (1993): Hardware/software cosynthesis for microcontrollers. - IEEE Des. Test Comput., Vol.10, No.4, pp.64-75.

[017] Fiduccia C.M. and Mattheyses R.M. (1982): A linear-time heuristic for improving network partions. - Proc. 19th Design Automation Conference, Piscataway, USA, pp.175-181.

[018] 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.

[019] Gupta R.K. and deMicheli G. (1993): Hardware-software cosynthesis for digital systems. - IEEE Des. Test Comput., Vol.10, No.3, pp.29-41.

[020] 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 sue. - Proc. IEEE 4th Ann. Workshop Workload Characterization, Austin, USA, pp.3-14.

[021] 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.

[022] Henkel J. and Ernst R. (2001): An approach to automated hardware/software partitioning using a flexible granulary that is driven by high-level estimation techniques. - IEEE Trans. VLSI Syst., Vol.9, No.2, pp.273-289.

[023] 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.

[024] Kalavade A. (1995): System-level codesign of mixed hardware-software systems. - Ph.D. thesis, University of California, Berkeley, CA, USA.

[025] 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.

[026] 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.

[027] 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. | Zbl 0333.05001

[028] Krishnamurthy B. (1984): An improved min-cut algorithm for partitioning VLSI networks. - IEEE Trans. Comput., Vol.33, No.5, pp.438-446. | Zbl 0529.94022

[029] Lopez-Vallejo M., Grajal J. and Lopez J.C. (2000): Constraint-driven system partitioning. - Proc. Design, Automation and Test in Europe Conference andExhibion, Paris, France, pp.411-416.

[030] 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.

[031] 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.

[032] 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.

[033] 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.

[034] 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.

[035] Niemann R. (1998): Hardware/Software Co-Design for Data Flow Dominated Embedded Systems. - Norwell: Kluwer. | Zbl 0927.68003

[036] 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.

[037] 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.

[038] Qin S. and He J. (2000): An algebraic approach to hardware/software partitioning. - Tech. Rep., No.206, The Uned Nations University, International Institute for Software Technology.

[039] 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.

[040] Sanchis L.A. (1989): Multiple-way network partitioning. - IEEE Trans. Comp., Vol.38, No.1, pp.62-81. | Zbl 0709.94615

[041] 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.

[042] 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.

[043] Vahid F. (1997): Modifying min-cut for hardware and software functional partitioning. - Proc. Int. Workshop Hardware-Software Codesign, Braunschweig, Germany, pp.43-48.

[044] 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.

[045] Vahid F. and Gajski D. (1995): Clustering for improved system-level functional partitioning. - Proc. 8th Int. Symp. System Synthesis, Cannes, France, pp.28-33.

[046] Vahid F. and Le T.D. (1997): Extending the Kernighan/Lin heuristic for hardware and software functional partitioning. - Des. Autom. Emb. Syst., Vol.2, No.2, pp.237-261.

[047] 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.

[048] Wolf W. (2003): A decade of hardware/software codesign. - IEEE Comp., Vol.36, No.4, pp.38-43.

[049] 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