计算机应用 ›› 2013, Vol. 33 ›› Issue (07): 1898-1902.DOI: 10.11772/j.issn.1001-9081.2013.07.1898

• 先进计算 • 上一篇    下一篇

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

张良,徐成,田峥,李涛   

  1. 湖南大学 信息科学与工程学院,长沙 410082
  • 收稿日期:2013-01-24 修回日期:2013-03-01 出版日期:2013-07-01 发布日期:2013-07-06
  • 通讯作者: 张良
  • 作者简介:张良(1987-),男,河南南阳人,硕士研究生,主要研究方向:嵌入式系统;徐成(1962-),男,湖北蕲春人,教授,博士,CCF会员,主要研究方向:嵌入式系统、数字视频处理、机械控制与自动化;田峥(1983-),男,湖南长沙人,博士研究生,CCF会员,主要研究方向:计算机视觉、模式识别;李涛(1986-),男,湖南郴州人,硕士研究生,主要研究方向:嵌入式系统。
  • 基金资助:

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

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

ZHANG Liang,XU ChengCheng,TIAN Zheng,LI Tao   

  1. College of Information Science and Engineering, Hunan University, Changsha Hunan 410082, China
  • Received:2013-01-24 Revised:2013-03-01 Online:2013-07-06 Published:2013-07-01
  • Contact: ZHANG Liang

摘要: 软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。

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

Abstract: 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.

Key words: Hardware/Software (HW/SW) partitioning, heuristic algorithm, 0-1 knapsack problem, Simulated Annealing (SA), cost function

中图分类号: