基于贪心算法和模拟退火算法的软硬件划分  

Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm

作　　者：张良[1] 徐成[1] 田峥[1] 李涛[1] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机应用》2013年第7期1898-1902,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60973030);湖南省科研条件创新专项(2010TT1002)

摘　　要：软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。Hardware/Software （HW/SW） partitioning is one of the crucial steps in the co-design of embedded system, and it has been proven to be a NP problem. Considering that the latest work has slow convergence speed and poor solution quality, the authors proposed a HW/SW partitioning method based on greedy algorithm and Simulated Annealing （SA） algorithm. This method reduced the HW/SW partitioning problem to the extended 0-1 knapsack problem, and used the greedy algorithm to do the initial rapid partition; then divided the solution space reasonably and designed a new cost function and used the improved SA algorithm to search for the global optimal solution. Compared to the existing improved algorithms, the experimental results show that the new algorithm is more effective and practical in terms of the quality of partitioning and the running time, and the promotion proportions are 8% and 17% respectively.

关 键 词：软硬件划分 启发式算法 0—1背包问题 模拟退火 代价函数 

分 类 号：TP302.7[自动化与计算机技术—计算机系统结构]