基于改進蟻群算法的嵌入式系統軟硬件劃分

潘穎　阮文惠

摘 要： 針對標準蟻群算法的軟硬件劃分問題求解難題，提出改進蟻群算法的系統軟硬件劃分方法。首先分析了當前嵌入式系統軟硬件劃分研究的現狀，并構建軟硬件劃分的數學模型；然后采用蟻群算法模擬螞蟻覓食行為搜索數學模型的最優解，并引入逆反饋機制提高蟻群算法的搜索性能；最后通過實驗證明軟硬件劃分問題求解的有效性。實驗結果表明，改進蟻群算法提高了問題求解的效率，獲得了合理的軟硬件劃分結果，且結果優于標準蟻群算法。

關鍵詞： 硬件系統； 蟻群算法； 軟件系統； 收斂速度； 仿真測試

中圖分類號： TN919?34； TP181 文獻標識碼： A 文章編號： 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 引 言

隨著計算機技術和微電子技術的不斷成熟，嵌入式系統的應用范圍更加廣泛[1]。嵌入式系統包括硬件系統和軟件系統兩部分，以前由于硬件成本高，價格高，軟件系統占的比例大。近幾年，隨著集成技術的發展，硬件價格急劇下降，出現了硬件系統和軟件系統平分天下的格局[2]。硬件系統和軟件系統均有各自的優勢，對于一個嵌入式系統，如何對硬件系統和軟件系統進行準確劃分，降低系統的成本，同時保證系統滿足實際要求，成為人們關注的焦點[3?4]。

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

為了對嵌入式系統軟硬件進行精確劃分，降低系統成本，針對標準蟻群算法在軟硬件劃分問題求解過程存在的難題，提出了改進蟻群算法的系統軟硬件劃分方法，通過實驗證明該方法在軟硬件劃分問題上求解的有效性。

1 改進蟻群算法

1.1 標準蟻群算法

蟻群一共包含有[m]只螞蟻，它們分布于[n]個節點上，不同螞蟻下一次移動選擇節點的概率不同，該節點沒有被訪問過，并且對路徑上信息素濃度進行更新。

節點選擇的條件為：節點[i]和[j]的路徑信息素濃度為[τij；]節點[i]轉移到[j]的啟發信息為[ηij，]它們的值根據具體問題進行設置。在[t]時刻，螞蟻[k]從節點[i]選擇節點[j]為目的地的概率為：

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

式中：[Nki]表示螞蟻[k]可以選擇的節點；[α]表示殘留信息權值；[β]表示啟發信息的重要程度。

在蟻群移動的過程中，為了不讓殘留信息對啟發信息產生干擾，螞蟻經過全部節點后，需要更新殘留信息濃度，使部分信息素揮發，同時將最新訪問節點信息加入到[τij，]即有：

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

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

1.2 標準蟻群算法的不足以及改進

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

1.3 改進蟻群算法的有效性測試

為了比較改進蟻群算法（IACO）和標準蟻群算法（ACO）的優越性，選擇兩個Sphere和Rosenbrock測試執行速度和求解精度，結果見圖2。對圖2的變化曲線進行分析可以發現，IACO的迭代次數顯著減少，計算時間復雜度明顯下降，提高了蟻群搜索問題解的速度，而且得到更高的精度結果，這說明本文引入逆反饋過程可以獲得更優的蟻群算法。

2 改進蟻群算法的嵌入式系統軟硬件劃分

2.1 軟硬件問題的數學模型

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

嵌入式系統軟硬件劃分的節點之間通信開銷[cvi，vj]和的數學模型[12]為：

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

式中[p（vi）]表示[vi]的全部前驅節點。

相應的約束條件為：

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

2.2 軟硬件劃分問題的求解

（1） 對具體的嵌入式系統軟硬件問題進行分析，建立數學模型。

（2） 對改進蟻群算法的參數進行設置，并初始化蟻群。

（3） 將所有螞蟻平均分配到嵌入式系統軟硬件構成的DAG節點上。

（4） 根據式（1）計算每一只螞蟻選擇下一個節點的概率，并且從轉移到的該節點上建立每只螞蟻的轉移路徑。

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

（6） 根據閾值評價相遇螞蟻的數目，為每一只螞蟻建立自己的路徑。

（7） 根據閾值判斷結果進行信息素更新操作。在每次循環時，信息素濃度不能超過范圍[τmin，τmax，]不然采用式（3）進行強制設置。

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

（8） 根據蟻群的最優路徑得到嵌入式系統軟硬件劃分的最佳方案。

3 仿真實驗的結果與分析

為了測試改進蟻群算法的嵌入式系統軟硬件劃分方法的有效性，選擇粒子群算法（PSO）[13]的嵌入式系統軟硬件劃分方法進行仿真對比測試。

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

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

4 結 語

嵌入式系統是當前計算機領域中的研究熱點，而軟硬件劃分直接影響嵌入式系統的性能，針對標準蟻群算法存在收斂速度慢，難以獲得全局最優的軟硬件劃分方案的問題，本文提出了改進蟻群算法的系統軟硬件劃分方法。首先建立了軟硬件劃分的數學模型，然后采用改進蟻群算法模擬螞蟻覓食行為搜索數學模型的最優解，實驗結果表明，改進蟻群算法提高了問題求解的效率，獲得了合理的軟硬件劃分結果，且結果優于其他算法，在嵌入式系統較硬件劃分中具有更高的實際應用價值。

參考文獻

[1] 鄒誼，莊鎮泉，楊俊安.基于遺傳算法的嵌入式系統軟硬件劃分算法[J].中國科學技術大學學報，2003，34（6）：724?731.

[2] 唐思章，黃勇.SOPC與嵌入式系統軟硬件協同設計[J].單片機與嵌入式系統應用，2005，25（12）：35?56.

[3] 何湘竹，陳軍波，陳亞光，等.SOC軟硬件劃分系統中的關鍵算法[J].計算機工程與應用，2006，43（14）：105?108.

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

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

[6] 劉功杰，張魯峰，李思昆.遺傳算法在軟硬件劃分中的應用[J].國防科技大學學報，2002，24（2）：64?68.

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

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

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

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

[11] 熊志輝，李思昆，陳吉華.遺傳算法與螞蟻算法動態融合的軟硬件劃分[J].軟件學報，2005，16（4）：503?512.

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

[13] 劉安，馮金富，梁曉龍，等.基于遺傳粒子群優化的嵌入式系統軟硬件劃分算法[J].計算機輔助設計與圖形學學報，2010，22（6）：927?934.