鄢小虎 何發(fā)智 陳壹林

(1武漢大學(xué)軟件工程國家重點實驗室, 武漢 430072)(2武漢大學(xué)計算機學(xué)院, 武漢 430072)

求解大規(guī)模軟硬件劃分問題的爬山淘汰粒子群算法

鄢小虎 何發(fā)智 陳壹林

(1武漢大學(xué)軟件工程國家重點實驗室, 武漢 430072)(2武漢大學(xué)計算機學(xué)院, 武漢 430072)

為了求解大規(guī)模軟硬件劃分問題,提出了一種爬山淘汰粒子群算法(EPSO-HC)．首先,模擬達(dá)爾文進(jìn)化論,淘汰群體中當(dāng)前全局最差位置附近的個體,保持搜索種群的多樣性,防止算法早熟收斂;其次,改進(jìn)爬山法的搜索機制,以粒子自身經(jīng)歷的最優(yōu)位置為方向,在當(dāng)前全局最優(yōu)位置附近集中搜索,提升解的質(zhì)量;然后,采用圖形處理器并行計算軟硬件通信代價,以減少EPSO-HC算法的運行時間;最后,通過求解基準(zhǔn)任務(wù)和特大規(guī)模任務(wù)來評價EPSO-HC算法的性能．試驗結(jié)果表明,針對23個軟硬件劃分任務(wù),與其他軟硬件劃分算法相比,所提算法解的質(zhì)量更高,運行時間更少．

軟硬件劃分;粒子群優(yōu)化算法;爬山法;通信代價;并行計算

現(xiàn)代嵌入式系統(tǒng)是軟件和硬件一體化的系統(tǒng),系統(tǒng)的任務(wù)由硬件實現(xiàn)(如FPGA,ASIC等)和軟件實現(xiàn)(如ARM,DSP等)協(xié)同完成．硬件實現(xiàn)速度快,但成本較高;軟件實現(xiàn)的代價低,但需要耗費更多的時間[1]．軟硬件劃分是指在滿足一定的約束條件下，將系統(tǒng)功能合理地分配到軟件實現(xiàn)或硬件實現(xiàn)上.

目前，求解軟硬件劃分問題的方法分為精確算法和啟發(fā)式算法2類[2].粒子群算法實現(xiàn)容易且收斂速度快，已成功應(yīng)用于求解軟硬件劃分的問題中.在硬件代價和求解時間方面，文獻(xiàn)[3]指出基于粒子群算法的軟硬件劃分方法優(yōu)于遺傳算法.文獻(xiàn)[4]將再啟動技術(shù)引入粒子群算法，以求解軟硬件劃分問題.文獻(xiàn)[5]融合粒子群算法和禁忌搜索算法，求解軟硬件劃分問題.然而，隨著嵌入式系統(tǒng)設(shè)計規(guī)模的逐漸增大，現(xiàn)有的啟發(fā)式算法已難以獲取最優(yōu)解.

本文提出了一種爬山淘汰粒子群算法(EPSO-HC)來求解大規(guī)模軟硬件劃分問題,通過模擬達(dá)爾文進(jìn)化論,增加搜索種群的多樣性;通過更新當(dāng)前全局最優(yōu)位置,增強搜索的集中性．

1 模型定義

本文采用文獻(xiàn)[6]中的軟硬件劃分模型.在無向圖G=(V,E)中,V和E分別表示節(jié)點和邊的集合．軟硬件劃分問題可以描述為

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

(1)

式中,x={x1,x2,…,xn}表示軟硬件劃分問題的一個解;C(x)表示軟硬件劃分x的通信代價;si和hi分別表示節(jié)點vi的軟件代價和硬件代價;xi=1表示節(jié)點i由軟件實現(xiàn),xi=0表示節(jié)點i由硬件實現(xiàn);R為約束值．

文獻(xiàn)[6]提出了3種啟發(fā)式的一維搜索算法來求解式(1),其中Alg-new3算法性能最佳．文獻(xiàn)[7-8] 針對式(1),分別提出了啟發(fā)式的Heur算法和基于迭代排序思想的NodeRank算法．

2 爬山淘汰粒子群算法

在標(biāo)準(zhǔn)粒子群算法中,N個粒子在D維目標(biāo)搜索空間中尋優(yōu),令第t個粒子的當(dāng)前位置Xt,速度Vt和自身經(jīng)歷的最優(yōu)位置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．

將群體中當(dāng)前全局最優(yōu)的位置記為Pg={Pg1,Pg2,…,PgD},則粒子群算法的進(jìn)化方程為

(5)

(6)

式中,w為慣性權(quán)重;r1,r2為[0,1]區(qū)間中的隨機數(shù);c1,c2為學(xué)習(xí)因子;k為迭代次數(shù)．標(biāo)準(zhǔn)粒子群算法在求解復(fù)雜問題時存在容易陷入局部最優(yōu)解和早熟收斂的問題[9]．

2.1 淘汰粒子群算法

根據(jù)達(dá)爾文進(jìn)化論,物競天擇,適者生存,生物間互相競爭,能適應(yīng)環(huán)境者被選擇存留下來,不能適應(yīng)環(huán)境者將被淘汰[10]．本文通過模擬達(dá)爾文進(jìn)化論,淘汰群體中不能適應(yīng)環(huán)境的弱小粒子．

定義1(不能適應(yīng)環(huán)境者) 將不能適應(yīng)環(huán)境者定義為群體中弱小的個體．

定義2(弱小的粒子) 將弱小的粒子定義為群體中當(dāng)前全局最差位置附近的粒子．

在淘汰粒子群算法中,模擬達(dá)爾文進(jìn)化論,淘汰當(dāng)前全局最差位置附近的弱小粒子,由隨機產(chǎn)生的粒子替代．在群體中,將當(dāng)前全局最差位置定義為Pw={Pw1,Pw2,…,PwD},第j個弱小粒子的位置為Yj={Yj1,Yj2,…,YjD}．由于弱小粒子在全局最差位置的附近,則Yj和Pw之間的關(guān)系如圖1所示．

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

在圖1中,Yj-1,Yj和Yj+1為弱小粒子的位置．Yj在以Pw為中心的圓圈內(nèi),則

(7)

式中,c3為范圍因子;Ra為粒子的搜索半徑．在淘汰粒子群算法中,隨機產(chǎn)生的新粒子替代弱小的粒子,能增加搜索種群的多樣性,防止算法早熟收斂．

2.2 改進(jìn)爬山法

爬山法(HC)是一種常用的貪心搜索算法．該算法在當(dāng)前解的鄰域內(nèi)進(jìn)行搜索,若候選解優(yōu)于當(dāng)前解,則用該解替代當(dāng)前解;反之則搜索另外一個解再進(jìn)行比較,直到滿足終止條件時為止．

本文采用爬山法在當(dāng)前全局最優(yōu)位置Pg附近尋優(yōu),利用搜索到的更優(yōu)位置替代Pg．爬山法的搜索方向是隨機的,因此該方法的搜索過程盲目且效率較低．本文改進(jìn)了爬山法的搜索方向,從粒子群自身最優(yōu)位置Pi中隨機取l個點作為算法的搜索方向,改進(jìn)爬山法的搜索過程示意圖如圖2所示．

圖2 改進(jìn)爬山法的搜索過程示意圖

對于當(dāng)前全局最優(yōu)位置,改進(jìn)爬山法向前搜索的位置為

(8)

改進(jìn)爬山法循環(huán)向前搜索,直到將l個方向搜索完,算法結(jié)束．利用改進(jìn)爬山法更新當(dāng)前全局最優(yōu)位置,能夠提升解的質(zhì)量，增強搜索的集中性．

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

軟硬件劃分問題屬于組合最優(yōu)化問題,求解時需要采用離散的EPSO-HC算法．本文采用如下公式對每個粒子的位置進(jìn)行離散化:

(9)

采用離散的EPSO-HC算法來求解式(1),圖3為EPSO-HC算法的流程圖．為了提升解的質(zhì)量,采用NodeRank算法對EPSO-HC算法的種群進(jìn)行初始化．

在EPSO-HC算法中,令cir為節(jié)點i和節(jié)點r的通信代價,則軟硬件通信代價C(x)的計算公式為

(10)

式中,xi,xr分別表示節(jié)點i和節(jié)點r的軟硬件劃分．

定理1 軟硬件通信代價C(x)的時間復(fù)雜度為O(n2)．

圖3 EPSO-HC算法的流程圖

證明 式(10)中包含2層循環(huán),執(zhí)行每一層循環(huán)的耗時為O(n2)．因此,軟硬件通信代價C(x)的時間復(fù)雜度為O(n2)．

在EPSO-HC算法中,每次迭代都需要計算所有粒子的通信代價C(x)．由于C(x)的時間復(fù)雜度為O(n2),因此在EPSO-HC算法的計算過程中,軟硬件通信代價的計算非常耗時．為了縮短運行時間,本文采用圖形處理器(GPU)加速軟硬件通信代價的計算過程．每次迭代過程中,N個軟硬件通信代價在GPU并行環(huán)境中同時計算,從而有效減少EPSO-HC算法的整體運行時間．

4 試驗結(jié)果與分析

4.1 軟硬件劃分的基準(zhǔn)任務(wù)

本文通過求解23個軟硬件劃分任務(wù)來驗證軟硬件劃分方法的性能．試驗環(huán)境如下：計算機的內(nèi)存為16 GB，處理器的型號為Intel(R) Core(TM) i7-4770；算法的開發(fā)工具為Matlab R2014b軟件；GPU型號為NVIDIA GeForce GTX 780,共有2 304個流處理器,顯存頻率為6 008 MHz,顯存容量為3 GB．

本文采用文獻(xiàn)[6]中的參數(shù)設(shè)置,R取2種不同的約束值,令通信代價與軟件代價之比Cr=0.1, 1,10．Cr和R取值不同時,可得到6種不同的算例(見表1)．參考文獻(xiàn)[6],表2給出軟硬件劃分的基準(zhǔn)任務(wù),其中m為邊數(shù)．

表1 6種不同的算例

表2 軟硬件劃分的基準(zhǔn)任務(wù)

軟硬件劃分問題是一種NP困難問題．爬山法采用了貪心策略,在求解此類問題時容易陷入局部最優(yōu)解．本文分別采用Alg-new3算法、Heur算法、NodeRank算法、PSO算法和EPSO-HC算法來求解表2中的軟硬件劃分基準(zhǔn)任務(wù)．在EPSO-HC算法和PSO算法中,粒子數(shù)為40，最大迭代次數(shù)為50，慣性權(quán)重隨迭代次數(shù)的增加在0.9和0.7之間線性遞減，學(xué)習(xí)因子c1=c2=2．范圍因子c3和搜索步長c4對EPSO-HC算法的性能影響較大,本文通過試驗確定了這2個參數(shù)的取值分別為:c3=0.1,c4=0.8．HC算法的最大迭代次數(shù)為30,NodeRank算法的參數(shù)設(shè)置與文獻(xiàn)[8]相同．為了不失一般性，本文隨機選擇100次的求解結(jié)果，據(jù)此分析軟硬件劃分算法的性能.

采用改進(jìn)百分?jǐn)?shù)來分析軟硬件劃分算法解的質(zhì)量，算法A相對于算法B的改進(jìn)百分?jǐn)?shù)計算公式為

(11)

式中,hA,hB分別為算法A和算法B的硬件代價．在不同算例下,Heur算法、NodeRank算法、PSO算法和EPSO-HC算法相對于Alg-new3算法的100次試驗平均硬件代價改進(jìn)百分?jǐn)?shù)τa見圖4．

(a) 算例1

(b) 算例2

(c) 算例3

(d) 算例4

(e) 算例5

(f) 算例6

由圖4可知,采用EPSO-HC算法得到的解優(yōu)于其他算法的結(jié)果．當(dāng)任務(wù)規(guī)模較小時,采用NodeRank算法、PSO算法和EPSO-HC算法得到的解幾乎相同，這是因為此時軟硬件劃分問題的復(fù)雜度較低,NodeRank算法和PSO算法均可搜索到全局最優(yōu)解．但隨著任務(wù)規(guī)模的增加,求解軟硬件劃分優(yōu)化問題的難度增大,EPSO-HC算法的改進(jìn)百分?jǐn)?shù)明顯優(yōu)于其他算法．

為了評價GPU并行加速的效果,比較了不同算法的運行時間．對于EPSO-HC算法,通信代價的計算過程在GPU并行環(huán)境中運行,其他算法則在串行環(huán)境中運行．當(dāng)任務(wù)規(guī)模小于1.6×104時,算法的整體運行時間較短,GPU中數(shù)據(jù)交換和任務(wù)分配等額外操作占據(jù)了主要部分,GPU并行計算的優(yōu)勢不明顯,EPSO-HC算法的運行時間大于PSO算法的運行時間;當(dāng)任務(wù)規(guī)模大于等于1.6×104時,通信代價的計算非常耗時,采用GPU并行計算能縮短計算時間, EPSO-HC算法的運行時間明顯少于PSO算法的運行時間．

4.2 特大規(guī)模軟硬件劃分任務(wù)

隨著現(xiàn)代嵌入式系統(tǒng)的發(fā)展,軟硬件劃分問題的任務(wù)規(guī)模越來越大．為了進(jìn)一步研究算法的性能,本文定義了9種典型的特大規(guī)模軟硬件劃分任務(wù)(見表3)．

表3 特大規(guī)模軟硬件劃分任務(wù)

采用Alg-new3算法、Heur算法、NodeRank算法、PSO算法和EPSO-HC算法來求解表3中的特大規(guī)模任務(wù)．本文選擇在算例3下分析這幾種算法的性能．圖5給出了100次試驗后不同算法的平均性能比較．

由圖5可知,對于特大規(guī)模任務(wù),EPSO-HC算法的全局搜索能力較強,相比其他算法,解的質(zhì)量明顯提升．采用GPU并行加速后,EPSO-HC算法和NodeRank算法的運行時間差距較小,EPSO-HC算法和PSO算法的運行時間差距較大．當(dāng)任務(wù)規(guī)模為8×104時,EPSO-HC算法的運行時間較PSO算法減少43.76 s,占PSO運行時間的20.91%,并行加速效果明顯．綜上所示,針對23個軟硬件劃分任務(wù),與其他軟硬件劃分算法相比,EPSO-HC算法解的質(zhì)量更高,運行時間更少．因此,將EPSO-HC算法用于求解大規(guī)模軟硬件劃分問題是有效可行的．

(a) 平均硬件代價改進(jìn)百分?jǐn)?shù)

(b) 平均運行時間

5 結(jié)語

本文提出了一種用于求解大規(guī)模軟硬件劃分問題的爬山淘汰粒子群算法．在EPSO-HC算法中,模擬達(dá)爾文進(jìn)化論,淘汰群體中當(dāng)前全局最差位置附近的個體,保持了搜索種群的多樣性,避免了算法的早熟收斂．通過改進(jìn)爬山法的搜索方向,將HC算法集成到EPSO-HC算法中,提高了算法搜索的集中性,提升了解的質(zhì)量．采用GPU并行加速軟硬件通信代價的計算過程,有效地減少了算法的運行時間．

下一步研究將融合其他優(yōu)化算法,持續(xù)提升EPSO-HC算法的性能,并將該算法應(yīng)用到求解其他軟硬件劃分模型中．

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]. 計算機學(xué)報, 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— )，男，博士生；何發(fā)智(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，fzhe@whu.edu.cn.

國家自然科學(xué)基金資助項目(61472289)、國家重點研發(fā)計劃資助項目(2016YFC0106305).

鄢小虎,何發(fā)智,陳壹林.求解大規(guī)模軟硬件劃分問題的爬山淘汰粒子群算法[J].東南大學(xué)學(xué)報(自然科學(xué)版),2017,47(2):225-230.

10.3969/j.issn.1001-0505.2017.02.005.

TP301

A

1001-0505(2017)02-0225-06