Creator:
Mann, Zoltán Ádám ; Orbán, András ; Farkas, Viktor
Contributor:
Title:
Evaluating the Kernighan-Lin heuristic for hardware/software partitioning
Group publication title:
Subject and Keywords:
Kernighan/Lin heuristic ; Fiduccia/Mattheyses heuristic ; hardware/software partitioning ; hardware/software codesign
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.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Date:
Resource Type:
DOI:
Pages:
Source:
AMCS, volume 17, number 2 (2007) ; click here to follow the link