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

Elimination particle swarm optimization with hill climbing algorithm for solving large-scale hardware/software partitioning problem

作　　者：鄢小虎[1,2] 何发智[1,2] 陈壹林 Yan Xiaohu He Fazhi Chen Yilin(State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China School of Computer Science and Technology, Wuhan University, Wuhan 430072, China)

机构地区：[1]武汉大学软件工程国家重点实验室,武汉430072 [2]武汉大学计算机学院,武汉430072

出　　处：《东南大学学报（自然科学版）》2017年第2期225-230,共6页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(61472289);国家重点研发计划资助项目(2016YFC0106305)

摘　　要：为了求解大规模软硬件划分问题,提出了一种爬山淘汰粒子群算法(EPSO-HC).首先,模拟达尔文进化论,淘汰群体中当前全局最差位置附近的个体,保持搜索种群的多样性,防止算法早熟收敛;其次,改进爬山法的搜索机制,以粒子自身经历的最优位置为方向,在当前全局最优位置附近集中搜索,提升解的质量;然后,采用图形处理器并行计算软硬件通信代价,以减少EPSOHC算法的运行时间;最后,通过求解基准任务和特大规模任务来评价EPSO-HC算法的性能.试验结果表明,针对23个软硬件划分任务,与其他软硬件划分算法相比,所提算法解的质量更高,运行时间更少.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 EPSOHC algorithm. Finally,the experiments on benchmark and large-scale HW/SW partitioning tasks are conducted to evaluate the algorithm performance. The experimental results showthat,compared with the other HW/SW partitioning algorithms for 23 HW/SW partitioning tasks,the proposed algorithm achieves higher quality solution and shorter runtime.

关 键 词：软硬件划分 粒子群优化算法 爬山法 通信代价 并行计算 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]