基于扩展背包问题的的软硬件划分算法

Hardware/Software Partitioning Algorithm Based on Extension Knapsack

软硬件划分问题常以时间为约束对硬件面积进行优化。随着嵌入式的发展,功耗这一因素也越来越重要,故在约束条件中加入了功耗的约束。贪婪算法是解决0-1背包问题的一种简单有效的方法,因此建立多约束的软硬件划分问题与0-1背包问题之间的联系,采用扩展的贪婪算法解决多性能指标的软硬件划分问题。利用仿真与动态规划方法的对比,进行了有效性验证。

The hardware/software partitioning often takes time as the restraint to optimize hardware area. With the development of embedded technology, the factor of power consumption becomes more important. Therefore, the restraint to power consumption is added into the restraint condition. Since the greedy algorithm is an easy but effective method to solve the 0-1 knapsack problem, a re- lationship between the text multi-restraint hardware/software partitioning and 0-1 knapsack is established. The extended greedy algo- rithm is adopted to solve the problem of the hardware/software partitioning with many performance indexes. A effective verification was implemented with the method of the contrast between the simulation and dynamic planning results. The simulation reults show that the method can ruduce execution time and get good approximate solutions.