A branch-and-bound algorithm for hardware/software partitioning

This paper investigates hardware/software (Hw/Sw) partitioning, a key problem in embedded co-design system. An efficient algorithm are proposed to optimally solve the problem in which the communication overhead is taken into account. The proposed algorithm constructs an efficient branch-and-bound approach to partition the hot path selected by path profiling techniques. The techniques for generation of good initial solution and the efficient lower bound for the feasible solution are customized in branch and bound search. Experimental results show that the partition result proposed by the new algorithm produces 10% increase in speedup as compared with the traditional approximate algorithm in most of the cases.