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.
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.
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.
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.
Financed by the National Centre for Research and Development under grant No. SP/I/1/77065/10 by the strategic scientific research and experimental development program:
SYNAT - “Interdisciplinary System for Interactive Scientific and Scientific-Technical Information”.