Efficient heuristic and tabu search for hardware/software partitioning

• DOI: 10.1007/s11227-013-0888-9
• Publication Date: 2013-02-06T10:33:49Z
• Authors: Jigang Wu; Pu Wang; Siew-Kei Lam; Thambipillai Srik...
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

Hardware/software (HW/SW) partitioning is a crucial step in HW/SW codesign that determines which components of the system are implemented on hardware and which ones on software. It has been proved that the HW/SW partitioning problem is NP-hard. In this paper, we present two approaches for HW/SW partitioning that aims to minimize the hardware cost while taking into account software and communication constraints. The first is a heuristic approach that treats the HW/SW partitioning problem as an extended 0---1 knapsack problem. In the second approach, tabu search is used to further improve the solution obtained from the proposed heuristic algorithm. Experimental results show that the proposed algorithms outperform a recently reported work by up to 28 %.