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

鄢小虎 何发智 陈壹林

(1武汉大学软件工程国家重点实验室, 武汉 430072)(2武汉大学计算机学院, 武汉 430072)

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

鄢小虎 何发智 陈壹林

(1武汉大学软件工程国家重点实验室, 武汉 430072)(2武汉大学计算机学院, 武汉 430072)

为了求解大规模软硬件划分问题,提出了一种爬山淘汰粒子群算法(EPSO-HC)．首先,模拟达尔文进化论,淘汰群体中当前全局最差位置附近的个体,保持搜索种群的多样性,防止算法早熟收敛;其次,改进爬山法的搜索机制,以粒子自身经历的最优位置为方向,在当前全局最优位置附近集中搜索,提升解的质量;然后,采用图形处理器并行计算软硬件通信代价,以减少EPSO-HC算法的运行时间;最后,通过求解基准任务和特大规模任务来评价EPSO-HC算法的性能．试验结果表明,针对23个软硬件划分任务,与其他软硬件划分算法相比,所提算法解的质量更高,运行时间更少．

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

现代嵌入式系统是软件和硬件一体化的系统,系统的任务由硬件实现(如FPGA,ASIC等)和软件实现(如ARM,DSP等)协同完成．硬件实现速度快,但成本较高;软件实现的代价低,但需要耗费更多的时间[1]．软硬件划分是指在满足一定的约束条件下，将系统功能合理地分配到软件实现或硬件实现上.

目前，求解软硬件划分问题的方法分为精确算法和启发式算法2类[2].粒子群算法实现容易且收敛速度快，已成功应用于求解软硬件划分的问题中.在硬件代价和求解时间方面，文献[3]指出基于粒子群算法的软硬件划分方法优于遗传算法.文献[4]将再启动技术引入粒子群算法，以求解软硬件划分问题.文献[5]融合粒子群算法和禁忌搜索算法，求解软硬件划分问题.然而，随着嵌入式系统设计规模的逐渐增大，现有的启发式算法已难以获取最优解.

本文提出了一种爬山淘汰粒子群算法(EPSO-HC)来求解大规模软硬件划分问题,通过模拟达尔文进化论,增加搜索种群的多样性;通过更新当前全局最优位置,增强搜索的集中性．

1 模型定义

本文采用文献[6]中的软硬件划分模型.在无向图G=(V,E)中,V和E分别表示节点和边的集合．软硬件划分问题可以描述为

xi∈{0,1},i=1,2,…,n

(1)

式中,x={x1,x2,…,xn}表示软硬件划分问题的一个解;C(x)表示软硬件划分x的通信代价;si和hi分别表示节点vi的软件代价和硬件代价;xi=1表示节点i由软件实现,xi=0表示节点i由硬件实现;R为约束值．

文献[6]提出了3种启发式的一维搜索算法来求解式(1),其中Alg-new3算法性能最佳．文献[7-8] 针对式(1),分别提出了启发式的Heur算法和基于迭代排序思想的NodeRank算法．

2 爬山淘汰粒子群算法

在标准粒子群算法中,N个粒子在D维目标搜索空间中寻优,令第t个粒子的当前位置Xt,速度Vt和自身经历的最优位置Pt分别为

Xt={Xt1,Xt2,…,Xtd,…,XtD}

(2)

Vt={Vt1,Vt2,…,Vtd,…,VtD}

(3)

Pt={Pt1,Pt2,…,Ptd,…,PtD}

(4)

式中,1≤t≤N,1≤d≤D．

将群体中当前全局最优的位置记为Pg={Pg1,Pg2,…,PgD},则粒子群算法的进化方程为

(5)

(6)

式中,w为惯性权重;r1,r2为[0,1]区间中的随机数;c1,c2为学习因子;k为迭代次数．标准粒子群算法在求解复杂问题时存在容易陷入局部最优解和早熟收敛的问题[9]．

2.1 淘汰粒子群算法

根据达尔文进化论,物竞天择,适者生存,生物间互相竞争,能适应环境者被选择存留下来,不能适应环境者将被淘汰[10]．本文通过模拟达尔文进化论,淘汰群体中不能适应环境的弱小粒子．

定义1(不能适应环境者) 将不能适应环境者定义为群体中弱小的个体．

定义2(弱小的粒子) 将弱小的粒子定义为群体中当前全局最差位置附近的粒子．

在淘汰粒子群算法中,模拟达尔文进化论,淘汰当前全局最差位置附近的弱小粒子,由随机产生的粒子替代．在群体中,将当前全局最差位置定义为Pw={Pw1,Pw2,…,PwD},第j个弱小粒子的位置为Yj={Yj1,Yj2,…,YjD}．由于弱小粒子在全局最差位置的附近,则Yj和Pw之间的关系如图1所示．

图1 全局最差位置附近的粒子

在图1中,Yj-1,Yj和Yj+1为弱小粒子的位置．Yj在以Pw为中心的圆圈内,则

(7)

式中,c3为范围因子;Ra为粒子的搜索半径．在淘汰粒子群算法中,随机产生的新粒子替代弱小的粒子,能增加搜索种群的多样性,防止算法早熟收敛．

2.2 改进爬山法

爬山法(HC)是一种常用的贪心搜索算法．该算法在当前解的邻域内进行搜索,若候选解优于当前解,则用该解替代当前解;反之则搜索另外一个解再进行比较,直到满足终止条件时为止．

本文采用爬山法在当前全局最优位置Pg附近寻优,利用搜索到的更优位置替代Pg．爬山法的搜索方向是随机的,因此该方法的搜索过程盲目且效率较低．本文改进了爬山法的搜索方向,从粒子群自身最优位置Pi中随机取l个点作为算法的搜索方向,改进爬山法的搜索过程示意图如图2所示．

图2 改进爬山法的搜索过程示意图

对于当前全局最优位置,改进爬山法向前搜索的位置为

(8)

改进爬山法循环向前搜索,直到将l个方向搜索完,算法结束．利用改进爬山法更新当前全局最优位置,能够提升解的质量，增强搜索的集中性．

3 基于爬山淘汰粒子群算法的并行软硬件划分方法

软硬件划分问题属于组合最优化问题,求解时需要采用离散的EPSO-HC算法．本文采用如下公式对每个粒子的位置进行离散化:

(9)

采用离散的EPSO-HC算法来求解式(1),图3为EPSO-HC算法的流程图．为了提升解的质量,采用NodeRank算法对EPSO-HC算法的种群进行初始化．

在EPSO-HC算法中,令cir为节点i和节点r的通信代价,则软硬件通信代价C(x)的计算公式为

(10)

式中,xi,xr分别表示节点i和节点r的软硬件划分．

定理1 软硬件通信代价C(x)的时间复杂度为O(n2)．

图3 EPSO-HC算法的流程图

证明 式(10)中包含2层循环,执行每一层循环的耗时为O(n2)．因此,软硬件通信代价C(x)的时间复杂度为O(n2)．

在EPSO-HC算法中,每次迭代都需要计算所有粒子的通信代价C(x)．由于C(x)的时间复杂度为O(n2),因此在EPSO-HC算法的计算过程中,软硬件通信代价的计算非常耗时．为了缩短运行时间,本文采用图形处理器(GPU)加速软硬件通信代价的计算过程．每次迭代过程中,N个软硬件通信代价在GPU并行环境中同时计算,从而有效减少EPSO-HC算法的整体运行时间．

4 试验结果与分析

4.1 软硬件划分的基准任务

本文通过求解23个软硬件划分任务来验证软硬件划分方法的性能．试验环境如下：计算机的内存为16 GB，处理器的型号为Intel(R) Core(TM) i7-4770；算法的开发工具为Matlab R2014b软件；GPU型号为NVIDIA GeForce GTX 780,共有2 304个流处理器,显存频率为6 008 MHz,显存容量为3 GB．

本文采用文献[6]中的参数设置,R取2种不同的约束值,令通信代价与软件代价之比Cr=0.1, 1,10．Cr和R取值不同时,可得到6种不同的算例(见表1)．参考文献[6],表2给出软硬件划分的基准任务,其中m为边数．

表1 6种不同的算例

表2 软硬件划分的基准任务

软硬件划分问题是一种NP困难问题．爬山法采用了贪心策略,在求解此类问题时容易陷入局部最优解．本文分别采用Alg-new3算法、Heur算法、NodeRank算法、PSO算法和EPSO-HC算法来求解表2中的软硬件划分基准任务．在EPSO-HC算法和PSO算法中,粒子数为40，最大迭代次数为50，惯性权重随迭代次数的增加在0.9和0.7之间线性递减，学习因子c1=c2=2．范围因子c3和搜索步长c4对EPSO-HC算法的性能影响较大,本文通过试验确定了这2个参数的取值分别为:c3=0.1,c4=0.8．HC算法的最大迭代次数为30,NodeRank算法的参数设置与文献[8]相同．为了不失一般性，本文随机选择100次的求解结果，据此分析软硬件划分算法的性能.

采用改进百分数来分析软硬件划分算法解的质量，算法A相对于算法B的改进百分数计算公式为

(11)

式中,hA,hB分别为算法A和算法B的硬件代价．在不同算例下,Heur算法、NodeRank算法、PSO算法和EPSO-HC算法相对于Alg-new3算法的100次试验平均硬件代价改进百分数τa见图4．

(a) 算例1

(b) 算例2

(c) 算例3

(d) 算例4

(e) 算例5

(f) 算例6

由图4可知,采用EPSO-HC算法得到的解优于其他算法的结果．当任务规模较小时,采用NodeRank算法、PSO算法和EPSO-HC算法得到的解几乎相同，这是因为此时软硬件划分问题的复杂度较低,NodeRank算法和PSO算法均可搜索到全局最优解．但随着任务规模的增加,求解软硬件划分优化问题的难度增大,EPSO-HC算法的改进百分数明显优于其他算法．

为了评价GPU并行加速的效果,比较了不同算法的运行时间．对于EPSO-HC算法,通信代价的计算过程在GPU并行环境中运行,其他算法则在串行环境中运行．当任务规模小于1.6×104时,算法的整体运行时间较短,GPU中数据交换和任务分配等额外操作占据了主要部分,GPU并行计算的优势不明显,EPSO-HC算法的运行时间大于PSO算法的运行时间;当任务规模大于等于1.6×104时,通信代价的计算非常耗时,采用GPU并行计算能缩短计算时间, EPSO-HC算法的运行时间明显少于PSO算法的运行时间．

4.2 特大规模软硬件划分任务

随着现代嵌入式系统的发展,软硬件划分问题的任务规模越来越大．为了进一步研究算法的性能,本文定义了9种典型的特大规模软硬件划分任务(见表3)．

表3 特大规模软硬件划分任务

采用Alg-new3算法、Heur算法、NodeRank算法、PSO算法和EPSO-HC算法来求解表3中的特大规模任务．本文选择在算例3下分析这几种算法的性能．图5给出了100次试验后不同算法的平均性能比较．

由图5可知,对于特大规模任务,EPSO-HC算法的全局搜索能力较强,相比其他算法,解的质量明显提升．采用GPU并行加速后,EPSO-HC算法和NodeRank算法的运行时间差距较小,EPSO-HC算法和PSO算法的运行时间差距较大．当任务规模为8×104时,EPSO-HC算法的运行时间较PSO算法减少43.76 s,占PSO运行时间的20.91%,并行加速效果明显．综上所示,针对23个软硬件划分任务,与其他软硬件划分算法相比,EPSO-HC算法解的质量更高,运行时间更少．因此,将EPSO-HC算法用于求解大规模软硬件划分问题是有效可行的．

(a) 平均硬件代价改进百分数

(b) 平均运行时间

5 结语

本文提出了一种用于求解大规模软硬件划分问题的爬山淘汰粒子群算法．在EPSO-HC算法中,模拟达尔文进化论,淘汰群体中当前全局最差位置附近的个体,保持了搜索种群的多样性,避免了算法的早熟收敛．通过改进爬山法的搜索方向,将HC算法集成到EPSO-HC算法中,提高了算法搜索的集中性,提升了解的质量．采用GPU并行加速软硬件通信代价的计算过程,有效地减少了算法的运行时间．

下一步研究将融合其他优化算法,持续提升EPSO-HC算法的性能,并将该算法应用到求解其他软硬件划分模型中．

References)

[1]Trindade A B, Cordeiro L C. Applying SMT-based verification to hardware/software partitioning in embedded systems[J].DesignAutomationforEmbeddedSystems, 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].ACMTransactionsonDesignAutomationofElectronicSystems, 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]//IEEE6thInternationalWorkshoponSystemonChipforRealTimeApplications. 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].DesignAutomationforEmbeddedSystems, 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]//The2ndInternationalConferenceonComputerResearchandDevelopment. 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].IEEETransactionsonComputers, 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].TheJournalofSupercomputing, 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].ChineseJournalofComputers, 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].NeuralComputingandApplications, 2016, 27(4): 989-1006. DOI:10.1007/s00521-015-1914-z.

[10]Vorzimmer P. Darwin, Malthus, and the theory of natural selection[J].JournaloftheHistoryofIdeas, 1969, 30(4): 527-542. DOI: 10.2307/2708609.

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

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)

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.

hardware/software partitioning; particle swarm optimization algorithm; hill climbing algorithm; communication cost; parallel computing

10.3969/j.issn.1001-0505.2017.02.005

2016-08-14. 作者简介: 鄢小虎(1986— )，男，博士生；何发智(联系人)，男，博士，教授，博士生导师，fzhe@whu.edu.cn.

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

鄢小虎,何发智,陈壹林.求解大规模软硬件划分问题的爬山淘汰粒子群算法[J].东南大学学报(自然科学版),2017,47(2):225-230.

10.3969/j.issn.1001-0505.2017.02.005.

TP301

A

1001-0505(2017)02-0225-06