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

作     者：张良 徐成 田峥 李涛 ZHANG Liang;XU Cheng;TIAN Zheng;LI Tao

作者机构：湖南大学信息科学与工程学院长沙410082 

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

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2013年第33卷第7期

页      码：1898-1902页

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

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

学科分类：08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11772/j.issn.1001-9081.2013.07.1898

馆 藏 号：203581202...