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

(1武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室, 武漢 430072)(2武漢大學(xué)計(jì)算機(jī)學(xué)院, 武漢 430072)

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

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

(1武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室, 武漢 430072)(2武漢大學(xué)計(jì)算機(jī)學(xué)院, 武漢 430072)

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

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

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

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

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

1 模型定義

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

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

(1)

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

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

2 爬山淘汰粒子群算法

在標(biāo)準(zhǔn)粒子群算法中,N個(gè)粒子在D維目標(biāo)搜索空間中尋優(yōu),令第t個(gè)粒子的當(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ū)間中的隨機(jī)數(shù);c1,c2為學(xué)習(xí)因子;k為迭代次數(shù)．標(biāo)準(zhǔn)粒子群算法在求解復(fù)雜問(wèn)題時(shí)存在容易陷入局部最優(yōu)解和早熟收斂的問(wèn)題[9]．

2.1 淘汰粒子群算法

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

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

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

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

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

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

(7)

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

2.2 改進(jìn)爬山法

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

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

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

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

(8)

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

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

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

(9)

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

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

(10)

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

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

圖3 EPSO-HC算法的流程圖

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

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

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

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

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

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

表1 6種不同的算例

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

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

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

(11)

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

(a) 算例1

(b) 算例2

(c) 算例3

(d) 算例4

(e) 算例5

(f) 算例6

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

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

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

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

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

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

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

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

(b) 平均運(yùn)行時(shí)間

5 結(jié)語(yǔ)

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

下一步研究將融合其他優(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]陳志,武繼剛,宋國(guó)治,等. NodeRank:一種高效軟硬件劃分算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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. 作者簡(jiǎn)介: 鄢小虎(1986— )，男，博士生；何發(fā)智(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，fzhe@whu.edu.cn.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472289)、國(guó)家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目(2016YFC0106305).

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

10.3969/j.issn.1001-0505.2017.02.005.

TP301

A

1001-0505(2017)02-0225-06