基于混合蛙跳算法的軟硬件劃分方法*

盧　晨，毛樂(lè)樂(lè)，黃　勇

(廣西民族大學(xué)，a.信息科學(xué)與工程學(xué)院;b.網(wǎng)絡(luò)與信息化管理中心，廣西 南寧　530006)

?

基于混合蛙跳算法的軟硬件劃分方法*

盧晨a，毛樂(lè)樂(lè)a，黃勇b

(廣西民族大學(xué)，a.信息科學(xué)與工程學(xué)院;b.網(wǎng)絡(luò)與信息化管理中心，廣西 南寧530006)

軟硬件劃分問(wèn)題是嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計(jì)的關(guān)鍵問(wèn)題，劃分結(jié)果的好壞直接影響著系統(tǒng)性能的優(yōu)劣.將軟硬件劃分問(wèn)題轉(zhuǎn)化成0-1背包問(wèn)題，提出了一種基于混合蛙跳算法求解軟硬件劃分問(wèn)題的方法.該方法在求解軟硬件劃分問(wèn)題的過(guò)程中，不斷地尋找更優(yōu)可行解，逐漸達(dá)到搜索全局最優(yōu)解，使得系統(tǒng)的軟硬件實(shí)現(xiàn)總代價(jià)最小.實(shí)驗(yàn)結(jié)果表明，該方法能很好求解軟硬件劃分問(wèn)題，所應(yīng)用算法的收斂速度明顯優(yōu)于對(duì)比算法.

軟硬件協(xié)同設(shè)計(jì)；軟硬件劃分；混合蛙跳算法；啟發(fā)式算法

0　引言

嵌入式系統(tǒng)設(shè)計(jì)中，系統(tǒng)組件功能可由軟件或硬件實(shí)現(xiàn)，軟件實(shí)現(xiàn)具有成本低、配置靈活的優(yōu)點(diǎn)，但執(zhí)行速度慢；硬件實(shí)現(xiàn)執(zhí)行效率高，功耗小，但成本高[1].早期的嵌入式系統(tǒng)規(guī)模小，功能簡(jiǎn)單，設(shè)計(jì)人員憑借經(jīng)驗(yàn)實(shí)現(xiàn)軟硬件劃分在一定程度上可以滿足設(shè)計(jì)需求.隨著嵌入式系統(tǒng)應(yīng)用需求的日益增長(zhǎng)，系統(tǒng)較之前更為龐大復(fù)雜，設(shè)計(jì)周期也越來(lái)越短，科學(xué)合理的軟硬件劃分方法顯得尤為重要.因此，軟硬件劃分成為嵌入式系統(tǒng)軟硬協(xié)同設(shè)計(jì)中的首要問(wèn)題，其主要目標(biāo)是如何兼顧系統(tǒng)的性能和成本，達(dá)到兩者的最佳結(jié)合.

近年來(lái)，國(guó)內(nèi)外已經(jīng)對(duì)關(guān)于軟硬件劃分的問(wèn)題進(jìn)行了大量的研究，軟硬件問(wèn)題已經(jīng)被證明為NP問(wèn)題[1-3]，已有的解決方法主要有兩類算法：精確算法和啟發(fā)式算法.精確算法有整數(shù)線性規(guī)劃、動(dòng)態(tài)規(guī)劃算法等規(guī)劃類方法，這類算法沒(méi)有明確的目標(biāo)函數(shù)，約束條件多，計(jì)算時(shí)間復(fù)雜度較高，計(jì)算時(shí)間會(huì)很長(zhǎng)，一般用于較小規(guī)模的劃分問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)，并不適用.啟發(fā)式算法可廣泛應(yīng)用于求解規(guī)模較大的劃分問(wèn)題，例如遺傳算法(GA)[4]，量子遺傳算法(QGA)[5]，混合量子遺傳算法(HQGA)[6]，粒子群優(yōu)化算法(PSO)[7-8]等智能優(yōu)化算法.其中，混合蛙跳算法[9-10]是一種新興的基于群智能的亞啟發(fā)式智能優(yōu)化算法, 該算法具有概念簡(jiǎn)單，參數(shù)少，計(jì)算速度快，全局搜索尋優(yōu)能力強(qiáng)，易于實(shí)現(xiàn)的特點(diǎn).目前，尚未看到利用混合蛙跳算法求解軟硬件劃分問(wèn)題的研究工作.

為便于求解軟硬件劃分問(wèn)題，首先將劃分問(wèn)題轉(zhuǎn)換成標(biāo)準(zhǔn)0-1背包問(wèn)題，然后利用混合蛙跳算法求解0-1背包問(wèn)題，從而實(shí)現(xiàn)對(duì)軟硬件劃分問(wèn)題的求解，最后通過(guò)實(shí)驗(yàn)證明該方法的有效性和可行性.

1　軟硬件劃分問(wèn)題的數(shù)學(xué)模型

1.1軟硬件劃分問(wèn)題

求解軟硬件劃分問(wèn)題時(shí)，通常使用無(wú)向圖來(lái)描述任務(wù)流圖.

定義1R={R1，R2，…，Rn}代表劃分系統(tǒng)的所有任務(wù)節(jié)點(diǎn)集合,其中Ri表示第i個(gè)任務(wù)節(jié)點(diǎn)，其中i=1,2,…,n.圖中的一個(gè)節(jié)點(diǎn)就是對(duì)應(yīng)劃分系統(tǒng)的一個(gè)任務(wù)，每個(gè)節(jié)點(diǎn)包含其軟件、硬件代價(jià)信息.

定義2系統(tǒng)總代價(jià)由軟件代價(jià)和硬件代價(jià)組成，即系統(tǒng)總代價(jià)為軟件代價(jià)與硬件代價(jià)之和.

定義3軟硬件劃分問(wèn)題中x=(x1,x2,…,xn)是劃分系統(tǒng)任務(wù)流圖的一個(gè)可行解，代表對(duì)系統(tǒng)的一種劃分，xi∈{0,1}，xi=1代表Ri由軟件實(shí)現(xiàn)，xi=0代表Ri由硬件實(shí)現(xiàn)，其中i代表第i個(gè)節(jié)點(diǎn), i=1,2,…,n.

定義4劃分系統(tǒng)中的任務(wù)可由軟件實(shí)現(xiàn)，也可由硬件實(shí)現(xiàn)，但不可同時(shí)由軟件和硬件實(shí)現(xiàn).

在軟硬件劃分中將原節(jié)點(diǎn)集合R={R1,R2,…,Rn}劃分為兩個(gè)子集，即Q=(Rh,RS)，其中Rh∪RS=R且Rh∩RS=Φ.其中Rh表示任務(wù)節(jié)點(diǎn)交由硬件實(shí)現(xiàn)，RS表示任務(wù)節(jié)點(diǎn)交由軟件實(shí)現(xiàn).

系統(tǒng)劃分后總的軟件代價(jià)、硬件代價(jià)分別表示為公式(1)、公式(2).

(1)

(2)

軟硬件劃分問(wèn)題：給定一個(gè)任務(wù)流程圖以及軟件代價(jià)函數(shù)s(x)硬件代價(jià)函數(shù)h(x)和約束C，求解軟硬件劃分，在滿足SR≤C情況下，使得HR最小，即軟件在約束范圍內(nèi)使得硬件的代價(jià)消耗最小.

x=(x1,x2,…,xn)是劃分系統(tǒng)進(jìn)行劃分后的一個(gè)可行解，xi=1表示Ri由軟件實(shí)現(xiàn)，xi=0表示Ri由硬件實(shí)現(xiàn)，經(jīng)過(guò)劃分后的系統(tǒng)硬件代價(jià)h(x)、軟件代價(jià)s(x)可以分別表示為公式(3)、公式(4).

(3)

(4)

式中si與hi分別表示第i個(gè)任務(wù)節(jié)點(diǎn)交給軟件和硬件實(shí)現(xiàn)所花費(fèi)的代價(jià).

將軟硬件劃分問(wèn)題形式化描述為公式(5).

(5)

將公式(5)簡(jiǎn)單變形后得公式(6).

(6)

1.20-1背包問(wèn)題

0-1背包問(wèn)題(KnapsackProblem)是一種組合優(yōu)化的NP問(wèn)題.給定多個(gè)重量和價(jià)值不同的物品和一個(gè)背包，從不同重量和價(jià)值的物品中選擇裝入容量有限的背包使得裝入背包中物品的總價(jià)值最大.在選擇裝入背包的物品時(shí)，對(duì)每種物品i只能選擇裝入背包或不裝入背包，不允許將物品i部分裝入背包，也不允許將物品i多次裝入背包，在背包問(wèn)題中假設(shè)物品的重量是wi>0,其價(jià)值為vi>0，背包的容量為k>0，xi∈{0,1}，當(dāng)xi=1時(shí)表示物品裝入背包，否則不裝入背包，使得背包所裝入的物品重量小于一個(gè)背包的容量，即wi*xi≤k,而且要使得背包所裝入物品的價(jià)值盡量最大化，即使得V=vi*xi達(dá)到最大，形式化描述如公式(7).

(7)

顯然，式(7)與式(6)可以進(jìn)行等價(jià)的變換，即將軟硬件劃分問(wèn)題的硬件代價(jià)hi，軟件代價(jià)si，約束參數(shù)c分別對(duì)應(yīng)0-1背包問(wèn)題中的物品價(jià)值bi，物品重量wi，背包容量k，則說(shuō)明軟硬件劃分問(wèn)題可以看成0-1背包問(wèn)題進(jìn)行解決.于是解決0-1背包問(wèn)題的算法也可以應(yīng)用到軟硬件劃分問(wèn)題.

2　混合蛙跳算法

2.1算法原理

混合蛙跳算法[9](SFLA)是由EusuffM.M和Lansey提出的一種亞啟發(fā)式群智能進(jìn)化算法，它的執(zhí)行過(guò)程模擬了一群青蛙在濕地中跳動(dòng)覓食的自然界元進(jìn)化行為.該算法的原理為種群中每只蛙代表一個(gè)解，濕地代表解空間，在算法的初期，一群蛙被分成m個(gè)規(guī)模為n的子群，不同的子群.根據(jù)適應(yīng)度值大小找到組內(nèi)位置最好和最差的青蛙，位置最差的蛙采用一定的進(jìn)化方法，首先用子群最好的個(gè)體與最差的個(gè)體產(chǎn)生新的個(gè)體，對(duì)最差蛙的位置進(jìn)行調(diào)整，可視為一次跳躍，如果新的子個(gè)體的適應(yīng)度比父代個(gè)體優(yōu)，則子個(gè)體替代父代個(gè)體，否則利用全局最優(yōu)的個(gè)體與最差的個(gè)體產(chǎn)生新的個(gè)體，可視為再次跳躍，如果新的子個(gè)體的適應(yīng)度比父代個(gè)體優(yōu)，則子個(gè)體替代父代個(gè)體，否則將隨機(jī)產(chǎn)生新個(gè)體替代最差的個(gè)體.在達(dá)到預(yù)先定義的局部搜索迭代次數(shù)之后，這一過(guò)程不斷重復(fù)直到預(yù)先定義的收斂條件得到滿足.

2.2算法描述

設(shè)SFLA算法的第t代種群P(t)的規(guī)模為N，分為m個(gè)規(guī)模為n的子群為Pk(t)(1≤k≤m)，N=m*n，每一只青蛙的個(gè)體表示為xi(t)=(xi1(t)，xi2(t),…,xid(t))，(l≤j≤d)其中下界為L(zhǎng)=(l1,l2,l3,…,li)，上界為U=(u1,u2,…,ui)，(1≤i≤N)，設(shè)xb(t)和xw(t)分別為子群pk(t)的最優(yōu)個(gè)體和最差個(gè)體，xg(t)為種群p(t)的全局最優(yōu)個(gè)體，令temp=(y1,y2,…,yd)為一臨時(shí)向量，R1為(0,1)中的一個(gè)隨機(jī)數(shù)，R2為(0,1)中的一個(gè)隨機(jī)數(shù)，c1,c2為(1,2)的一個(gè)隨機(jī)數(shù)，w為1.17.算法的實(shí)現(xiàn)流程如下：

Step1：參數(shù)初始化.確定蛙群的數(shù)量、種群以及每個(gè)種群的青蛙數(shù).

Step2：隨機(jī)產(chǎn)生初始蛙群，計(jì)算各個(gè)蛙的適應(yīng)值.

Step3：按適應(yīng)值大小進(jìn)行降序排序并記錄全局最優(yōu)解xg(t),子群最優(yōu)解xb(t)和最差解xw(t).

Step4：根據(jù)種群P(t+1)個(gè)體f(temp.a[i])的值降序重新排列，重新構(gòu)成子群Pk(t+1)(1≤k≤m)并對(duì)其進(jìn)行評(píng)估，更新子群中的xb(t+1),xw(t+1), xg(t+1).

Step5：輸出xg(t).

3　仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境為32位Windows7，CPU：Intel(R)Core(TM)i5-3470，RAM：4.00GB，所使用的編程語(yǔ)言為C++.

由于嵌入式系統(tǒng)軟硬件劃分問(wèn)題可以建模轉(zhuǎn)換成0-1背包問(wèn)題，那么應(yīng)用于0-1背包問(wèn)題的測(cè)試基準(zhǔn)同樣適用于軟硬件劃分問(wèn)題.本文分別給出3個(gè)實(shí)例，其中實(shí)例1、2選自文獻(xiàn)[12]，實(shí)例3選自文獻(xiàn)[7].

實(shí)例1i=10，c=269，硬件代價(jià)hi={55,10,47,5,4,50,8,61,85,87}，軟件代價(jià)si={95,4,60,32,23,72,80,62,65,46}.

回溯算法和e-近似算法[11]可解得到最優(yōu)值295，蟻群算法則要迭代100多次以后可得到最優(yōu)解，運(yùn)行人工螢火蟲(chóng)群算法[12]，迭代20次后得到最優(yōu)解，運(yùn)行混合群算法，迭代2次就可以得到最優(yōu)解.與蟻群算法對(duì)比結(jié)果如圖1所示：

圖1　SFLA與ACO算法收斂性圖

實(shí)例2i=20，c=878，硬件代價(jià)hi={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58}，軟件代價(jià)si={44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}

回溯算法解得最優(yōu)值為1024，e-近似算法解得近似值1018，蟻群算法和蜂群算法可得到的最好解為1024，文獻(xiàn)[7]采用蟻群算法求解，經(jīng)過(guò)200次迭代得最優(yōu)解為1024.運(yùn)行蜂群算法，60次迭代后可得最好解為1024，采用本文提出的混合蛙跳算法只需28次迭代即可得到最優(yōu)解1024.與蜂群算法的對(duì)比結(jié)果如圖2所示：

圖2　SFLA與ABC算法收斂性圖

實(shí)例3i=20，硬件代價(jià)hi={91,2,43,83,84,85,65,96,87,8,49,30,19,58,87,26,95,74,43,12,51}，軟件代價(jià)si={41,42,93,74,95,46,77,38,9,50,79,48,77,16,65,14,73,22,71,60}，對(duì)比粒子群算法和混合蛙跳算法得如表1所示.

表1　不同方法在實(shí)例3上的統(tǒng)計(jì)結(jié)果

對(duì)比表1中的統(tǒng)計(jì)數(shù)據(jù)可以得出，迭代次數(shù)范圍在1～100之間，運(yùn)用粒子群算法和混合蛙跳算法求得0-1背包問(wèn)題最優(yōu)值相近，迭代次數(shù)為100～200范圍內(nèi)，混合蛙跳算法求得的0-1背包問(wèn)題最優(yōu)值明顯優(yōu)于粒子群算法.

4　結(jié)語(yǔ)

借鑒解決0-1背包問(wèn)題的思路，結(jié)合混合蛙跳算法的優(yōu)勢(shì)，本文提出了一種基于混合蛙跳算法求解軟硬件劃分問(wèn)題的新方法.實(shí)驗(yàn)表明，該方法具有可行性和有效性，在工程實(shí)際中有一定的應(yīng)用價(jià)值.下一步的研究工作是進(jìn)一步改進(jìn)該算法，拓寬該算法的應(yīng)用領(lǐng)域.

[1]P.Arato, S.Juhasz, Z.A.Mann. Hardware- software partitioning in embedded system design[A].WISP2003,Budapest,Hungary,Septem-ber 2003:197-222.

[2]R. K. Gupta. Co-synthesis of hardware and software for digital embedded systems[D].PhD thesis, Stanford University, December 1993.

[3]R.Ernst,J.Henkel,T.Benner.Hardware-software co-synthesis for micro-controllers[J]. IEEE Design Test Comput.1993,10(4):64-75.

[4 ]劉功杰，張魯峰，李思昆.遺傳算法在軟硬件劃分中的應(yīng)用[J].國(guó)防科技大學(xué)學(xué)報(bào).2002,24(2):64-68.

[5] 鄒誼，莊鎮(zhèn)泉，李斌.基于量子遺傳算法的嵌入式系統(tǒng)軟硬件劃分算法[J].電路與系統(tǒng)學(xué)報(bào),2004,9(5):1-7.

[6]R.Guo,B.Li,Y.Zou,Z.Zhuang. Hybrid quan turn probabilistic coding genetic algorithm for large scale hardware-software co-synthesis of embedded system [J].IEEE Congress on Evolutionary Computation,2007:3454-3458.

[7]FARMAHINI-FARAHANIA,KAMALA,FAKHRAIESM,etal.HW/SW partitioning using discrete particle swarm[C]//Proceed-ingsofthe 17thACM Great Lakes Symposium on VLSI. NewYork:ACM Press, 2007: 359- 364.

[8]劉安,馮金富,梁曉龍,等. 基于遺傳粒子群優(yōu)化的嵌入式系統(tǒng)軟硬件劃分算法[J] .計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào), 2010,22(6):927-933.

[9]胥楓,張桂珠,趙芳,等,一種具有領(lǐng)導(dǎo)機(jī)制的混合蛙跳優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究, 2014(7).

[10]趙洋，單娟.二進(jìn)制混合蛙跳算法秋季0-1背包問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(35):39-44.

[11] MA Qiang，YOUNG E F Y．Voltage island-driven floor planning[C]//Proc of IEEE/ACM International Conference on Computer-Aided Design．Piscataway: IEEE Press，2007: 644-649．

[12]程魁，馬良.0-1背包問(wèn)題的螢火蟲(chóng)群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013(4):993-995.

[責(zé)任編輯蘇琴]

[責(zé)任校對(duì)黃招揚(yáng)]

Hardware/Software Partitioning based on Shuffled Frog Leaping Algorithm

LU Chena，MAO Le-lea，HUANG Yongb

(a.CollegeofInformationScienceandEngineering;b.NetworkandInformationManagementCenter,GuangxiUniversityforNationalities,Nanning530006,China)

Hardware and software partitioning is a key problem in the co-design of hardware and software of embedded system, which affects the performance of the system. In this paper, we present a new method based on shuffled frog leaping algorithm(SFLA) for solving the hardware/software partitioning problem, which is formulated as a 0-1 knapsack problem. The SFLA algorithm can keep looking for more optimal feasible solution, and gradually to search the global optimal solution, which makes the minimal total cost of hardware and software development. Experimental results show that our method is feasible for the hardware/software partitioning, and has much better convergence rate than the contrast algorithms.

hardware/software co-design; hardware/software partitioning; shuffled frog leaping algorithm; heuristic algorithm

2015-10-20.

廣西高?？茖W(xué)技術(shù)研究重點(diǎn)項(xiàng)目(2013ZD021)；廣西民族大學(xué)2015年研究生教育創(chuàng)新計(jì)劃項(xiàng)目(gxun-chxs2015097).

盧晨(1991-)，女，江西贛州人，廣西民族大學(xué)碩士研究生，研究方向：可信系統(tǒng)驗(yàn)證與分析、網(wǎng)絡(luò)與信息安全；毛樂(lè)樂(lè)(1989-)，男，河北衡水人，廣西民族大學(xué)碩士研究生，研究方向：大規(guī)模集成電路驗(yàn)證.

TP302

A

1673-8462(2016)02-0073-04