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

盧　晨，毛樂樂，黃　勇

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

?

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

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

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

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

軟硬件協同設計；軟硬件劃分；混合蛙跳算法；啟發式算法

0　引言

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

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

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

1　軟硬件劃分問題的數學模型

1.1軟硬件劃分問題

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

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

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

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

定義4劃分系統中的任務可由軟件實現，也可由硬件實現，但不可同時由軟件和硬件實現.

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

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

(1)

(2)

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

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

(3)

(4)

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

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

(5)

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

(6)

1.20-1背包問題

0-1背包問題(KnapsackProblem)是一種組合優化的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，約束參數c分別對應0-1背包問題中的物品價值bi，物品重量wi，背包容量k，則說明軟硬件劃分問題可以看成0-1背包問題進行解決.于是解決0-1背包問題的算法也可以應用到軟硬件劃分問題.

2　混合蛙跳算法

2.1算法原理

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

2.2算法描述

設SFLA算法的第t代種群P(t)的規模為N，分為m個規模為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)的最優個體和最差個體，xg(t)為種群p(t)的全局最優個體，令temp=(y1,y2,…,yd)為一臨時向量，R1為(0,1)中的一個隨機數，R2為(0,1)中的一個隨機數，c1,c2為(1,2)的一個隨機數，w為1.17.算法的實現流程如下：

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

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

Step3：按適應值大小進行降序排序并記錄全局最優解xg(t),子群最優解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　仿真實驗

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

由于嵌入式系統軟硬件劃分問題可以建模轉換成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]可解得到最優值295，蟻群算法則要迭代100多次以后可得到最優解，運行人工螢火蟲群算法[12]，迭代20次后得到最優解，運行混合群算法，迭代2次就可以得到最優解.與蟻群算法對比結果如圖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}

回溯算法解得最優值為1024，e-近似算法解得近似值1018，蟻群算法和蜂群算法可得到的最好解為1024，文獻[7]采用蟻群算法求解，經過200次迭代得最優解為1024.運行蜂群算法，60次迭代后可得最好解為1024，采用本文提出的混合蛙跳算法只需28次迭代即可得到最優解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上的統計結果

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

4　結語

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

[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] 鄒誼，莊鎮泉，李斌.基于量子遺傳算法的嵌入式系統軟硬件劃分算法[J].電路與系統學報,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]劉安,馮金富,梁曉龍,等. 基于遺傳粒子群優化的嵌入式系統軟硬件劃分算法[J] .計算機輔助設計與圖形學報, 2010,22(6):927-933.

[9]胥楓,張桂珠,趙芳,等,一種具有領導機制的混合蛙跳優化算法[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背包問題的螢火蟲群優化算法[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年研究生教育創新計劃項目(gxun-chxs2015097).

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

TP302

A

1673-8462(2016)02-0073-04