二次改進(jìn)遺傳算法與3DNoC低功耗映射

張大坤　宋國治　林華洲　任淑霞

(天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院　天津　300387)(Zhandakun2013@163.com)

二次改進(jìn)遺傳算法與3DNoC低功耗映射

張大坤宋國治林華洲任淑霞

(天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院天津300387)(Zhandakun2013@163.com)

摘要隨著集成電路技術(shù)的迅速發(fā)展，芯片的集成度不斷提高，片上眾多處理單元間的高效互連成為關(guān)鍵問題，因而相繼出現(xiàn)了片上系統(tǒng)(system-on-chip, SoC)和二維片上網(wǎng)絡(luò)(two-dimensional network-on-chip, 2D NoC).當(dāng)二維片上網(wǎng)絡(luò)在多方面達(dá)到瓶頸時，三維片上網(wǎng)絡(luò)(three-dimensional network-on-chip, 3D NoC)應(yīng)運而生.三維片上網(wǎng)絡(luò)已引起學(xué)術(shù)界和產(chǎn)業(yè)界的高度重視，三維片上網(wǎng)絡(luò)低功耗映射是其中的1個關(guān)鍵問題.之前的研究曾提出過一種基于改進(jìn)遺傳算法的3D NoC低功耗映射算法，并收到了良好的仿真效果.但當(dāng)問題規(guī)模變大時，計算量隨之增大、運行效率明顯降低.針對這一問題，對3D NoC中面向功耗優(yōu)化的二次改進(jìn)遺傳算法任務(wù)映射機制進(jìn)行研究，提出了一種新的3D NoC低功耗映射算法，并對該映射算法進(jìn)行了仿真實驗.實驗結(jié)果表明，在種群規(guī)模較大的條件下，該算法不僅能夠繼續(xù)降低功耗，而且能夠大幅度地減少映射算法的運行時間.

關(guān)鍵詞三維片上網(wǎng)絡(luò)；低功耗映射；改進(jìn)遺傳算法；二次改進(jìn)遺傳算法；貪心算法

1958年世界誕生了第1個集成電路，隨著集成電路規(guī)模的不斷增大，片上系統(tǒng)(system-on-chip,SoC)應(yīng)運而生，而且SoC的處理單元(processingelements,PE)數(shù)不斷增加，為高效地連接數(shù)量巨大的PE，產(chǎn)生了二維片上網(wǎng)絡(luò)(two-dimensionalnetwork-on-chip, 2DNoC)這種主流的片上互連架構(gòu).而2DNoC在面積、功耗、布局布線以及封裝密度等方面都已達(dá)到了瓶頸，三維片上網(wǎng)絡(luò)(three-dimensionalnetwork-on-chip, 3DNoC)應(yīng)運而生.自2005年第1篇以3DNoC為主題的學(xué)術(shù)論文發(fā)表以來[1]，3DNoC以其更短的全局互連、更高的性能、更低的互連損耗、更高的封裝密度以及更小的體積等諸多優(yōu)勢成為1個重要的研究方向[2-3].降低功耗是3DNoC所面臨的1個關(guān)鍵問題，從多種途徑降低3DNoC的功耗非常必要.映射決定知識產(chǎn)權(quán)(intellectualproperty，IP)核在3DNoC上的位置，通過改進(jìn)映射算法能夠有效地降低3DNoC的功耗.因此，3DNoC低功耗映射已逐漸成為3DNoC領(lǐng)域的研究熱點.3DNoC映射問題和任務(wù)調(diào)度問題相似，都是NP難解問題[4].有許多研究者嘗試應(yīng)用各種算法解決3DNoC映射問題，其中，美國賓夕法尼亞州立大學(xué)Charles[5]采用遺傳算法研究了考慮到熱感知和通信感知的3DNoC映射問題；南京大學(xué)王佳文[6-8]、湯普森河大學(xué)的Elmiligi等人[9]、航空電子系統(tǒng)綜合技術(shù)重點實驗室Ge等人[10]均嘗試過采用遺傳算法解決3DNoC映射問題，并取得了相應(yīng)的研究成果.本文將對3DNoC中面向功耗優(yōu)化的二次改進(jìn)遺傳算法任務(wù)映射機制進(jìn)行研究.

13DNoC低功耗映射問題

1.1基本概念

3DNoC低功耗映射就是在給定通信軌跡圖和拓?fù)浣Y(jié)構(gòu)圖的基礎(chǔ)上，研究如何將IP核映射到3DNoC的資源節(jié)點上，使得整個3DNoC的通信量最小，達(dá)到降低通信功耗的目的.為了描述3DNoC映射問題，給出如下定義:

定義1. 通信軌跡圖CTG(N,C).設(shè)CTG(N,C)為有向圖，其中N為頂點集，節(jié)點ni∈N表示1個IP核;C為邊集，有向邊ci j∈C表示節(jié)點ci到節(jié)點cj的邊，wi j表示邊ci j的權(quán)重.

定義2. 拓?fù)浣Y(jié)構(gòu)圖TAG(T,E).設(shè)TAG(T,E)為有向圖，其中,T為PE集合，ti∈T表示1個PE;E為邊集，有向邊ei j表示節(jié)點ti到節(jié)點tj的邊[11-12].

1.23DNoC映射算法評估標(biāo)準(zhǔn)

目前尚沒有一致公認(rèn)的面向3DNoC映射問題的評估標(biāo)準(zhǔn).3DNoC作為解決片上系統(tǒng)通信問題的解決方案.其中，網(wǎng)絡(luò)吞吐量與平均延遲都是重要的性能指標(biāo)；3DNoC映射算法的設(shè)計也應(yīng)當(dāng)考慮功耗問題，過高的功耗可能會對網(wǎng)絡(luò)產(chǎn)生致命的影響；3DNoC的三維立體結(jié)構(gòu)，會引發(fā)網(wǎng)絡(luò)內(nèi)部發(fā)熱不均的問題，發(fā)熱過高可能會導(dǎo)致整個網(wǎng)絡(luò)的癱瘓；對于實時性要求相對高的應(yīng)用，最大網(wǎng)絡(luò)延時也應(yīng)作為網(wǎng)絡(luò)性能的重要指標(biāo).文獻(xiàn)[13-14]提出了評價映射算法優(yōu)劣的4個重要性能指標(biāo)：

1) 平均網(wǎng)絡(luò)延遲.3DNoC的出現(xiàn)主要是為了解決SoC內(nèi)資源節(jié)點之間的通信問題,因此，平均網(wǎng)絡(luò)延遲是衡量3DNoC設(shè)計質(zhì)量的重要指標(biāo)，平均網(wǎng)絡(luò)延遲間接地決定了3DNoC的吞吐率.

2) 最大網(wǎng)絡(luò)延遲.目前大多數(shù)針對3DNoC的延時模型都是平均延時模型，然而在出現(xiàn)擁塞的狀況下，決定整個網(wǎng)絡(luò)通信效率的往往是最大延遲，當(dāng)最大延遲超過了其容錯上限，將導(dǎo)致整個網(wǎng)絡(luò)無法正常工作.因此，最大延遲也是3DNoC評估的重要指標(biāo).

3) 平均功耗.3DNoC在傳遞消息的過程中會發(fā)生能量的消耗，平均功耗能夠反映3DNoC在傳送數(shù)據(jù)時功耗性能.

4) 發(fā)熱與負(fù)載均衡.3DNoC由于其結(jié)構(gòu)特性，內(nèi)部節(jié)點容易出現(xiàn)發(fā)熱過高的情況，過熱點的產(chǎn)生將影響整個芯片的性能.過熱點區(qū)域位于網(wǎng)絡(luò)邊緣容易散熱，可以降低過熱點區(qū)域?qū)φ麄€網(wǎng)絡(luò)性能的影響.因此，在網(wǎng)絡(luò)設(shè)計時盡可能地將過熱點區(qū)域分散到網(wǎng)絡(luò)邊緣.

1.33DNoC功耗模型

1.3.13DNoC功耗計算公式

3DNoC中的功耗主要來自2方面：路由節(jié)點上的功耗和鏈路上的功耗.路由節(jié)點上的功耗主要是路由節(jié)點內(nèi)部存儲、交換、路由內(nèi)部連線和路由選擇所產(chǎn)生的能耗；鏈路上的功耗指的是路由數(shù)據(jù)經(jīng)過路由節(jié)點之間鏈路時所產(chǎn)生的能耗.文獻(xiàn)[11]給出了3DNoC的功耗模型，節(jié)點ti發(fā)送1個微片(flit)到節(jié)點tj消耗的能量表示為

(1)

其中，μ表示節(jié)點ti到節(jié)點tj經(jīng)過的路由器個數(shù)，μH和μV分別是節(jié)點ti到節(jié)點tj經(jīng)過的水平方向和垂直方向的邊數(shù)(跳步)，ERbit表示1個微片通過 1個路由器時所消耗的能量，ELHbit和ELVbit分別表示1個微片通過1條水平方向和垂直方向的線路時的耗能.文獻(xiàn)[14]給出的ELHbit和ELVbit的計算公式為

(2)

(3)

其中，dH和dV分別表示水平方向和垂直方向線路的長度，Vdd表示供電電壓，CwireH和CwireV分別表示水平方向和垂直方向線路的電容.

1.3.2映射目標(biāo)函數(shù)

3DNoC映射就是尋找IP核與PE的1個對應(yīng)關(guān)系.在給定通信軌跡圖CTG和拓?fù)浣Y(jié)構(gòu)圖TAG的條件下尋找1個映射函數(shù)M(·):N→T，使得總功耗最低(用Emin表示)，其目標(biāo)函數(shù)如下：

(4)

且滿足條件：

(5)

(6)

對于確定的拓?fù)浣Y(jié)構(gòu)，ERbit，ELHbit和ELVbit是確定的.由文獻(xiàn)[11]可知，線路上的功耗與線路的長度成正比，所以,2個通信節(jié)點之間的線路長度是影響3DNoC功耗的關(guān)鍵要素.由于硅穿孔(throughsiliconvia，TSV)技術(shù)的出現(xiàn)，3DNoC在垂直方向的線路長度遠(yuǎn)遠(yuǎn)小于水平方向的長度，因此，傳輸同樣的數(shù)據(jù)量，在垂直方向的功耗遠(yuǎn)遠(yuǎn)小于水平方向的功耗.

2基于改進(jìn)遺傳算法的3DNoC低功耗映射

本文作者曾對3DNoC映射問題進(jìn)行了研究，提出一種基于改進(jìn)遺傳算法(improvedgeneticalgorithm，IGA)的3DNoC低功耗映射算法(簡稱IG映射算法)[15]，現(xiàn)對其進(jìn)行簡單回顧.

2.1問題簡介

如引言所述，用遺傳算法解決3DNoC映射問題已取得一些研究成果[5-11]，從映射出發(fā)降低3DNoC功耗是1個有效的途徑.遺傳算法根據(jù)問題的目標(biāo)函數(shù)構(gòu)造1個適應(yīng)值函數(shù)，產(chǎn)生由多個解構(gòu)成的初始種群，根據(jù)適應(yīng)值的優(yōu)劣選擇種群中的個體進(jìn)行遺傳操作產(chǎn)生新的種群，當(dāng)進(jìn)化達(dá)到終止條件后，選擇適應(yīng)值好的個體作為問題的解.算法的實現(xiàn)主要分為如下5個步驟：

算法1. 遺傳算法.

Step1. 遺傳算法在運行之前要將解空間的數(shù)據(jù)表示成算法運行時可用的基因數(shù)據(jù)，由于每個IP核只能映射到1個PE上，因此，在映射問題中采用整數(shù)編碼.

Step2. 隨機產(chǎn)生1個初始種群，種群中每個個體都對應(yīng)映射算法的1個解.

Step3. 根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適應(yīng)值函數(shù)，計算種群中每個個體的適應(yīng)值.

Step4. 根據(jù)適應(yīng)值的優(yōu)劣不斷地進(jìn)行選擇和繁殖操作，以得到下一代種群.

Step5. 達(dá)到終止條件后，選擇適應(yīng)值最好的個體作為算法的最終解.

基本遺傳算法的初始種群是隨機生成的，這使得初始種群存在個體分布不均勻、初始種群質(zhì)量偏低的問題.作者提出的IG映射算法是將貪心算法與遺傳算法相結(jié)合，用以解決3DNoC低功耗映射問題，相對于傳統(tǒng)遺傳算法具有更優(yōu)的搜索能力.

2.2IG映射算法的核心思想

IG映射算法是貪心算法與遺傳算法的組合，即采用貪心算法生成初始種群的遺傳算法，貪心算法思想主要體現(xiàn)在生成初始種群個體上.用貪心算法生成初始種群個體主要分為3個步驟：

算法2. 貪心算法.

Step1. 隨機地將任務(wù)圖中的1個節(jié)點(即IP核)映射到3DNoC的第1個位置(把所有IP核從1到N進(jìn)行編號，N為任務(wù)圖上IP核的個數(shù)，n代表任意1個IP核;把所有PE從1到M進(jìn)行編號，M為3DNoC上PE的個數(shù)，m代表任意1個PE).

Step2. 分別計算將所有IP核集合中可用數(shù)字放入所有PE集可用位置后的適應(yīng)值，用n,m,fit表示未使用數(shù)字n放入3DNoC的第m個位置使得適應(yīng)值fit最大，將n,m,fit放入集合F中，從F中選擇fit最大的3組，隨機地從這3組中選擇一組n,m,fit，將n放到3DNoC的第m個位置，把n從可用的IP核集合中刪除，把m從3DNoC的可用位置集合中刪除.

Step3. 重復(fù)Step2，直到?jīng)]有未使用的數(shù)字(IP核集合為空)，即任務(wù)圖中的所有節(jié)點都已映射到3DNoC上.

生成初始種群后，采用遺傳算法進(jìn)行遺傳操作，得到最優(yōu)個體，然后用最優(yōu)個體生成仿真器能夠識別的通信模式文件，仿真器讀取通信模式文件進(jìn)行仿真得到映射功耗.仿真結(jié)果表明，IG映射算法可以有效地降低功耗，從總體趨勢上看，隨著處理單元數(shù)目的增加，功耗降低的幅度逐漸增大，在種群規(guī)模為200、處理單元為120的情況下，總功耗可降低14.42%[15].

3二次改進(jìn)遺傳算法與3DNoC低功耗映射研究

3.1問題的提出與算法描述

3.1.1問題的提出

2.2節(jié)中的IG映射算法是采用貪心算法生成初始種群中的每個個體，使初始種群的質(zhì)量整體得到了提升，有效地降低了功耗.但該算法在生成初始種群時，單個個體生成的計算量較大，在確定1個IP核映射到3DNoC上時，會計算所有未映射到3DNoC上的IP核放到3DNoC上所有可用位的適應(yīng)值,而且生成每個個體都要進(jìn)行同樣的運算，所以該算法在生成初始種群時運行效率明顯低于基本遺傳算法.針對這一問題，對3DNoC中面向功耗優(yōu)化的二次改進(jìn)遺傳算法任務(wù)映射機制進(jìn)行研究，提出了一種基于改進(jìn)貪心算法和遺傳算法的3DNoC低功耗映射策略，并稱其為基于二次改進(jìn)遺傳算法(doubleimprovedgeneticalgorithm,I2G)的3DNoC低功耗映射算法并稱之為I2G映射算法.

3.1.2I2G映射算法的核心思想

IG映射算法是用一般的貪心算法生成初始種群，而I2G映射算法則采用改進(jìn)貪心算法生成初始種群.I2G映射算法中采用的改進(jìn)貪心算法與IG映射算法中采用的貪心算法的區(qū)別在于：

1) 2.2節(jié)中貪心算法在Step1，隨機地將1個IP核(用n表示)映射到3DNoC的第1個位置(數(shù)字n可重復(fù)出現(xiàn))，而改進(jìn)貪心算法中在第1個位置上放置的IP核(n)不可重復(fù)出現(xiàn)(n=1，2，…，N).

2) 2.2節(jié)中貪心算法在Step2，是從集合F中找出3組fit最大的n,m,fit，隨機地從中選1組，而改進(jìn)貪心算法只選取fit值最大的1組n,m,fit，將n放到3DNoC的第m個位置，把n從可用的IP核集合中刪除，把m從3DNoC的可用位置集合中刪除；重復(fù)2)直到IP核集合為空，即表示生成了1個個體.

3) 2.2節(jié)中貪心算法可以生成任意多個個體，而改進(jìn)貪心算法只能生成N個個體(N為任務(wù)圖規(guī)模).因此，改進(jìn)貪心算法會對所有已生成的個體進(jìn)行變異操作生成一定數(shù)量的鄰居個體，最后從所有生成的個體中選取一定數(shù)量的個體作為初始種群.

I2G映射算法的具體實現(xiàn)詳見3.2.3節(jié).

3.2種群個體向量表示與初始種群生成

3.2.1種群個體向量表示

由于每個PE都可以向其他任意1個PE發(fā)送數(shù)據(jù)，CTG中的IP核可以映射到任意1個可用的PE上.因此，在3DNoC映射中種群個體采用整數(shù)編碼，假設(shè)個體X=(x1,x2,…,xn)，n為CTG的IP核個數(shù)，xi為IP核編號，個體X的編碼為1到n的1種排列，通過對編碼進(jìn)行解碼即可得到1種映射方案.1個簡單的16節(jié)點視頻對象平面解碼器芯片(videoobjectplanedecoder,VOPD)的通信軌跡圖如圖1所示[16]，以此圖為例來說明種群個體的向量表示.圖1中箭頭附近的數(shù)字表示節(jié)點間的通訊量，單位是MBps.

Fig. 1　VOPD communication trace diagram.圖1　VOPD 通信軌跡圖

VOPD中的IP核用數(shù)字1,2,…,16表示，將VOPD映射到2×3×3的3DNoC上，3DNoC上的每個PE用數(shù)字t1到t18表示，t1到t6表示第1層，t7到t12表示第2層，t13到t18表示第3層，如圖2所示.個體X=(2,3,4,1,16,5,7,6,11,15,14,12,13,10,8,9)，表示將IP核集(2,3,4,1,16,5,7,6,11,15,14,12,13,10,8,9)分別映射到處理單元t1到t16上，映射結(jié)果如圖3所示.將所有IP核映射到3DNoC上之后，計算3DNoC上所有節(jié)點之間的通信總量，用遺傳算法根據(jù)3DNoC上的通信總量計算其適應(yīng)值，通信總量越大，適應(yīng)值越小，用遺傳算法根據(jù)適應(yīng)值大小進(jìn)行遺傳操作.

Fig. 2　3D NoC topological structure圖2　3D NoC拓?fù)浣Y(jié)構(gòu)

Fig. 3　Mapping result圖3　映射結(jié)果

3.2.2應(yīng)用改進(jìn)貪心算法生成初始種群

應(yīng)用本文提出的改進(jìn)貪心算法生成初始種群(Pop)的主要過程如下：

算法3. 改進(jìn)貪心算法.

Step1. 將數(shù)字i放到個體X的第1個位置(i=1，2，…，N，當(dāng)選取每個i后，重復(fù)Step2到Step5，每次循環(huán)都生成1個個體).

Step2. 初始化可用集合P={1,2,…,N}，N為CTG的IP核個數(shù)，將i從可用集合P中刪除.

Step3. 遍歷可用集合P中的數(shù)字n，將n放入個體X的所有可用位置，計算放入這些位置后X的適應(yīng)值，從這些適應(yīng)值中找到最大的適應(yīng)值fit，記下n放到使得X適應(yīng)值最大的位置m，把n,m,fit存到集合F中.

Step4. 遍歷集合F，找到fit值最大的1個元素n,m,fit，把n放到個體X的第m個位置，并把n從可用集合P中刪除.

Step5. 重復(fù)Step3和Step4，直到可用集合P=?，當(dāng)P=?時，表示產(chǎn)生了新個體X，把X加入臨時種群tempPop中.

Step6. 重復(fù)上述Step5，生成N個個體.

Step7. 將個體X中的任意2個坐標(biāo)數(shù)字交換(即變異操作)，生成1個新個體Y，即X的鄰居個體.用此方法生成20個X的鄰居個體放入臨時種群tempPop中.

Step8. 從臨時種群tempPop中選取一定規(guī)模適應(yīng)值最大的個體放入Pop中.

3.2.3I2G映射算法實現(xiàn)

1) 低功耗映射實現(xiàn)流程

算法4.I2G映射算法.

Step1. 采用改進(jìn)貪心算法生成初始種群(詳見3.2.2節(jié)).

Step2. 用遺傳算法對初始種群進(jìn)行進(jìn)化操作，得到算法的最優(yōu)解.

Step3. 根據(jù)最優(yōu)解生成仿真平臺能夠識別的通信模式(trafficpattern)文件.

Step4. 仿真平臺讀取通信模式文件進(jìn)行仿真，得到3DNoC低功耗映射仿真結(jié)果.

2) 通信模式文件的生成過程

算法5. 通信模式文件生成.

Step1. 將CTG(N,C)里的邊集C，根據(jù)改進(jìn)遺傳算法得到最優(yōu)個體X，轉(zhuǎn)換成TAG的邊集E.例如：最優(yōu)個體X=(2,3,4,1,8,5,7,6)，邊c12，邊c12的權(quán)重w12=100，映射到TAG上后得到邊e41，邊e41的權(quán)重w41=100.統(tǒng)計所有邊的通信量之和wSum.

Step2. 生成隨機數(shù)1≤r≤n，如果第r條邊為e13，則在通信模式文件中寫入1 3，如果通信量等于0，則循環(huán)查找下一條邊，直到找到通信量大于0的邊，在通信模式文件中寫入該條邊的信息，將該條邊的通信量減1.

Step3. 重復(fù)Step2，直到所有邊的通信量為0.

4仿真實驗與結(jié)果分析

4.1仿真平臺與參數(shù)設(shè)計

4.1.1仿真平臺選擇

仿真實驗是在Ubuntu13操作系統(tǒng)下，采用C++語言編寫算法的實現(xiàn)程序，在codeblocks12.11環(huán)境下，采用AccessNoxim0.2作為仿真軟件進(jìn)行映射算法的仿真(AccessNoxim0.2對主流的2DNoC仿真軟件noxim進(jìn)行了改進(jìn)，改進(jìn)后可以用于3DNoC的仿真實驗).

4.1.2拓?fù)浣Y(jié)構(gòu)與路由選擇

1) 拓?fù)浣Y(jié)構(gòu)的選擇

3DMesh具有結(jié)構(gòu)規(guī)則、布線簡單、網(wǎng)絡(luò)節(jié)點位置平等且在垂直方向互連采用TSV技術(shù)減小了總體布線長度等優(yōu)點，實驗中采用了3DMesh結(jié)構(gòu).

2) 路由選擇

XYZ路由算法易于理解與實現(xiàn)，是主流的路由算法，實驗中采用了該路由算法.

4.1.3參數(shù)設(shè)置

1) 算法的參數(shù)設(shè)置.種群規(guī)模為200,遺傳迭代次數(shù)為100，交叉率為0.9，變異率為0.02.

2) 仿真軟件的參數(shù)設(shè)置.數(shù)據(jù)包采用無記憶泊松分布(memorylessPoissondistribution)方式注入，數(shù)據(jù)包的注入率(packetinjectionrate)設(shè)為0.02；仿真軟件統(tǒng)計循環(huán)5 000次的總功耗；數(shù)據(jù)包的大小介于2個微片到10個微片之間；路由器每個通道的緩存大小設(shè)為8個微片.

4.1.4硬件運行環(huán)境

整個仿真實驗的硬件環(huán)境是：CPU為Intel?CoreTMi3-2120,主頻為3.30GHz,內(nèi)存為4GB的微型計算機.

4.2仿真實驗結(jié)果分析

采用C++語言編寫了基于IG映射算法[15]和基于I2G映射算法的3DNoC低功耗映射程序，在上述環(huán)境下進(jìn)行了仿真實驗.

4.2.1經(jīng)典任務(wù)圖的功耗對比

1) 針對VOPD的功耗對比

首先針對2個經(jīng)典的通信軌跡圖VOPD和DVOPD(doublevideoobjectplanedecoder)進(jìn)行仿真實驗.其中，VOPD中有16個節(jié)點，如圖1所示，將VOPD映射到2×2×4的3DNoC上.仿真實驗中，分別采用IG映射算法和I2G映射算法對該任務(wù)圖進(jìn)行映射操作，用得到的最優(yōu)解生成通信模式文件，仿真器AccessNoxim通過讀取通信模式文件進(jìn)行映射仿真，得到映射功耗.用實驗數(shù)據(jù)分別對2種映射算法得到的最小功耗、平均功耗和最大功耗進(jìn)行了比較，如圖4所示：

Fig. 4　Comparison of two mapping algorithms’ power consumption for VOPD.圖4　針對VOPD的2種映射算法功耗對比

分析針對VOPD的2種映射算法仿真結(jié)果可見，在最低功耗方面I2G映射算法低于IG映射算法，即采用I2G映射算法的功耗更低，但是降低的幅度較??；而在平均功耗和最大功耗方面，I2G映射算法的功耗高于IG映射算法的功耗，I2G映射算法與IG映射算法的唯一區(qū)別就是生成初始種群時采用的貪心策略不同.對任務(wù)圖分別進(jìn)行實驗，由實驗結(jié)果可知：I2G映射算法與IG映射算法相比，最低功耗降低了2.02%、平均功耗增加了2.15%、最高功耗增加了1.54%.其中，I2G映射算法的功耗高于基于IG映射算法[16]的功耗，這是由于VOPD只有16個節(jié)點(節(jié)點過少)，采用改進(jìn)貪心策略得到的初始種群容易陷入局部最優(yōu).

2) 針對DVOPD的功耗對比

通信軌跡圖DVOPD有32個節(jié)點，如圖5所示[16]，圖5中箭頭附近的數(shù)字表示節(jié)點間的通訊量，單位是MBps.實驗中將DVOPD映射到2×2×4的3DNoC上，針對通信軌跡圖DVOPD分別用2種映射算法進(jìn)行了仿真實驗.

Fig. 5　DVOPD task communication diagram.圖5　DVOPD任務(wù)通信圖

Fig. 6　Comparison of two mapping algorithms’ power consumption for DVOPD.圖6　針對DVOPD的2種映射算法功耗對比

實驗中對任務(wù)通信圖DVOPD分別采用IG映射算法和I2G映射算法的仿真結(jié)果如圖6所示.I2G映射算法得到的仿真結(jié)果明顯優(yōu)于IG映射算法的仿真結(jié)果：I2G映射算法與IG映射算法相比，最低功耗降低了13.37%、平均功耗降低了9.18%、最高功耗降低了7.48%.功耗降低顯著，這是由于DVOPD有32個節(jié)點，任務(wù)規(guī)模較大，采用改進(jìn)貪心策略得到的初始種群不容易陷入局部最優(yōu).由以上實驗和分析可見，當(dāng)任務(wù)圖規(guī)模增大時，I2G映射算法的優(yōu)勢更為明顯.

4.2.2經(jīng)典任務(wù)圖映射算法運行時間對比

IG映射算法和I2G映射算法的運行時間對比如圖7所示.由圖7可見，I2G映射算法的運行時間明顯少于IG映射算法的運行時間.對于VOPD，由于任務(wù)圖規(guī)模較小，生成每個個體所用的時間較短，因此I2G算法的運行時間減少幅度較小，比IG映射算法減少了19.11%(I2G映射算法的運行時間為3.619s、IG映射算法的運行時間為4.474s)；而對于DVOPD，I2G映射算法的運行時間比IG映射算法的運行時間[15]減少幅度增大、減少了68.90%(I2G映射算法的運行時間為5.444s、IG映射算法的運行時間為17.503s).

Fig. 7　Comparison of two mapping algorithms’ running time.圖7　2種映射算法運行時間對比

4.2.3200種群規(guī)模下隨機任務(wù)圖的功耗對比

1) 仿真實驗數(shù)據(jù)

采用任務(wù)生成器TGFF[17]生成隨機任務(wù)圖，針對不同IP核數(shù)的CTG、種群規(guī)模為200時，分別采用IG映射算法和I2G映射算法求解10次，得到的功耗如表1和表2所示(對仿真實驗數(shù)據(jù)從低到高進(jìn)行了排序).

Table 1　Experimental Results of Ten Simulation for IG Mapping Algorithm

Table 2　Experimental Results of Ten Simulation for I2G Mapping Algorithm

2) 最低功耗比較

當(dāng)IP核數(shù)較少時，I2G映射算法相對于IG映射算法的最低功耗降低幅度較小，在10%以內(nèi).其中，21個IP核時，I2G映射算法比IG映射算法的功耗低了17.46%，這是由于IP核數(shù)目較少，容易導(dǎo)致2種算法均陷入局部最優(yōu)，因此出現(xiàn)了在21個IP核時I2G映射算法的功耗降低幅度較大.從整體趨勢來看，隨著IP核數(shù)的增加，功耗降低幅度增加，如圖8所示.當(dāng)IP核數(shù)為121時，I2G映射算法比IG映射算法功耗降低了22.64%.

Fig. 8　Comparison of two mapping algorithms’ minimum power consumption.圖8　2種映射算法最低功耗對比

3) 最高功耗對比

當(dāng)IP核個數(shù)為21時，I2G映射算法相對于IG映射算法最高功耗降低了17.40%.當(dāng)IP核個數(shù)為82時，I2G映射算法比IG映射算法的最高功耗降低了19.25%(為所做實驗的最大降低幅度)，如圖9所示.當(dāng)IP核數(shù)為121時，I2G映射算法相比IG映射算法最高功耗降低了13.95%.

Fig. 9　Comparison of two mapping algorithms’ maximum power consumption.圖9　2種映射算法最高功耗對比

4) 平均功耗對比

當(dāng)IP核數(shù)為21時，I2G映射算法比IG映射算法平均功耗降低了14.85%；當(dāng)IP核數(shù)為82時，I2G映射算法比IG映射算法平均功耗降低了13.61%；當(dāng)IP核數(shù)為121時，I2G映射算法相比IG映射算法平均功耗降低了17.18%(為所做實驗的最大值)，如圖10所示：

Fig. 10　Comparison of two mapping algorithms’ average power consumption.圖10　2種映射算法平均功耗對比

4.2.4種群規(guī)模200隨機任務(wù)圖運行時間對比

種群規(guī)模為200時2種映射算法的運行時間對比如圖11所示.由圖11可見，I2G映射算法比IG映射算法的運行時間顯著減少；當(dāng)IP核數(shù)為59時，I2G映射算法比IG映射算法的運行時間減少了74.05%.

Fig. 11　Comparison of two mapping algorithms’ running time with a population size of 200.圖11　種群規(guī)模為200的2種映射算法運行時間對比

4.2.5300種群規(guī)模隨機任務(wù)圖功耗與時間對比

1) 2種映射算法功耗對比

種群規(guī)模為300時，2種映射算法平均功耗的比較如圖12所示.IP核數(shù)為121時，I2G映射算法比IG映射算法的功耗降低了13.48%.

2) 2種映射算法運行時間對比

種群規(guī)模為300時I2G映射算法與IG映射算法運行時間對比如圖13所示.IP核數(shù)為121時，I2G映射算法比IG映射算法的運行時間減少了85.56%.

4.2.6隨機任務(wù)圖不同種群規(guī)模下運行時間對比

2種映射算法在IP核數(shù)為82時，種群規(guī)模不同時的運行時間對比如圖14所示.當(dāng)種群規(guī)模為600時，I2G映射算法比IG映射算法運行時間減少了89.98%(此時功耗降低16.36%).隨著種群規(guī)模的增大，I2G映射算法的運行時間比IG映射算法的運行時間減少幅度逐漸增大；隨著種群規(guī)模的增加，IG映射算法的運行時間大幅度增加，而I2G映射算法的運行時間變動幅度很小(這是由于I2G映射算法采用了改進(jìn)貪心策略生成初始種群，因此，種群規(guī)模對映射算法的運行時間影響很小).

Fig. 12　Comparison of two mapping algorithms’ average power consumption with a population size of 300.圖12　種群規(guī)模為300時2種映射算法平均功耗對比

Fig. 13　Comparison of two mapping algorithms’ average power consumption with a population size of 300.圖13　種群規(guī)模為300時2種映射算法平均功耗對比

Fig. 14　Comparison of two mapping algorithms’s running time with different population sizes and 82 IP cores.圖14　IP核數(shù)82時不同種群規(guī)模2種映射算法運行時間對比

4.2.7映射算法收斂速度對比

針對VOPD的收斂速度對比如圖15所示，從迭代開始IG映射算法得到的適應(yīng)值要遠(yuǎn)遠(yuǎn)大于基本遺傳算法和I2G映射算法，而且在之后的進(jìn)化過程中，IG映射算法得到的適應(yīng)值變化很小，這說明在任務(wù)圖規(guī)模較小時，IG映射算法容易陷入局部最優(yōu).

Fig. 15　Convergence speed for two VOPD mapping algorithms.圖15　針對VOPD的2種映射算法的收斂速度對比

針對DVOPD在100次的迭代過程中收斂速度對比如圖16所示，基本遺傳算法的收斂速度比較慢，最終得到的適應(yīng)值要小于另外2種映射算法；IG映射算法的收斂速度比基本遺傳算法快，但是比I2G映射算法慢；I2G映射算法在算法運行初期得到的最大適應(yīng)值要比IG映射算法小，而算法運行后期I2G映射算法收斂速度更快，而且得到的適應(yīng)值更大.

Fig. 16　Convergence speed for two DVOPD mapping algorithms.圖16　針對DVOPD的2種映射算法的收斂速度對比

5結(jié)論與展望

5.1結(jié)論

針對IG映射算法運行時間較長的問題，本文提出了基于I2G算法的3DNoC低功耗映射算法(簡稱I2G映射算法).仿真結(jié)果表明，隨著種群規(guī)模的增大，I2G映射算法在功耗繼續(xù)保持降低的前提下，運行時間大幅度地減少.特別是，當(dāng)IP核數(shù)為82、種群規(guī)模為600時，I2G映射算法與IG映射算法相比，平均功耗降低了16.36%，運行時間減少了89.98%.仿真實驗表明，本文所提出的I2G映射算法效果顯著.

5.2展望

1) 本文采用XYZ路由算法進(jìn)行了I2G映射算法的仿真實驗，在今后的研究中將對動態(tài)路由策略下的映射問題進(jìn)行研究.

2) 發(fā)熱是3DNoC設(shè)計中需要考慮的重要問題，隨著研究的深入，我們將在映射算法研究中加入發(fā)熱等方面因素的考慮.

3) 隨著專用3DNoC需求的增多，出現(xiàn)了許多異構(gòu)3DNoC架構(gòu)，例如基于異構(gòu)布局、位移交換和基于樹圖的3DNoC架構(gòu). 目前，針對異構(gòu)3DNoC架構(gòu)的映射算法的研究還處于起步階段，還有很大的發(fā)展空間. 在未來的研究中，可以充分利用異構(gòu)特征，針對不同類型的任務(wù)通信圖采用不同的映射算法來提高3DNoC的映射效率并降低系統(tǒng)的功耗.

4) 目前有一種映射方法是將任務(wù)圖映射到子網(wǎng)絡(luò)上，并將子網(wǎng)絡(luò)用定位的方式在片上網(wǎng)絡(luò)中找到相應(yīng)大小的區(qū)域，最后將任務(wù)圖映射到該區(qū)域. 采用這樣的映射方式，多個任務(wù)的映射可同時進(jìn)行. 但由于任務(wù)通信圖與子網(wǎng)絡(luò)上處理單元大小存在不一致性，往往造成子網(wǎng)絡(luò)上處理單元的浪費。減少處理單元的浪費將是一個值得研究的課題.

參考文獻(xiàn)

[1]LeeK,LeeSJ,KimD,etal.Networks-on-chipandnetworks-in-packageforhigh-performanceSoCplatforms[C] //Procofthe2005ConfonAsianSolid-StateCircuits.NewYork:ACM, 2005: 485-488

[2]PavlidisVF,FriedmanEG. 3-Dtopologiesfornetworks-on-chip[J].IEEETransonVeryLargeScaleIntegrationSystems, 2007, 15(10): 1081-1090

[3]DavisWR,WilsonJ,MickS,etal.Demystifying3DICs:Theprosandconsofgoingvertical[J].IEEEDesign&TestofComputers, 2005, 22(6): 498-510

[4]JohnsonDS,GareyM.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].SanFrancisco,CA:Freeman&Co, 1979

[5]CharlesAQ.Thermal-awaremappingandplacementfor3-DNoCdesigns[C] //Procofthe2005IntConfonSOC.NewYork:ACM, 2005: 25-28

[6]WangJiawen. 3DNockeytechnologyresearch[D].Nanjing:NanjingUniversity, 2012 (inChinese)(王佳文. 3DNoC關(guān)鍵技術(shù)研究[D]. 南京: 南京大學(xué), 2012)

[7]WangJiawen,LiLi,WangZhongfeng,etal.Energy-efficientmappingfor3DNoCusinglogisticfunctionbasedadaptivegeneticalgorithms[J].ChineseJournalofElectronics, 2014, 23(2): 254-262

[8]WangJiawen,LiLi,HongBingpan,etal.Latency-awaremappingfor3DNoCusingrank-basedmulti-objectivegeneticalgorithm[C] //Procofthe2011ConfonASIC.NewYork:ACM, 2011: 413-416

[9]ElmiligiH,GebaliF,El-Kharashi,etal.Power-awaremappingfor3DNoCdesignsusinggeneticalgorithms[J].ProcediaComputerScience, 2014, 34: 538-543

[10]GeFen,FengGui,YuShuang,etal.Power-andthermal-awaremappingfor3Dnetwork-on-chip[J].InformationTechnologyJournal, 2013, 12(23): 7297-7304

[11]WangXiaohang,LiuPeng,YangMei,etal.Energyefficientrun-timeincrementalmappingfor3Dnetworks-on-chip[J].JournalofComputerScienceandTechnology, 2013, 28(1): 54-71

[12]ZhangZhen.Researchofmappingmethodsfor3D-mesh-orientedCMPnetworksonchip[D].Guangzhou:GuangdongUniversityofTechnology, 2012 (inChinese)(張振. 基于3D-MESH的CMP片上網(wǎng)絡(luò)映射方法研究[D]. 廣州: 廣東工業(yè)大學(xué), 2012)

[13]QianYue,LuZhonghai,DouQiang,etal.CommunicationperformanceanalysisoftheNoCsin2Dand3Darchitectures[J].ComputerEngineering&Science, 2011, 33(3): 34-40 (inChinese)(錢悅, 魯中海, 竇強, 等. 片上網(wǎng)絡(luò)二維和三維結(jié)構(gòu)的通信性能分析[J]. 計算機工程與科學(xué), 2011, 33(3): 34-40)

[14]MatsutaniH,KoibuchiM,AmanoH.Tightly-coupledmulti-layertopologiesfor3-DNoCs[C] //Procofthe2007ConfonParallelProcessing.NewYork:ACM, 2007: 75-79

[15]LinHuaZhou,ZhangDaKun,HuangCui.Researchonlow-powermappingforthree-dimensionalnetwork-on-chipbasedonimprovedgeneticalgorithm[J].ComputerEngineering&Application, 2016, 52(1): 81-88 (inChinese)(林華洲, 張大坤, 黃翠. 基于改進(jìn)遺傳算法的3DNoC低功耗映射研究[J]. 計算機工程與應(yīng)用, 2016, 52(1): 81-88)

[16]PradipKS,SantanuC.Asurveyonapplicationmappingstrategiesfornetwork-on-chipdesign[J].JournalofSystemsArchitecture, 2013, 59(1): 60-76

[17]DickRP,RhodesDL,WolfW.TGFF:Taskgraphsforfree[C] //Procofthe1998ConfonHardware/SoftwareCodesign.NewYork:ACM, 1998: 97-101

ZhangDakun,bornin1960.ReceivedherPhDdegreeincomputertechnologyfromNortheasternUniversity.ProfessoratTianjinPolytechnicUniversity.Hermainresearchinterestsinclude3Dnetworks-on-chip,bigdatavisualizationanalysis,andvirtualreality.

SongGuozhi,bornin1977.ReceivedhisPhDdegreefromQueenMary,UniversityofLondon,UK.AssociateprofessoratTianjinPolytechnicUniversity.Hismainresearchinterestsinclude3Dnetworks-on-chip,heterogeneouswirelessnetworkintegration,andqueueingtheory(guozhi.song@gmail.com).

LinHuazhou,bornin1990.MScandidate.Hisresearchinterestsinclude3Dnetworks-on-chip(linhuazhou90@126.com).

RenShuxia,bornin1973.ReceivedherPhDdegreefromTianjinUniversity.Associateprofessor.Herresearchinterestsinclude3Dnetworks-on-chip,datamining,andbigdataanalysis(t_rsx@126.com).

2014年《計算機研究與發(fā)展》高被引論文TOP10

數(shù)據(jù)來源：中國知網(wǎng),CSCD；統(tǒng)計日期：2016-02-16

DoubleImprovedGeneticAlgorithmandLowPowerTaskMappingin3DNetworks-on-Chip

ZhangDakun,SongGuozhi,LinHuazhou,andRenShuxia

(School of Computer Science & Software Engineering, Tianjin Polytechnic University, Tianjin 300387)

AbstractWith the rapid development of integrated circuit technology, the number of integrated components on a chip continues to increase. Efficient interconnection between the processing units on chip becomes a key issue. Therefore firstly system-on-chip (SoC) and then two-dimensional networks-on-chip (2D NoC) have been proposed to cope with this problem. But now even the 2D NoC has reached a bottleneck in many aspects, so the design of Three-Dimensional networks-on-chip (3D NoC) is inevitable. 3D NoC has attracted the attention of the researchers from both Academia and industry. One of the key issues of 3D NoC is low-power mapping. We have previously proposed a 3D NoC low-power mapping algorithm based on improved genetic algorithm with good results. But when the scale of the problem gets larger, the amount of calculation increases gradually and operation efficiency is reduced significantly. To solve this problem, this paper proposes a new 3D NoC task mapping algorithm with power optimization based on a double improved genetic algorithm, and the simulation experiments are conducted to validate the algorithm. The results show that under the conditions of a large population size, the 3D NoC task mapping algorithm cannot only reduce the power, but also reduce the running time significantly.

Key words3D network-on-chip (3D NoC); low-power mapping; improved genetic algorithm; double improved genetic algorithm; Greedy algorithm

收稿日期：2015-07-23；修回日期：2016-01-22

基金項目：國家自然科學(xué)基金項目(61272006)

中圖法分類號TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61272006).