International Journal of applied mathematics and computer science

online read us now

Paper details

Number 2 - June 2007
Volume 17 - 2007

Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

Zoltán Ádám Mann, András Orbán, Viktor Farkas

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.

Keywords
Kernighan/Lin heuristic, Fiduccia/Mattheyses heuristic, hardware/software partitioning, hardware/software codesign

DOI
10.2478/v10006-007-0022-3