基于改进模拟退火算法的软硬件划分

doi:10.3724/SP.J.1087.2011.01797

计算机应用 ›› 2011, Vol. 31 ›› Issue (07): 1797-1799.DOI: 10.3724/SP.J.1087.2011.01797

基于改进模拟退火算法的软硬件划分

肖平,徐成,杨志邦

湖南大学信息科学与工程学院,长沙 410082

收稿日期:2011-01-05 修回日期:2011-02-24 发布日期:2011-07-01 出版日期:2011-07-01
通讯作者: 肖平
作者简介:肖平(1985-),男,湖南邵阳人,硕士研究生,主要研究方向：嵌入式系统;徐成(1962-),男,湖北蕲春人,教授,主要研究方向：嵌入式系统;杨志邦(1984-),男,湖南邵阳人,博士研究生,主要研究方向：嵌入式系统;刘彦(1979-),男,湖南长沙人,讲师,主要研究方向：嵌入式系统、可重构计算。
基金资助:
国家自然科学基金资助项目

Hardware/software partitioning based on improved simulated annealing algorithm

Ping XIAO,Cheng XU,Zhi-Mang YANG

College of Information Science and Engineering,Hunan University,Changsha Hunan 410082,China

Received:2011-01-05 Revised:2011-02-24 Online:2011-07-01 Published:2011-07-01
Contact: Ping XIAO

摘要/Abstract

摘要： 软硬件划分是嵌入式系统协同设计中的关键问题，已经被证明是一个NP问题。模拟退火算法是解决该问题常用的启发式算法，但是其存在收敛速度过慢的问题。通过改进算法的扰动模型和退火进度，提出一种新的代价函数计算方法来提高它的收敛速度。实验结果表明，相对于基于经典的模拟退火算法和已有改进的算法，新算法运行时间大大减少，并且增大了找到近似最优解的概率。

关键词: 软硬件协同设计, 软硬件划分, 启发式算法, 模拟退火, 代价函数

Abstract: Hardware/software partitioning is a key issue of embedded system design, and it has been proven to be a NP problem. Simulated annealing algorithm is a heuristic algorithm to solve this problem, but the simulated annealing algorithm has slow convergence. By improving the disturbance model and its annealing schedule, a new cost function method was proposed to accelerate the convergence speed. Compared to the classical simulated annealing algorithm and improved algorithms, the experimental results show that the new algorithm significantly reduces the running time and increases the probability of finding an approximately optimal solution.

Key words: Hardware/software co-design, Hardware-software partitioning, Heuristic algorithm, Simulated annealing, Cost function

中图分类号:

TP302.7

肖平徐成杨志邦. 基于改进模拟退火算法的软硬件划分[J]. 计算机应用, 2011, 31(07): 1797-1799.

Ping XIAO Cheng XU Zhi-Mang YANG. Hardware/software partitioning based on improved simulated annealing algorithm[J]. Journal of Computer Applications, 2011, 31(07): 1797-1799.

参考文献

[1]APAT P,MANN Z ,ORBáN A. Hardware-software co-design for Kohonen’s self organizing map[C]// Proceedings of the IEEE 7th International Conference on Intelligent Engineering Systems. New York: IEEE,2003:136-156.

[2]BASSIRI M M,SHAHHOSEINI H S. On-line HW/SW partitioning and co-scheduling in reconfigurable computing systems[C]// 2nd IEEE International Conference on Computer Science and Information Technology. New York: IEEE,2009:557-562.

[3]MEEUWS R. A quantitative model for hardware/software partitioning[D]. Julianalaan, NetherLands: Delft University of Technology,2007.

[4]CHEHIDA K B,AUGUIN M. HW/SW partitioning approach for reconfigurable system design[C]// Proceedings of the 2002 International Conference on Compilers,Architecture,and Synthesis for Embedded Systems. New York: ACM,2002:247-251.

[5]WU JIGANG,SRIKANTHAN T. Algorithmic aspects of hardware/software partitioning: 1D search algorithms[J]. IEEE Transactions on Computers,2010,59(4):532-544.

[6]BANERJEE S,DUTT N. Efficient search space exploration for HW-SW partitioning[C]// The IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. New York: ACM,2004: 122-127.

[7]邢冀鹏,邹雪城,刘政林,等.一种基于改进模拟退火算法的软硬件划分技术[J].微电子学与计算机,2006,23(5):31-37.

[8]ELES P,PENG Z,KUCHCINSKI K,et al. System level hardware/software partitioning based on simulated annealing and tabu search[J]. Design Automation for Embedded Systems,1997,2(1):5-32.

[9]KORYFIDIS I. Power aware HW/SW partitioning for DVB-H receiver module[D]. Julianalaan,Netherlands: Delft University of Technology,2006.

[10]沈英哲,周学海.一种用于可重构计算系统的软硬件划分算法[J].中国科学技术大学学报,2009,39(2)：182-188.

[11]VAKIL-BAGHMISHEH M T,NAVARBAF A. A modified very fast simulated annealing algorithm[C]// 2008 Internatioal Symposium on Telecommunications. New York: IEEE,2008:61-66.

[12]Task Graphs for Free (TGFF v3.0)[EB/OL].[2010-10-20].http://ziyang.eecs.umich.edu/~dickrp/tgff/

[1]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[2]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[3]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[4]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[5]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[6]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[7]	刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.
[8]	隗千千, 董兴业, 王焕政. 染缸排产建模及滑动时间窗启发式调度算法[J]. 计算机应用, 2020, 40(1): 292-298.
[9]	朱杰, 张文怡, 薛菲. 基于遗传模拟退火算法的立体仓库储位优化[J]. 计算机应用, 2020, 40(1): 284-291.
[10]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[11]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[12]	林立, 孟学雷, 宋仲仲. 考虑区域协调性的城际列车开行方案优化[J]. 计算机应用, 2019, 39(2): 598-603.
[13]	李飞龙, 赵春艳, 范如梦. 基于禁忌搜索算法求解随机约束满足问题[J]. 计算机应用, 2019, 39(12): 3584-3589.
[14]	吴斌, 王超, 董敏. 基于混合果蝇优化算法的现场服务调度问题[J]. 计算机应用, 2018, 38(9): 2706-2711.
[15]	赵云钦, 蔡超, 王厚军, 李东武. 基于带电粒子搜索的无人潜航器航路规划方法[J]. 计算机应用, 2018, 38(7): 2107-2112.

基于改进模拟退火算法的软硬件划分

Hardware/software partitioning based on improved simulated annealing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics