Hardware/software (HW/SW) partitioning is to determine which componentsof a system are implemented on hardware and which ones on software. It is one of the mostimportant steps in the design of embedded systems. The HW/SW partitioning problem is anNP-hard constrained binary optimization problem. In this paper, we propose a tabu search-basedmemetic algorithm to solve the HW/SW partitioning problem. First, we convert theconstrained binary HW/SW problem into an unconstrained binary problem using an adaptivepenalty function that has no parameters in it. A memetic algorithm is then suggestedfor solving this unconstrained problem. The algorithm uses a tabu search as its local searchprocedure. This tabu search has a special feature with respect to solution generation, andit uses a feedback mechanism for updating the tabu tenure. In addition, the algorithm integratesa path relinking procedure for exploitation of newly found solutions. Computationalresults are presented using a number of test instances from the literature. The algorithmproves its robustness when its results are compared with those of two other algorithms. Theeffectiveness of the proposed parameter-free adaptive penalty function is also shown.
展开▼
