<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><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—by using appropriate data structures—are also presented. These investigations are accompanied by numerous empirical test results.</p></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.

Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

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

International Journal of Applied Mathematics and Computer Science

{"article-title":"Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning"}

In recent years, several heuristics have been proposed for the hardware/software partitioning problem. One of the most promising directions is the adaptation...

Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

Published Online: Jul 17, 2007

Page range: 249 - 267

DOI: https://doi.org/10.2478/v10006-007-0022-3

Keywords
Kernighan/Lin heuristic, Fiduccia/Mattheyses heuristic, hardware/software partitioning, hardware/software co-design

This content is open access.

Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

Published Online: Jul 17, 2007

Page range: 249 - 267

DOI: https://doi.org/10.2478/v10006-007-0022-3

KeywordsKernighan/Lin heuristic, Fiduccia/Mattheyses heuristic, hardware/software partitioning, hardware/software co-design

This content is open access.

Keywords
Kernighan/Lin heuristic, Fiduccia/Mattheyses heuristic, hardware/software partitioning, hardware/software co-design