高效软硬件划分算法及其提升技术

软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。

Efficient Heuristic and Tabu Search for Hardware/Software Partitioning

Hardware/software(HW/SW) partitioning is one of the crucial steps in HW/SW co-design. It determines which componented of the system arc implemented on hardware and which ones on software. It has been proved that the HW/SW partitioning problem is NP-hard. This paper presented an heuristic algorithm for the HW/SW partitioning problem, which has been treated as an extended 0-1 knapsack problem. Tabu search was used to further the solution obtamed through the proposed heuristic algorithm, in order to minimize the hardware cost with the constraints of the soft- ware cost and the communication cost. Experimental results show that the algorithms proposed in the paper can produce better solution than the latest work, and the improvement is up to 28%.