A Hybrid Branch-and-Bound Strategy for Hardware/Software Partitioning

This paper proposes a hybrid branch and bound strategy based on global best-first (GBF) scheme and local best-first (LBF) scheme.The proposed hybrid approach not only inherits the merit of GBF that produces fewer expanded nodes but also significantly reduces the search space of GBF, and thus it efficiently overcomes the blind search of the LBF scheme. A new data structure called string-queue is also proposed specially for the implementation of the selection rule and elimination rule in the branch and bound search. The properties of the hybrid approach are tested by computational experiments in hardware/software partitioning problem which is known to be NP-hard. Experimental results show that, the search space can be significantly reduced by the hybrid algorithm and the number of expanded nodes keeps less increase, when the hybrid frequency and the number of expanded nodes are properly chosen in its initial stage. As a result, the proposed hybrid framework successfully enhances the problem-solving capacity over the traditional branch-and-bound algorithm.