[1]鄢小虎,何发智,陈壹林.求解大规模软硬件划分问题的爬山淘汰粒子群算法[J].东南大学学报(自然科学版),2017,47(2):225-230.[doi:10.3969/j.issn.1001-0505.2017.02.005]
　Yan Xiaohu,He Fazhi,Chen Yilin.Elimination particle swarm optimization with hill climbing algorithm for solving large-scale hardware/software partitioning problem[J].Journal of Southeast University (Natural Science Edition),2017,47(2):225-230.[doi:10.3969/j.issn.1001-0505.2017.02.005]
点击复制

求解大规模软硬件划分问题的爬山淘汰粒子群算法()
分享到：

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
47
期数:
2017年第2期
页码:
225-230
栏目:
计算机科学与工程
出版日期:
2017-03-20

文章信息/Info

Title:
Elimination particle swarm optimization with hill climbing algorithm for solving large-scale hardware/software partitioning problem
作者:
鄢小虎; 何发智; 陈壹林
1武汉大学软件工程国家重点实验室, 武汉 430072; 2武汉大学计算机学院, 武汉 430072
Author(s):
Yan Xiaohu;  He Fazhi;  Chen Yilin
1State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China
2School of Computer Science and Technology, Wuhan University, Wuhan 430072, China
关键词:
软硬件划分;  粒子群优化算法;  爬山法;  通信代价;  并行计算
Keywords:
hardware/software partitioning;  particle swarm optimization algorithm;  hill climbing algorithm;  communication cost;  parallel computing
分类号:
TP301
DOI:
10.3969/j.issn.1001-0505.2017.02.005
摘要:
为了求解大规模软硬件划分问题,提出了一种爬山淘汰粒子群算法(EPSO-HC).首先,模拟达尔文进化论,淘汰群体中当前全局最差位置附近的个体,保持搜索种群的多样性,防止算法早熟收敛;其次,改进爬山法的搜索机制,以粒子自身经历的最优位置为方向,在当前全局最优位置附近集中搜索,提升解的质量;然后,采用图形处理器并行计算软硬件通信代价,以减少EPSO-HC算法的运行时间;最后,通过求解基准任务和特大规模任务来评价EPSO-HC算法的性能.试验结果表明,针对23个软硬件划分任务,与其他软硬件划分算法相比,所提算法解的质量更高,运行时间更少.
Abstract:
To solve the large-scale hardware/software(HW/SW)partitioning problem, an elimination particle swarm optimization with hill climbing(EPSO-HC)algorithm is proposed. First, the Darwin’s theory of evolution is stimulated, and the particles in the immediate vicinity of the current global worst position are eliminated to keep population diversity and avoid premature convergence. Secondly, the search mechanism of the hill climbing(HC)algorithm is improved by regarding the particles’ own best positions as the search directions. Focus search is carried out near the current global position and the solution quality is improved. Then, the graphic processing unit(GPU)is adopted to compute the HW/SW communication cost in parallel to reduce the runtime of the EPSO-HC algorithm. Finally, the experiments on benchmark and large-scale HW/SW partitioning tasks are conducted to evaluate the algorithm performance. The experimental results show that, compared with the other HW/SW partitioning algorithms for 23 HW/SW partitioning tasks, the proposed algorithm achieves higher quality solution and shorter runtime.

参考文献/References:

[1] Trindade A B, Cordeiro L C. Applying SMT-based verification to hardware/software partitioning in embedded systems[J]. Design Automation for Embedded Systems, 2016, 20(1): 1-19. DOI:10.1007/s10617-015-9163-z.
[2] Arató P, Mann Z Á, Orbán A. Algorithmic aspects of hardware/software partitioning[J]. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1): 136-156. DOI:10.1145/1044111.1044119.
[3] Abdelhalim M B, Salama A E, Habib S E D. Hardware software partitioning using particle swarm optimization technique[C]//IEEE 6th International Workshop on System on Chip for Real Time Applications. Cairo,Egypt, 2006: 189-194. DOI: 10.1109/IWSOC. 2006.348234.
[4] Abdelhalim M B, Habib S E D. An integrated high-level hardware/software partitioning methodology[J]. Design Automation for Embedded Systems, 2011, 15(1): 19-50. DOI: 10.1007/s10617-010-9068-9.
[5] Eimuri T, Salehi S. Using DPSO and B&B algorithms for hardware/software partitioning in co-design[C]//The 2nd International Conference on Computer Research and Development. Kuala Lumpur,Malaysia, 2010: 416-420. DOI 10.1109/ICCRD.2010.88.
[6] Wu J G, Srikanthan T, Chen G. Algorithmic aspects of hardware/software partitioning: 1D search algorithms[J]. IEEE Transactions on Computers, 2010, 59(4): 532-544. DOI: 10.1109/TC.2009.173.
[7] Wu J G, Wang P, Lam S K, et al. Efficient heuristic and tabu search for hardware/software partitioning[J]. The Journal of Supercomputing, 2013, 66(1): 118-134. DOI: 10.1007/s11227-013-0888-9.
[8] 陈志,武继刚,宋国治,等. NodeRank:一种高效软硬件划分算法[J]. 计算机学报, 2013,36(10): 2033-2040. DOI: 10.3724/SP.J.1016.2013.02033.
Chen Zhi, Wu Jigang, Song Guozhi, et al. NodeRank: An efficient algorithm for hardware/software partitioning[J]. Chinese Journal of Computers, 2013, 36(10): 2033-2040. DOI:10.3724/SP.J.1016. 2013.02033. (in Chinese)
[9] Wang G G, Gandomi A H, Alavi A H, et al. A hybrid method based on krill herd and quantum-behaved particle swarm optimization[J]. Neural Computing and Applications, 2016, 27(4): 989-1006. DOI:10.1007/s00521-015-1914-z.
[10] Vorzimmer P. Darwin, Malthus, and the theory of natural selection[J]. Journal of the History of Ideas, 1969, 30(4): 527-542. DOI: 10.2307/2708609.

相似文献/References:

[1]史林军,张磊,陈少哺,等.飞轮储能系统在抑制电力系统多模式振荡中的应用[J].东南大学学报(自然科学版),2012,42(2):323.[doi:10.3969/j.issn.1001-0505.2012.02.025]
　Shi Linjun,Zhang Lei,Chen Shaobu,et al.Application of FESS in damping power system multi-mode oscillations[J].Journal of Southeast University (Natural Science Edition),2012,42(2):323.[doi:10.3969/j.issn.1001-0505.2012.02.025]
[2]熊培银,赖旭芝,吴敏.一类二阶非完整平面欠驱动机械系统位姿控制[J].东南大学学报(自然科学版),2015,45(4):690.[doi:10.3969/j.issn.1001-0505.2015.04.014]
　Xiong Peiyin,Lai Xuzhi,Wu Min.Position and attitude control for a class of planar underactuated mechanical system with second order non-holonomic constraints[J].Journal of Southeast University (Natural Science Edition),2015,45(2):690.[doi:10.3969/j.issn.1001-0505.2015.04.014]
[3]高岭,申元,高妮,等.基于文本挖掘的漏洞信息聚类分析[J].东南大学学报(自然科学版),2015,45(5):845.[doi:10.3969/j.issn.1001-0505.2015.05.006]
　Gao Ling,Shen Yuan,Gao Ni,et al.Clustering analysis of vulnerability information based on text mining[J].Journal of Southeast University (Natural Science Edition),2015,45(2):845.[doi:10.3969/j.issn.1001-0505.2015.05.006]

备注/Memo

备注/Memo:
收稿日期: 2016-08-14.
作者简介: 鄢小虎(1986— ),男,博士生;何发智(联系人),男,博士,教授,博士生导师,fzhe@whu.edu.cn.
基金项目: 国家自然科学基金资助项目(61472289)、国家重点研发计划资助项目(2016YFC0106305).
引用本文: 鄢小虎,何发智,陈壹林.求解大规模软硬件划分问题的爬山淘汰粒子群算法[J].东南大学学报(自然科学版),2017,47(2):225-230. DOI:10.3969/j.issn.1001-0505.2017.02.005.
更新日期/Last Update: 2017-03-20