基于改進(jìn)蟻群算法的嵌入式系統(tǒng)軟硬件劃分

潘穎　阮文惠

摘 要： 針對(duì)標(biāo)準(zhǔn)蟻群算法的軟硬件劃分問題求解難題，提出改進(jìn)蟻群算法的系統(tǒng)軟硬件劃分方法。首先分析了當(dāng)前嵌入式系統(tǒng)軟硬件劃分研究的現(xiàn)狀，并構(gòu)建軟硬件劃分的數(shù)學(xué)模型；然后采用蟻群算法模擬螞蟻覓食行為搜索數(shù)學(xué)模型的最優(yōu)解，并引入逆反饋機(jī)制提高蟻群算法的搜索性能；最后通過實(shí)驗(yàn)證明軟硬件劃分問題求解的有效性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)蟻群算法提高了問題求解的效率，獲得了合理的軟硬件劃分結(jié)果，且結(jié)果優(yōu)于標(biāo)準(zhǔn)蟻群算法。

關(guān)鍵詞： 硬件系統(tǒng)； 蟻群算法； 軟件系統(tǒng)； 收斂速度； 仿真測(cè)試

中圖分類號(hào)： TN919?34； TP181 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）03?0164?03

Embedded system hardware and software partition

based on improved ant colony algorithm

PAN Ying， RUAN Wenhui

（School of Digital Media， Lanzhou University of Arts and Science， Lanzhou 730030， China）

Abstract： Since it is hard for the standard ant colony algorithm to solve the software and hardware partition problem， the hardware and software partition method based on the improved ant colony algorithm is proposed. The research status of the embedded system hardware and software partition is analyzed. The mathematical model of the hardware and software partition was constructed. The ant colony algorithm is used to simulate the foraging behavior of ants to search the optimal solution of the mathematical model. The inverse feedback mechanism is introduced to improve the search performance of the ant colony algorithm. The solving validity of the hardware and software partition problem was proved by means of experiments. The results show that the improved ant colony algorithm has improved the efficiency of problem solving， and obtained the reasonable hardware and software partition result， which is better than the result of the standard ant colony algorithm.

Keywords： hardware system； ant colony algorithm； software system； convergence speed； simulation test

0 引 言

隨著計(jì)算機(jī)技術(shù)和微電子技術(shù)的不斷成熟，嵌入式系統(tǒng)的應(yīng)用范圍更加廣泛[1]。嵌入式系統(tǒng)包括硬件系統(tǒng)和軟件系統(tǒng)兩部分，以前由于硬件成本高，價(jià)格高，軟件系統(tǒng)占的比例大。近幾年，隨著集成技術(shù)的發(fā)展，硬件價(jià)格急劇下降，出現(xiàn)了硬件系統(tǒng)和軟件系統(tǒng)平分天下的格局[2]。硬件系統(tǒng)和軟件系統(tǒng)均有各自的優(yōu)勢(shì)，對(duì)于一個(gè)嵌入式系統(tǒng)，如何對(duì)硬件系統(tǒng)和軟件系統(tǒng)進(jìn)行準(zhǔn)確劃分，降低系統(tǒng)的成本，同時(shí)保證系統(tǒng)滿足實(shí)際要求，成為人們關(guān)注的焦點(diǎn)[3?4]。

自嵌入式系統(tǒng)出現(xiàn)以后，很多機(jī)構(gòu)和大學(xué)專門成立了嵌入式軟硬件系統(tǒng)劃分研究團(tuán)隊(duì)，提出了許多有效的嵌入式軟硬件劃分算法[5]。最原始的方法為整數(shù)規(guī)劃算法，工作靈活，可以適應(yīng)不同類型的嵌入式系統(tǒng)，但整數(shù)規(guī)劃算法的嵌入式軟硬件系統(tǒng)劃分問題求解時(shí)間長(zhǎng)、速度慢，不能滿足嵌入式系統(tǒng)軟硬件劃分的效率[6]。隨后有學(xué)者提出了基于迭代算法的嵌入式軟硬件劃分方法，但同樣存在求解效率低的缺陷[7]。大量研究結(jié)果表明，嵌入式軟硬件系統(tǒng)劃分是一個(gè)限制條件多的NP難題，出現(xiàn)了基于遺傳算法的軟硬件劃分算法、基于免疫算法的軟硬件劃分算法、基于蟻群算法的軟硬件劃分算法[8?10]。有學(xué)者對(duì)三種算法的優(yōu)劣進(jìn)行比較，發(fā)現(xiàn)基于蟻群算法的軟硬件劃分算法性能最優(yōu)，然而標(biāo)準(zhǔn)蟻群算法存在收斂速度慢等不足，在嵌入式系統(tǒng)軟硬件劃分問題求解范圍受限[11]。

為了對(duì)嵌入式系統(tǒng)軟硬件進(jìn)行精確劃分，降低系統(tǒng)成本，針對(duì)標(biāo)準(zhǔn)蟻群算法在軟硬件劃分問題求解過程存在的難題，提出了改進(jìn)蟻群算法的系統(tǒng)軟硬件劃分方法，通過實(shí)驗(yàn)證明該方法在軟硬件劃分問題上求解的有效性。

1 改進(jìn)蟻群算法

1.1 標(biāo)準(zhǔn)蟻群算法

蟻群一共包含有[m]只螞蟻，它們分布于[n]個(gè)節(jié)點(diǎn)上，不同螞蟻下一次移動(dòng)選擇節(jié)點(diǎn)的概率不同，該節(jié)點(diǎn)沒有被訪問過，并且對(duì)路徑上信息素濃度進(jìn)行更新。

節(jié)點(diǎn)選擇的條件為：節(jié)點(diǎn)[i]和[j]的路徑信息素濃度為[τij；]節(jié)點(diǎn)[i]轉(zhuǎn)移到[j]的啟發(fā)信息為[ηij，]它們的值根據(jù)具體問題進(jìn)行設(shè)置。在[t]時(shí)刻，螞蟻[k]從節(jié)點(diǎn)[i]選擇節(jié)點(diǎn)[j]為目的地的概率為：

[pkijt=ταijtηβijj∈Nkiταijtηβij] （1）

式中：[Nki]表示螞蟻[k]可以選擇的節(jié)點(diǎn)；[α]表示殘留信息權(quán)值；[β]表示啟發(fā)信息的重要程度。

在蟻群移動(dòng)的過程中，為了不讓殘留信息對(duì)啟發(fā)信息產(chǎn)生干擾，螞蟻經(jīng)過全部節(jié)點(diǎn)后，需要更新殘留信息濃度，使部分信息素?fù)]發(fā)，同時(shí)將最新訪問節(jié)點(diǎn)信息加入到[τij，]即有：

[τijt+n=ρτijt+k=1mΔτkij] （2）

式中：[ρ]表示信息素的揮發(fā)程度；[Δτkij]表示殘留信息素的濃度。

1.2 標(biāo)準(zhǔn)蟻群算法的不足以及改進(jìn)

在標(biāo)準(zhǔn)蟻群算法的工作中，螞蟻的數(shù)目固定不變，只有正反饋過程，不能實(shí)現(xiàn)逆反饋過程，導(dǎo)致算法的收斂速度慢，工作效率低。為了解決標(biāo)準(zhǔn)蟻群算法存在的不足，設(shè)計(jì)了逆反饋過程，引入一個(gè)閾值[ε，]當(dāng)循環(huán)相遇螞蟻的數(shù)量小于[ε，]就按標(biāo)準(zhǔn)蟻群算法進(jìn)行工作，反之，相遇螞蟻路徑上的信息素均要進(jìn)行更新，改進(jìn)蟻群算法的具體工作流程如圖1所示。

1.3 改進(jìn)蟻群算法的有效性測(cè)試

為了比較改進(jìn)蟻群算法（IACO）和標(biāo)準(zhǔn)蟻群算法（ACO）的優(yōu)越性，選擇兩個(gè)Sphere和Rosenbrock測(cè)試執(zhí)行速度和求解精度，結(jié)果見圖2。對(duì)圖2的變化曲線進(jìn)行分析可以發(fā)現(xiàn)，IACO的迭代次數(shù)顯著減少，計(jì)算時(shí)間復(fù)雜度明顯下降，提高了蟻群搜索問題解的速度，而且得到更高的精度結(jié)果，這說明本文引入逆反饋過程可以獲得更優(yōu)的蟻群算法。

2 改進(jìn)蟻群算法的嵌入式系統(tǒng)軟硬件劃分

2.1 軟硬件問題的數(shù)學(xué)模型

嵌入式系統(tǒng)的軟硬件功能可以用DAG表示，[V]表示節(jié)點(diǎn)的集合，且任務(wù)[i]滿足條件：[vi∈V，][E]表示邊的集合，且有[ei=vi，vj∈V，]采用“0”和“1”分別表示嵌入式系統(tǒng)的軟件系統(tǒng)和硬件系統(tǒng)，那么節(jié)點(diǎn)的DAG具體如圖3所示。

嵌入式系統(tǒng)軟硬件劃分的節(jié)點(diǎn)之間通信開銷[cvi，vj]和的數(shù)學(xué)模型[12]為：

[cp（vi），vi=vj∈p（vi）c（vj，vi），由軟件完成maxvj∈p（vi）c（vj，vi），由硬件完成 ] （3）

式中[p（vi）]表示[vi]的全部前驅(qū)節(jié)點(diǎn)。

相應(yīng)的約束條件為：

[minTvends.t. i=1nphixi+psi（-xi）≤Pi=1nahixi≤Ahi=1nasi（-xi）≤Asxi∈Z] （4）

2.2 軟硬件劃分問題的求解

（1） 對(duì)具體的嵌入式系統(tǒng)軟硬件問題進(jìn)行分析，建立數(shù)學(xué)模型。

（2） 對(duì)改進(jìn)蟻群算法的參數(shù)進(jìn)行設(shè)置，并初始化蟻群。

（3） 將所有螞蟻平均分配到嵌入式系統(tǒng)軟硬件構(gòu)成的DAG節(jié)點(diǎn)上。

（4） 根據(jù)式（1）計(jì)算每一只螞蟻選擇下一個(gè)節(jié)點(diǎn)的概率，并且從轉(zhuǎn)移到的該節(jié)點(diǎn)上建立每只螞蟻的轉(zhuǎn)移路徑。

（5） 對(duì)全部螞蟻轉(zhuǎn)移路徑進(jìn)行分析，看是否有相遇的螞蟻，若有將相遇的螞蟻，則將它們的路徑取作為一條新路徑。

（6） 根據(jù)閾值評(píng)價(jià)相遇螞蟻的數(shù)目，為每一只螞蟻建立自己的路徑。

（7） 根據(jù)閾值判斷結(jié)果進(jìn)行信息素更新操作。在每次循環(huán)時(shí)，信息素濃度不能超過范圍[τmin，τmax，]不然采用式（3）進(jìn)行強(qiáng)制設(shè)置。

[τij=τmin，τij≤τminτmax，τij≥τmax] （5）

（8） 根據(jù)蟻群的最優(yōu)路徑得到嵌入式系統(tǒng)軟硬件劃分的最佳方案。

3 仿真實(shí)驗(yàn)的結(jié)果與分析

為了測(cè)試改進(jìn)蟻群算法的嵌入式系統(tǒng)軟硬件劃分方法的有效性，選擇粒子群算法（PSO）[13]的嵌入式系統(tǒng)軟硬件劃分方法進(jìn)行仿真對(duì)比測(cè)試。

在不同節(jié)點(diǎn)數(shù)目的條件下，采用Matlab 2014R編程進(jìn)行模擬測(cè)試，兩種方法的嵌入式系統(tǒng)面積變化曲線如圖4所示。從圖4可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，兩種嵌入式系統(tǒng)軟硬件劃分方法設(shè)計(jì)系統(tǒng)的面積隨之增大，改進(jìn)蟻群算法的面積要小于粒子群算法，說明改進(jìn)蟻群算法的嵌入式系統(tǒng)的集成度更高，有效降低了嵌入式系統(tǒng)的功耗。

在不同節(jié)點(diǎn)數(shù)目的條件下，兩種方法對(duì)嵌入式軟硬件劃分問題求解的時(shí)間變化曲線如圖5所示。從圖5可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，改進(jìn)蟻群算法和粒子群算法的執(zhí)行時(shí)間也延長(zhǎng)，在相同條件下，改進(jìn)蟻群算法的執(zhí)行時(shí)間較短，是可以更快找到嵌入式軟硬件劃分問題的最優(yōu)方案，滿足了嵌入式軟硬件劃分問題求解的實(shí)時(shí)性，有效降低了嵌入式系統(tǒng)的功耗。

4 結(jié) 語

嵌入式系統(tǒng)是當(dāng)前計(jì)算機(jī)領(lǐng)域中的研究熱點(diǎn)，而軟硬件劃分直接影響嵌入式系統(tǒng)的性能，針對(duì)標(biāo)準(zhǔn)蟻群算法存在收斂速度慢，難以獲得全局最優(yōu)的軟硬件劃分方案的問題，本文提出了改進(jìn)蟻群算法的系統(tǒng)軟硬件劃分方法。首先建立了軟硬件劃分的數(shù)學(xué)模型，然后采用改進(jìn)蟻群算法模擬螞蟻覓食行為搜索數(shù)學(xué)模型的最優(yōu)解，實(shí)驗(yàn)結(jié)果表明，改進(jìn)蟻群算法提高了問題求解的效率，獲得了合理的軟硬件劃分結(jié)果，且結(jié)果優(yōu)于其他算法，在嵌入式系統(tǒng)較硬件劃分中具有更高的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)

[1] 鄒誼，莊鎮(zhèn)泉，楊俊安.基于遺傳算法的嵌入式系統(tǒng)軟硬件劃分算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2003，34（6）：724?731.

[2] 唐思章，黃勇.SOPC與嵌入式系統(tǒng)軟硬件協(xié)同設(shè)計(jì)[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2005，25（12）：35?56.

[3] 何湘竹，陳軍波，陳亞光，等.SOC軟硬件劃分系統(tǒng)中的關(guān)鍵算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，43（14）：105?108.

[4] 李正民，郭金金，呂瑩瑩.一種嵌入式系統(tǒng)軟硬件劃分算法[J].計(jì)算機(jī)仿真，2011，28（10）：104?107.

[5] 劉威，丁巖松，徐學(xué)航.嵌入式系統(tǒng)軟硬件劃分技術(shù)的研究[J].煤炭技術(shù)，2011，30（2）：173?175.

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

[7] 李暉，姚放吾，鄧新穎，等.基于免疫算法的嵌入式系統(tǒng)軟硬件劃分方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（22）：4239?4242.

[8] 陳瑋，顧思思.基于組合算法的嵌入式系統(tǒng)軟硬件劃分方法[J].計(jì)算機(jī)應(yīng)用與軟件，2015，32（10）：241?244.

[9] 邵歲鋒，張英杰.基于免疫粒子群的嵌入式系統(tǒng)軟硬件劃分方法[J].計(jì)算機(jī)應(yīng)用，2010，30（2）：479?481.

[10] 紀(jì)穎，李蘭英，石敏，等.基于遺傳和禁忌搜索混合的軟硬件劃分算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（20）：81?83.

[11] 熊志輝，李思昆，陳吉華.遺傳算法與螞蟻算法動(dòng)態(tài)融合的軟硬件劃分[J].軟件學(xué)報(bào)，2005，16（4）：503?512.

[12] 郭榮佐，黃君，王霖.基于π網(wǎng)的嵌入式系統(tǒng)軟硬件劃分方法[J].計(jì)算機(jī)應(yīng)用，2012，32（3）：855?860.

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