張大坤　宋國(guó)治　林華洲　任淑霞

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

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

張大坤宋國(guó)治林華洲任淑霞

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

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

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

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

13DNoC低功耗映射問(wèn)題

1.1基本概念

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

定義1. 通信軌跡圖CTG(N,C).設(shè)CTG(N,C)為有向圖，其中N為頂點(diǎn)集，節(jié)點(diǎn)ni∈N表示1個(gè)IP核;C為邊集，有向邊ci j∈C表示節(jié)點(diǎn)ci到節(jié)點(diǎn)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個(gè)PE;E為邊集，有向邊ei j表示節(jié)點(diǎn)ti到節(jié)點(diǎn)tj的邊[11-12].

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

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

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

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

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

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

1.33DNoC功耗模型

1.3.13DNoC功耗計(jì)算公式

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

(1)

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

(2)

(3)

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

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

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

(4)

且滿足條件：

(5)

(6)

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

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

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

2.1問(wèn)題簡(jiǎn)介

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

算法1. 遺傳算法.

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

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

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

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

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

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

2.2IG映射算法的核心思想

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

算法2. 貪心算法.

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

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

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

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

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

3.1問(wèn)題的提出與算法描述

3.1.1問(wèn)題的提出

2.2節(jié)中的IG映射算法是采用貪心算法生成初始種群中的每個(gè)個(gè)體，使初始種群的質(zhì)量整體得到了提升，有效地降低了功耗.但該算法在生成初始種群時(shí)，單個(gè)個(gè)體生成的計(jì)算量較大，在確定1個(gè)IP核映射到3DNoC上時(shí)，會(huì)計(jì)算所有未映射到3DNoC上的IP核放到3DNoC上所有可用位的適應(yīng)值,而且生成每個(gè)個(gè)體都要進(jìn)行同樣的運(yùn)算，所以該算法在生成初始種群時(shí)運(yùn)行效率明顯低于基本遺傳算法.針對(duì)這一問(wèn)題，對(duì)3DNoC中面向功耗優(yōu)化的二次改進(jìn)遺傳算法任務(wù)映射機(jī)制進(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，隨機(jī)地將1個(gè)IP核(用n表示)映射到3DNoC的第1個(gè)位置(數(shù)字n可重復(fù)出現(xiàn))，而改進(jìn)貪心算法中在第1個(gè)位置上放置的IP核(n)不可重復(fù)出現(xiàn)(n=1，2，…，N).

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

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

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

3.2種群個(gè)體向量表示與初始種群生成

3.2.1種群個(gè)體向量表示

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

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

VOPD中的IP核用數(shù)字1,2,…,16表示，將VOPD映射到2×3×3的3DNoC上，3DNoC上的每個(gè)PE用數(shù)字t1到t18表示，t1到t6表示第1層，t7到t12表示第2層，t13到t18表示第3層，如圖2所示.個(gè)體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上之后，計(jì)算3DNoC上所有節(jié)點(diǎn)之間的通信總量，用遺傳算法根據(jù)3DNoC上的通信總量計(jì)算其適應(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)的主要過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

算法4.I2G映射算法.

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

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

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

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

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

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

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

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

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

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

4.1仿真平臺(tái)與參數(shù)設(shè)計(jì)

4.1.1仿真平臺(tái)選擇

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

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

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

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

2) 路由選擇

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

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

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

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

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

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

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

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

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

1) 針對(duì)VOPD的功耗對(duì)比

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

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

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

2) 針對(duì)DVOPD的功耗對(duì)比

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

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

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

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

4.2.2經(jīng)典任務(wù)圖映射算法運(yùn)行時(shí)間對(duì)比

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

Fig. 7　Comparison of two mapping algorithms’ running time.圖7　2種映射算法運(yùn)行時(shí)間對(duì)比

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

1) 仿真實(shí)驗(yàn)數(shù)據(jù)

采用任務(wù)生成器TGFF[17]生成隨機(jī)任務(wù)圖，針對(duì)不同IP核數(shù)的CTG、種群規(guī)模為200時(shí)，分別采用IG映射算法和I2G映射算法求解10次，得到的功耗如表1和表2所示(對(duì)仿真實(shí)驗(yàn)數(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ù)較少時(shí)，I2G映射算法相對(duì)于IG映射算法的最低功耗降低幅度較小，在10%以內(nèi).其中，21個(gè)IP核時(shí)，I2G映射算法比IG映射算法的功耗低了17.46%，這是由于IP核數(shù)目較少，容易導(dǎo)致2種算法均陷入局部最優(yōu)，因此出現(xiàn)了在21個(gè)IP核時(shí)I2G映射算法的功耗降低幅度較大.從整體趨勢(shì)來(lái)看，隨著IP核數(shù)的增加，功耗降低幅度增加，如圖8所示.當(dāng)IP核數(shù)為121時(shí)，I2G映射算法比IG映射算法功耗降低了22.64%.

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

3) 最高功耗對(duì)比

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

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

4) 平均功耗對(duì)比

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

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

4.2.4種群規(guī)模200隨機(jī)任務(wù)圖運(yùn)行時(shí)間對(duì)比

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

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

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

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

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

2) 2種映射算法運(yùn)行時(shí)間對(duì)比

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

4.2.6隨機(jī)任務(wù)圖不同種群規(guī)模下運(yùn)行時(shí)間對(duì)比

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

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

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

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

4.2.7映射算法收斂速度對(duì)比

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

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

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

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

5結(jié)論與展望

5.1結(jié)論

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

5.2展望

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

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

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

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

參考文獻(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)(錢悅, 魯中海, 竇強(qiáng), 等. 片上網(wǎng)絡(luò)二維和三維結(jié)構(gòu)的通信性能分析[J]. 計(jì)算機(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]. 計(jì)算機(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年《計(jì)算機(jī)研究與發(fā)展》高被引論文TOP10

數(shù)據(jù)來(lái)源：中國(guó)知網(wǎng),CSCD；統(tǒng)計(jì)日期：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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61272006)

中圖法分類號(hào)TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61272006).