0 引言

集成電路在過去30年的發(fā)展幾乎完全遵循Moore定律，即集成電路的集成度每隔18個月就翻一番?，F(xiàn)在集成電路的面積進(jìn)一步減小，并獲得更高的集成度。集成度增加的結(jié)果就是能集成越來越多的功能，甚至是一個完整的系統(tǒng)都能夠被集成到單個芯片之中。這樣原來由微處理器、協(xié)處理器和多塊其他外圍芯片組成的系統(tǒng)，可以集成在一塊芯片內(nèi)實現(xiàn)，這種一塊芯片集成一個系統(tǒng)的技術(shù)，叫做系統(tǒng)集成芯片(SOC，System-On—Chip)技術(shù)。但是傳統(tǒng)的系統(tǒng)設(shè)計面臨著許多必須解決的矛盾問題，首先是系統(tǒng)高性能和低成本之間的矛盾；其次是系統(tǒng)復(fù)雜性與更新?lián)Q代周期之間的矛盾。
面對這種矛盾，一個可行的解決方案是采用SOC軟硬件協(xié)同設(shè)計方法。而軟硬件劃分是軟硬件協(xié)同設(shè)計方法的關(guān)鍵問題。軟硬件劃分問題是一個多目標(biāo)優(yōu)化問題，在優(yōu)化過程中要針對成本、面積、功耗、時間等多個目標(biāo)?，F(xiàn)在已經(jīng)有很多算法應(yīng)用到軟硬件劃分中，如遺傳算法、螞蟻算法、禁忌搜索算法、模擬退火算法等。本文主要采用基于小生境技術(shù)(Niching Methods)和精英保持策略的改進(jìn)遺傳算法來進(jìn)行軟硬件劃分研究。

l 遺傳算法基本思想

美國Michigan大學(xué)J．Holland教授于1975年提出的遺傳算法，遺傳算法是以達(dá)爾文的自然選擇和優(yōu)勝劣汰的生物進(jìn)化理論為基礎(chǔ)的。和傳統(tǒng)的搜索算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的成為種群(Population)的初始解開始搜索。種群中的每一個體都是問題的一個解，稱為染色體，這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。在新一代形成中，根據(jù)適應(yīng)值的大小選擇部分后代，淘汰部分后代。經(jīng)過若干代之后，算法收斂于最好的染色體，它可能是問題的最優(yōu)解或近似最優(yōu)解。圖l是遺傳算法基本的流程示意圖。

遺傳算法有三類基本的操作：選擇(Selection)、交叉(Crossover)、和變異(Mutation)。選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個體，是它們有機(jī)會作為父代為下一代繁殖子孫，選擇的原則是給予適應(yīng)度強(qiáng)的個體較大的機(jī)會。交又是最主要的遺傳算法操作，它同時對兩個染色體進(jìn)行操作，組合二者的特性產(chǎn)生新的后代，遺傳算法的性能很大程度上取決于采用的交叉運(yùn)算的性能。變異發(fā)生的概率最低，變異操作是在染色體上自發(fā)地產(chǎn)生隨機(jī)變化，在遺傳算法中變異可以提供初始種群中不包括的基因，為種群提供新的個體。
遺傳算法的主要優(yōu)點是：1)具有領(lǐng)悟無關(guān)的群體性全局搜索能力，可避免陷入局部最優(yōu)；2)搜索使用評價函數(shù)啟發(fā)過程簡單；3)使用概率機(jī)制進(jìn)行迭代，具有隨機(jī)性；4)可擴(kuò)展性強(qiáng)，易于介入已有的模型中去，且易于與其他優(yōu)化技術(shù)結(jié)合。

2 小生境技術(shù)和精英保持策略

2．1 小生境技術(shù)

早熟收斂是遺傳算法最嚴(yán)重的一個問題，保持群體的多樣性可以有效地防止群體的早熟收斂，而且種群多樣性也是遺傳算法能夠搜索全局最優(yōu)解的基本條件。其中小生境(niching methods)技術(shù)是遺傳算法維持種群多樣性而廣為采用的方法。在生物學(xué)中，小生境是指特定環(huán)境下的一種生存環(huán)境，相同的生物生活在同一個小生境中。借鑒此概念，遺傳算法將每一代個體劃分成若干類，每個類中選出若干適應(yīng)度較高的個體作為一個類的優(yōu)秀代表組成一個種群，再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個體群，同時采用預(yù)選擇機(jī)制或者排擠機(jī)制或共享機(jī)制完成選擇操作。這樣就可以更好的保持群體的多樣性，使其具有較高的全局尋優(yōu)能力和收斂速度。遺傳算法中模擬小生境的方法主要有以下幾種：1)基于預(yù)選擇的小生境實現(xiàn)方法；2)基于排擠的小生境實現(xiàn)方法；3)基于共享函數(shù)的小生境實現(xiàn)方法。

2．2 精英保持策略

在遺傳算法的運(yùn)行過程中，通過對個體進(jìn)行交叉、變異等遺傳操作而不斷地產(chǎn)生出新的個體。雖然隨著群體的進(jìn)化過程會產(chǎn)生出越來越多的優(yōu)良個體，但是猶豫遺傳算法的隨機(jī)性，可能會破壞當(dāng)前群體中的最好的個體。這將對遺傳算法的有效性和收斂性都有很大影響。為了使適應(yīng)度最好的個體能夠保存到下一代群體中，本文使用精英保持策略(Elitlsm Preserving)來進(jìn)行優(yōu)勝劣汰，將當(dāng)前群體中適應(yīng)度最高的個體不參與交叉和變異運(yùn)算，而是用它來替代當(dāng)前代中適應(yīng)度最低的個體。假設(shè)P，代表第i代的進(jìn)化群體，則精英保持策略的操作示意如圖2：

如圖2所示，精英保持策略的基本思想是對Pi進(jìn)行非劣排序，在群體中挑出最優(yōu)的個體保留到下一代Pi+1。這種保留通過在遺傳操作外部維持一個輔助群體P*來實現(xiàn)。P*中個體的編碼決策向量是所有解向量中的非被支配向量，即當(dāng)前代的Pareto最優(yōu)解。由于每代進(jìn)化后的非支配向量大小是個不定量，外部群體P*的大小具有不確定性。為了保持外部群體大小不變，在實際操作過程中采用截斷操作的辦法防止邊界解的遺失。其具體做法是：將Pi和P*i中所有的個體復(fù)制到P*i+1。如果P*i+1的群體大小超過了N*，利用截斷操作減少|(zhì)P*i+1|；如果P*i+1的群體大小少于N*，則用被支配個體填充P*i+1。

3 基于改進(jìn)的遺傳算法軟硬件劃分

SoC軟硬件劃分問題實際上可以看作一個求解多個目標(biāo)的優(yōu)化問題。其目標(biāo)是在滿足一定系統(tǒng)約束的前提下實現(xiàn)系統(tǒng)性能的最優(yōu)化?；诟倪M(jìn)的軟硬件劃分步驟如下：

步驟1：將待優(yōu)化的SoC系統(tǒng)轉(zhuǎn)化為數(shù)據(jù)流圖DFG

步驟2：從IP庫中調(diào)出數(shù)據(jù)流圖中可實現(xiàn)每個任務(wù)節(jié)點的候選IP

步驟3：對個體進(jìn)行整數(shù)編碼初始化，形成群體P0

步驟4：對Pi中的每個個體進(jìn)行性能評估，計算其執(zhí)行時間、面積、功耗和成本

步驟5：適應(yīng)度賦值

步驟6：合并Pi和P*i群體，對其進(jìn)行Pareto排序，構(gòu)造非支配集(NDS)。復(fù)制Pareto最優(yōu)個體，即所得的非支配集，記做P*i+1

步驟7：判斷結(jié)束條件是否滿足，如果t>Gen，則進(jìn)化結(jié)束，P*i+1為最終輸出的非劣解，P*i+1中每個個體的實現(xiàn)方式即為候選的軟硬件劃分解。否則繼續(xù)，轉(zhuǎn)步驟8

步驟8：構(gòu)造新群體。如果NDS<popsize，用分類方法構(gòu)造新群體；如果NDS>popsize，用聚類方法構(gòu)造新群體步驟9：對新群體執(zhí)行遺傳操作，操作的結(jié)果設(shè)為pi+l，令T=Pi+l；轉(zhuǎn)步驟4

3．1 數(shù)據(jù)流圖描述

數(shù)據(jù)流圖DFG(Data Flow Graph)是一個包含頂點和邊的有向無環(huán)圖。DFG由節(jié)點和弧線構(gòu)成，當(dāng)一個DFG用來描述一個SoC系統(tǒng)時，其頂點通常用來表示一些功能單元，對應(yīng)構(gòu)成系統(tǒng)的軟硬件部件；而弧則表示數(shù)據(jù)處理的順序，或者說是頂點之間的數(shù)據(jù)依賴關(guān)系，如圖3所示。

3．2 個體編碼和遺傳操作

在基于遺傳算法的軟硬件劃分中，最常見的編碼方法是二進(jìn)制編碼。通過二進(jìn)制編碼將數(shù)據(jù)流圖的節(jié)點映射到位串空間0和1上，然后在位串空間進(jìn)行遺傳操作。一般用0表示該節(jié)點由軟件實現(xiàn)，用l表示該節(jié)點由硬件實現(xiàn)。設(shè)IP核數(shù)目為20，每個節(jié)點編碼長度為5，二進(jìn)制編碼的交叉變異情況如圖3、圖4所示。

在圖3、圖4的遺傳操作過程中，有兩個節(jié)點的個體{Xl，X2}的二進(jìn)制編碼長度為10，節(jié)點Xl、X2的編碼取值范圍均為[00000，l0011]，經(jīng)過交叉和變異操作后，分別產(chǎn)生超出編碼取值范圍的無效個體{1011l，l0010}和{0llll，11010}。出于上述原因，本文采用整數(shù)向量編碼的個體編碼方案。該方法直接自然，避免了編碼、解碼的冗余，減輕了遺傳算法的計算負(fù)擔(dān)，提高了運(yùn)算效率，能夠更好地保持群體的多樣性。

針對圖3所示為目標(biāo)對象，在交叉概率PC=0．62，變異概率Pm=0．02，種群大小sizePop=80，演化代數(shù)numGen=l00的條件下，通過Matlab遺傳工具箱進(jìn)行模擬仿真，得出仿真結(jié)果如圖5所示。圖5中群體均值隨著迭代次數(shù)的增加逐漸收斂，說明基于小生境技術(shù)和精英保持策略的改進(jìn)算法可以得到該優(yōu)化問題的最優(yōu)解。

4 結(jié)論

綜上所述，在小生境技術(shù)的基礎(chǔ)上引入精英保持策略和保持群體多樣性的方法，即經(jīng)過優(yōu)化策略之后的算法，能夠更好更快地搜索到最優(yōu)解集，從而達(dá)到了加速算法收斂速度、并避免陷入局部最優(yōu)的目的。