盧　晨，毛樂樂，黃　勇

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

?

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

盧晨a，毛樂樂a，黃勇b

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

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

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

0　引言

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

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

為便于求解軟硬件劃分問題，首先將劃分問題轉換成標準0-1背包問題，然后利用混合蛙跳算法求解0-1背包問題，從而實現(xiàn)對軟硬件劃分問題的求解，最后通過實驗證明該方法的有效性和可行性.

1　軟硬件劃分問題的數(shù)學模型

1.1軟硬件劃分問題

求解軟硬件劃分問題時，通常使用無向圖來描述任務流圖.

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

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

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

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

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

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

(1)

(2)

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

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

(3)

(4)

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

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

(5)

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

(6)

1.20-1背包問題

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

(7)

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

2　混合蛙跳算法

2.1算法原理

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

2.2算法描述

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

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

Step2：隨機產生初始蛙群，計算各個蛙的適應值.

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

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

Step5：輸出xg(t).

3　仿真實驗

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

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

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

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

圖1　SFLA與ACO算法收斂性圖

實例2i=20，c=878，硬件代價hi={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58}，軟件代價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，文獻[7]采用蟻群算法求解，經過200次迭代得最優(yōu)解為1024.運行蜂群算法，60次迭代后可得最好解為1024，采用本文提出的混合蛙跳算法只需28次迭代即可得到最優(yōu)解1024.與蜂群算法的對比結果如圖2所示：

圖2　SFLA與ABC算法收斂性圖

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

表1　不同方法在實例3上的統(tǒng)計結果

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

4　結語

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

[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 ]劉功杰，張魯峰，李思昆.遺傳算法在軟硬件劃分中的應用[J].國防科技大學學報.2002,24(2):64-68.

[5] 鄒誼，莊鎮(zhèn)泉，李斌.基于量子遺傳算法的嵌入式系統(tǒng)軟硬件劃分算法[J].電路與系統(tǒng)學報,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] .計算機輔助設計與圖形學報, 2010,22(6):927-933.

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

[10]趙洋，單娟.二進制混合蛙跳算法秋季0-1背包問題[J].計算機工程與應用，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背包問題的螢火蟲群優(yōu)化算法[J].計算機應用研究，2013(4):993-995.

[責任編輯蘇琴]

[責任校對黃招揚]

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技術研究重點項目(2013ZD021)；廣西民族大學2015年研究生教育創(chuàng)新計劃項目(gxun-chxs2015097).

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

TP302

A

1673-8462(2016)02-0073-04