Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

• Autorzy: Mann Z. Á. , Orbán A. , Farkas V.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Kernighan/Lin heuristic; Fiduccia/Mattheyses heuristic; hardware/software partitioning; hardware-software codesign

PL

algorytm Kernighana-Lina; algorytm Fiduccia-Mattheysesa; partycjonowanie sprzętowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2007
• Tom: Vol. 17, no 2
• Strony: 249--267
• Opis fizyczny: Bibliogr. 50 poz., tab., wykr.

Twórcy

autor

Mann Z. Á.

• Budapest University of Technology and Economics, Department of Control Engineering and Information Technology, H–1117 Budapest, Magyar tudósok körútja 2, Hungary

autor

Orbán A.

• Budapest University of Technology and Economics, Department of Control Engineering and Information Technology, H–1117 Budapest, Magyar tudósok körútja 2, Hungary

autor

Farkas V.

• Budapest University of Technology and Economics, Department of Control Engineering and Information Technology, H–1117 Budapest, Magyar tudósok körútja 2, Hungary

Bibliografia

• [1] 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.
• [2] 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.
• [3] 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.
• [4] Arató P., Mann Z.Á. and Orbán A. (2003b): Hardwaresoftware co-design for Kohonen's self-organizing map. - Proc. IEEE 7th Int. Conf. Intelligent Engineering Systems, Luxor, Egypt, pp. 173-178.
• [5] Arató P., Mann Z.Á. and Orbán A. (2005a): Algorithmic aspects of hardware/software partitioning. - ACMTrans. Design Autom. Electron. Syst., Vol. 10, No. 1, pp. 136-156.
• [6] 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.
• [7] Arató P., Mann Z.Á. and Orbán A. (2007): Finding optimal hardware/software partitions. - Formal Meth. Syst. Design, (submitted).
• [8] Barros E., Rosenstiel W. and Xiong X. (1993): Hardware/ software partitioning with UNITY. - Proc. 2nd Int. Workshop Hardware-Software Codesign, Cambridge, USA.
• [9] 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] 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.
• [11] Cormen Th.H., Leiserson Ch.E., Rivest R.L. and Stein C. (2001): Introduction to Algorithms, 2nd Ed. - Cambridge: MIT Press.
• [12] 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.
• [13] de Berg M., Schwarzkopf O., van Kreveld M. and Overmars M. (2000): Computational Geometry: Algorithms and Applications, 2nd Ed.- Berlin: Springer.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] Ernst R., Henkel J. and Benner T. (1993): Hardware/software cosynthesis for microcontrollers. - IEEE Des. Test Comput., Vol. 10, No. 4, pp. 64-75.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] 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.
• [25] Kalavade A. (1995): System-level codesign of mixed hardwaresoftware systems.-Ph.D. thesis, University of California, Berkeley, CA, USA.
• [26] 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.
• [27] 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.
• [28] 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.
• [29] Krishnamurthy B. (1984): An improved min-cut algorithm for partitioning VLSI networks. - IEEE Trans. Comput., Vol. 33, No. 5, pp. 438-446.
• [30] Lopez-Vallejo M., Grajal J. and Lopez J.C. (2000): Constraintdriven system partitioning. - Proc. Design, Automation and Test in Europe Conference and Exhibition, Paris, France, pp. 411-416.
• [31] 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.
• [32] Lopez-Vallejo M. and Lopez J.C. (2003): On the hardwaresoftware partitioning problem: system modeling and partitioning techniques. - ACM Trans. Des. Autom. Electron. Syst., Vol. 8, No. 3, pp. 269-297.
• [33] 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.
• [34] 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.
• [35] 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.
• [36] Niemann R. (1998): Hardware/Software Co-Design for Data Flow Dominated Embedded Systems. -Norwell: Kluwer.
• [37] 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.
• [38] 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.
• [39] 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.
• [40] Quan G., Hu X. and Greenwood G. (1999): Preferencedriven hierarchical hardware/software partitioning. - Proc. IEEE/ACM Int. Conf. Computer Design, Austin, USA, pp. 652-657.
• [41] Sanchis L.A. (1989): Multiple-way network partitioning. - IEEE Trans. Comp. Vol. 38, No. 1, pp. 62-81.
• [42] 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.
• [43] 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.
• [44] Vahid F. (1997): Modifying min-cut for hardware and software functional partitioning. - Proc. Int. Workshop Hardware-Software Codesign, Braunschweig, Germany, pp. 43-48.
• [45] 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.
• [46] Vahid F. and Gajski D. (1995): Clustering for improved systemlevel functional partitioning. - Proc. 8th Int. Symp. System Synthesis, Cannes, France, pp. 28-33.
• [47] 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.
• [48] 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.
• [49] Wolf W. (2003): A decade of hardware/software codesign. - IEEE Comp., Vol. 36, No. 4, pp. 38-43.
• [50] 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.