A Tabu Search-Based Memetic Algorithm for HardwareSoftware Partitioning

Abstract EN

Hardware/software (HW/SW) partitioning is to determine which components of a system are implemented on hardware and which ones on software.

It is one of the most important steps in the design of embedded systems.

The HW/SW partitioning problem is an NP-hard constrained binary optimization problem.

In this paper, we propose a tabu search-based memetic algorithm to solve the HW/SW partitioning problem.

First, we convert the constrained binary HW/SW problem into an unconstrained binary problem using an adaptive penalty function that has no parameters in it.

A memetic algorithm is then suggested for solving this unconstrained problem.

The algorithm uses a tabu search as its local search procedure.

This tabu search has a special feature with respect to solution generation, and it uses a feedback mechanism for updating the tabu tenure.

In addition, the algorithm integrates a path relinking procedure for exploitation of newly found solutions.

Computational results are presented using a number of test instances from the literature.

The algorithm proves its robustness when its results are compared with those of two other algorithms.

The effectiveness of the proposed parameter-free adaptive penalty function is also shown.