Multiple-choice hardware/software partitioning: Computing model and algorithms

Hardware/software (HW/SW) partitioning is one of the crucial steps of co-design systems. It determines which components of the system are implemented in hardware and which ones are in software. As hardware of larger area may provide higher implementing speed for a give component due to the parallelizable execution in hardware, one component may have different ways of hardware implementations. In this paper the computing model is proposed to cater for the multiple-choice HW/SW partitioning. On the new computing model an efficient heuristic algorithm is developed, in which both speedup in hardware and communication penalty are taken into account. In addition, an exact algorithm is also presented based on dynamic programming to evaluate the approximate solutions produced by the heuristic algorithm for relatively small problems. Simulation results show that the heuristic algorithm runs fast and is able to produce high-quality approximate solutions. The difference between the approximate solutions and the optimal ones is bounded by 0.5%, and it hardly increases with the increase in the problem size.