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

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]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[2]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[3]	郭新明, 刘蕊, 谢飞, 林德钰. 无线视频传感器网络β-QoM目标栅栏覆盖构建算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2877-2884.
[4]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[5]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[6]	张新明, 温少晨, 刘尚旺. 差分扰动的堆优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2519-2527.
[7]	杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1155-1161.
[8]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.
[9]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.
[10]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[11]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[12]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[13]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[14]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[15]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.

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

Hardware/software partitioning based on improved simulated annealing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics