{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:44:15Z","timestamp":1709203455930},"reference-count":50,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,6,1]]},"abstract":"<jats:title>Evaluating the Kernighan-Lin Heuristic for Hardware\/Software Partitioning<\/jats:title><jats:p>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\u2014by using appropriate data structures\u2014are also presented. These investigations are accompanied by numerous empirical test results.<\/jats:p>","DOI":"10.2478\/v10006-007-0022-3","type":"journal-article","created":{"date-parts":[[2007,7,25]],"date-time":"2007-07-25T20:06:46Z","timestamp":1185394006000},"page":"249-267","source":"Crossref","is-referenced-by-count":6,"title":["Evaluating the Kernighan-Lin Heuristic for Hardware\/Software Partitioning"],"prefix":"10.61822","volume":"17","author":[{"given":"Zolt\u00e1n","family":"Mann","sequence":"first","affiliation":[]},{"given":"Andr\u00e1s","family":"Orb\u00e1n","sequence":"additional","affiliation":[]},{"given":"Viktor","family":"Farkas","sequence":"additional","affiliation":[]}],"member":"37438","reference":[{"issue":"1","key":"1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/12.822566","article-title":"Period-based load partitioning and assignment for large real-time applications","volume":"49","author":"T. Abdelzaher","year":"2000","journal-title":"IEEE Trans. Comput."},{"issue":"1-2","key":"2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-9260(95)00008-4","article-title":"Recent developments in netlist partitioning: A survey","volume":"19","author":"C. Alpert","year":"1995","journal-title":"VLSI J."},{"key":"3","first-page":"197","article-title":"Hardware\/software partitioning in embedded system design","author":"P. Arat\u00f3","year":"2003a"},{"key":"4","first-page":"173","article-title":"Hardware-software co-design for Kohonen's self-organizing map","author":"P. Arat\u00f3","year":"2003b"},{"issue":"1","key":"5","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/1044111.1044119","article-title":"Algorithmic aspects of hardware\/software partitioning","volume":"10","author":"P. Arat\u00f3","year":"2005a","journal-title":"ACM Trans. Design Autom. Electron. Syst."},{"issue":"12","key":"6","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/j.sysarc.2005.02.001","article-title":"Time-constrained scheduling of large pipelined datapaths","volume":"51","author":"P. Arat\u00f3","year":"2005b","journal-title":"J. Syst. Arch."},{"key":"7","article-title":"Finding optimal hardware\/software partitions","author":"P. Arat\u00f3","year":"2007","journal-title":"Formal Meth. Syst. Design"},{"key":"8","article-title":"Hardware\/software partitioning with UNITY","author":"E. Barros","year":"1993"},{"key":"9","first-page":"527","article-title":"A hardware\/software partitioning algorithm for designing pipelined ASIPs with least gate counts","author":"N. Binh","year":"1996"},{"key":"10","first-page":"42","article-title":"MAGELLAN: Multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs","author":"K. Chatha","year":"2001"},{"key":"11","volume-title":"Introduction to Algorithms","author":"Th. Cormen","year":"2001"},{"issue":"2","key":"12","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1109\/43.573831","article-title":"Two novel multiway circuit partitioning algorithms using relaxed locking","volume":"16","author":"A. Dasdan","year":"1997","journal-title":"IEEE Trans. Comput. Aided Des. Integ. Circ. Syst."},{"key":"13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. de Berg","year":"2000"},{"issue":"10","key":"14","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1109\/43.728914","article-title":"MOGAC: A multiobjective genetic algorithm for hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems","volume":"17","author":"R. Dick","year":"1998","journal-title":"IEEE Trans. Comput. Aided Des. Integ. Circ. Syst."},{"key":"15","first-page":"434","article-title":"Hardware\/software partitioning of VHDL system specifications","author":"P. Eles","year":"1996"},{"issue":"1","key":"16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1008857008151","article-title":"System level hardware\/software partitioning based on simulated annealing and tabu search","volume":"2","author":"P. Eles","year":"1997","journal-title":"Des. Autom. Emb. Syst."},{"issue":"4","key":"17","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1109\/54.245964","article-title":"Hardware\/software cosynthesis for microcontrollers","volume":"10","author":"R. Ernst","year":"1993","journal-title":"IEEE Des. Test Comput."},{"key":"18","first-page":"175","article-title":"A linear-time heuristic for improving network partitions","author":"C. Fiduccia","year":"1982"},{"key":"19","first-page":"22","article-title":"Hardware resource allocation for hardware\/software partitioning in the LYCOS system","author":"J. Grode","year":"1998"},{"issue":"3","key":"20","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/54.232470","article-title":"Hardware-software cosynthesis for digital systems","volume":"10","author":"R. Gupta","year":"1993","journal-title":"IEEE Des. Test Comput."},{"key":"21","first-page":"3","article-title":"MiBench: A free, commercially representative embedded benchmark suite","author":"M. Guthaus","year":"1997"},{"issue":"10","key":"22","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1109\/43.662682","article-title":"On implementation choices for iterative improvement partitioning algorithms","volume":"16","author":"L. Hagen","year":"1997","journal-title":"IEEE Trans. Comput. Aided Des. Integ. Circ. Syst."},{"issue":"2","key":"23","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1109\/92.924041","article-title":"An approach to automated hardware\/software partitioning using a flexible granularity that is driven by high-level estimation techniques","volume":"9","author":"J. Henkel","year":"2001","journal-title":"IEEE Trans. VLSI Syst."},{"key":"24","first-page":"173","article-title":"The dynamic locking heuristic - a new graph partitioning algorithm","author":"A Hoffmann","year":"1994"},{"key":"25","unstructured":"Kalavade A. (1995): <i>System-level codesign of mixed hardware-software systems<\/i>.\u2014Ph.D. thesis, University of California, Berkeley, CA, USA."},{"issue":"2","key":"26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1023\/A:1008872518365","article-title":"The extended partitioning problem: hardware\/software mapping, scheduling and implementation-bin selection","volume":"2","author":"A. Kalavade","year":"1997","journal-title":"Des. Autom. Emb. Syst."},{"issue":"9","key":"27","doi-asserted-by":"crossref","first-page":"819","DOI":"10.1109\/43.720318","article-title":"Hardware\/software partitioning for multifunction systems","volume":"17","author":"A. Kalavade","year":"1998","journal-title":"IEEE Trans. Comput. Aided Des. Integ. Circ. Syst."},{"issue":"2","key":"28","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","article-title":"An efficient heuristic procedure for partitioning graphs","volume":"49","author":"B. Kernighan","year":"1970","journal-title":"Bell Syst. Techn. J."},{"issue":"5","key":"29","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1109\/TC.1984.1676460","article-title":"An improved min-cut algorithm for partitioning VLSI networks","volume":"33","author":"B Krishnamurthy","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"30","first-page":"411","article-title":"Constraint-driven system partitioning","author":"M. Lopez-Vallejo","year":"2000"},{"key":"31","first-page":"914","article-title":"A knowledge based system for hardware-software partitioning","author":"M. Lopez-Vallejo","year":"1998"},{"issue":"3","key":"32","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/785411.785412","article-title":"On the hardware-software partitioning problem: system modeling and partitioning techniques","volume":"8","author":"M. Lopez-Vallejo","year":"2003","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"issue":"2","key":"33","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1023\/A:1008884219274","article-title":"LYCOS: The Lyngby co-synthesis system","volume":"2","author":"J. Madsen","year":"1997","journal-title":"Des. Autom. Emb. Syst."},{"key":"34","first-page":"222","article-title":"Optimization problems in system-level synthesis","author":"Z. Mann","year":"2003"},{"key":"35","first-page":"405","article-title":"A hardware\/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems","author":"B. Mei","year":"2000"},{"key":"36","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2803-3","volume-title":"Hardware\/Software Co-Design for Data Flow Dominated Embedded Systems","author":"R Niemann","year":"1998"},{"issue":"2","key":"37","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/A:1008832202436","article-title":"An algorithm for hardware\/software partitioning using mixed integer linear programming","volume":"2","author":"R. Niemann","year":"1997","journal-title":"Des. Autom. Emb. Syst."},{"key":"38","first-page":"447","article-title":"Interactive hardware-software partitioning and memory allocation based on data transfer profiling","author":"M. O'Nils","year":"1995"},{"key":"39","volume-title":"An algebraic approach to hardware\/software partitioning","author":"S. Qin","year":"2000"},{"key":"40","first-page":"652","article-title":"Preference-driven hierarchical hardware\/software partitioning","author":"G. Quan","year":"1999"},{"issue":"1","key":"41","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/12.8730","article-title":"Multiple-way network partitioning","volume":"38","author":"L Sanchis","year":"1989","journal-title":"IEEE Trans. Comp."},{"key":"42","first-page":"28","article-title":"Hardware software partitioning with integrated hardware design space exploration","author":"V. Srinivasan","year":"1998"},{"key":"43","first-page":"250","article-title":"Dynamic hardware\/software partitioning: A first approach","author":"G. Stitt","year":"2003"},{"key":"44","first-page":"43","article-title":"Modifying min-cut for hardware and software functional partitioning","author":"F Vahid","year":"1997"},{"issue":"3","key":"45","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1145\/567270.567273","article-title":"Partitioning sequential programs for CAD using a three-step approach","volume":"7","author":"F Vahid","year":"2002","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"46","first-page":"28","article-title":"Clustering for improved system-level functional partitioning","author":"F. Vahid","year":"1995"},{"issue":"2","key":"47","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1023\/A:1008836303344","article-title":"Extending the Kernighan\/Linheuristic for hardware and software functional partitioning","volume":"2","author":"F. Vahid","year":"1997","journal-title":"Des. Autom. Emb. Syst."},{"issue":"2","key":"48","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1109\/92.585225","article-title":"An architectural co-synthesis algorithm for distributed embedded computing systems","volume":"5","author":"W Wolf","year":"1997","journal-title":"IEEE Trans. VLSI Syst."},{"issue":"4","key":"49","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/MC.2003.1193227","article-title":"A decade of hardware\/software codesign","volume":"36","author":"W Wolf","year":"2003","journal-title":"IEEE Comp."},{"issue":"12","key":"50","doi-asserted-by":"crossref","first-page":"1480","DOI":"10.1109\/43.331405","article-title":"A general purpose, multiple-way partitioning algorithm","volume":"13","author":"C. Yeh","year":"1994","journal-title":"IEEE Trans. Comput. Aided Des. Integ. Circ. Syst."}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/17\/2\/article-p249.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/amcs.2007.17.issue-2\/v10006-007-0022-3\/v10006-007-0022-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:27:35Z","timestamp":1709202455000},"score":1,"resource":{"primary":{"URL":"https:\/\/content.sciendo.com\/doi\/10.2478\/v10006-007-0022-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,1]]},"references-count":50,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.2478\/v10006-007-0022-3","relation":{},"ISSN":["1641-876X"],"issn-type":[{"value":"1641-876X","type":"print"}],"subject":[],"published":{"date-parts":[[2007,6,1]]}}}