基于Prim初始種群選取優(yōu)化遺傳算法的三維片上網(wǎng)絡(luò)低功耗映射

宋國治，王 鋮，涂 遙，張大坤

(1.天津工業(yè)大學(xué) 計算機(jī)科學(xué)與軟件學(xué)院，天津 300387； 2.云南大學(xué) 信息學(xué)院，昆明 650091)

(*通信作者電子郵箱guozhi.song@googlemail.com)

基于Prim初始種群選取優(yōu)化遺傳算法的三維片上網(wǎng)絡(luò)低功耗映射

宋國治1*，王 鋮1,2，涂 遙1，張大坤1

(1.天津工業(yè)大學(xué) 計算機(jī)科學(xué)與軟件學(xué)院，天津 300387； 2.云南大學(xué) 信息學(xué)院，昆明 650091)

(*通信作者電子郵箱guozhi.song@googlemail.com)

針對將計算任務(wù)合理地映射到三維片上網(wǎng)絡(luò)(NoC)的問題，提出了一種基于遺傳算法(GA)的改進(jìn)算法。GA具有快速隨機(jī)的搜索能力，Prim算法可在加權(quán)連通圖內(nèi)得到最小生成樹，改進(jìn)算法結(jié)合了兩種算法的優(yōu)勢，將計算任務(wù)合理地分配到各個網(wǎng)絡(luò)節(jié)點，對于優(yōu)化三維片上網(wǎng)絡(luò)功耗和散熱等問題具有很高的效率。通過仿真實驗，對所提出的基于Prim算法的改進(jìn)GA與基本GA的3D NoC映射算法進(jìn)行了對比，仿真結(jié)果顯示，基于Prim算法的改進(jìn)GA平均功耗更低，從總體趨勢來看，處理單元數(shù)量的增加與功耗降低幅度成正相關(guān)，在101個處理單元情況下，平均功耗比基本GA降低32%。

三維片上網(wǎng)絡(luò)；低功耗；映射算法；遺傳算法；Prim算法

0 引言

近年來，隨著集成電路工藝和多核體系的飛速發(fā)展，芯片上集成的IP(Intellectual Property)核數(shù)目愈來愈多，用戶對嵌入式產(chǎn)品功能與性能的要求也愈來愈高，總線型結(jié)構(gòu)已經(jīng)不能完全滿足眾多的剛性需求。在這個背景下，二維片上網(wǎng)絡(luò)(Network-on-Chip, NoC)解決了SoC(System-on-Chip)面臨的一系列問題，但是從根本上依然避免不了由于芯片上IP核數(shù)的增加，芯片的面積有限、功耗不斷增大、芯片中全局導(dǎo)線的長度增加、工作頻率提升空間的限制所導(dǎo)致的關(guān)鍵部件路徑無法最短、功耗開銷增大和連線延遲等相關(guān)問題[1]。因此，三維片上網(wǎng)絡(luò)的概念被提出。與2D NoC相比，3D NoC的優(yōu)勢表現(xiàn)在全局互連更短、延時更低，系統(tǒng)性能更優(yōu)秀、功耗更低、封裝密度更高、芯片面積更小等方面，并且為混合芯片提供了連接方式。

在3D NoC領(lǐng)域中的關(guān)鍵性問題被美國卡內(nèi)基梅隆大學(xué)(Carnegie Mellon University)的Morgan等[2]歸納為三大類：3D NoC架構(gòu)、3D NoC通信和3D NoC映射。其中映射是研究如何將計算任務(wù)合理地映射到各個IP核上，這也是在片網(wǎng)設(shè)計階段需要解決一個重要的研究問題，3D NoC映射算法性能的提升對最終系統(tǒng)的執(zhí)行時間、通信時延、通信能耗等性能均有很大影響[3]。NoC映射是在已知NoC體系結(jié)構(gòu)和IP核間通信量的基礎(chǔ)上，按特定的算法將各IP核分配到NoC中各資源節(jié)點上，其中對應(yīng)關(guān)系需要滿足一定的條件限制，屬于非確定多項式(Non-Deterministic Polynomial, NP)問題中受約束的二次分配問題。

本文在應(yīng)用于三維片上網(wǎng)絡(luò)映射的基本遺傳算法基礎(chǔ)上，在初始種群選取階段結(jié)合Prim算法，形成一種基于Prim算法的改進(jìn)遺傳算法，并應(yīng)用到3D NoC低功耗映射問題中，提高了搜索性能并大幅降低了功耗。本文首先介紹了遺傳算法的原理，然后給出改進(jìn)遺傳的具體步驟，最后通過仿真實驗驗證算法的有效性。

1 3D NoC低功耗映射問題描述

1.1 基本概念

3D NoC映射的任務(wù)是探尋任務(wù)圖上每個任務(wù)與3D NoC上資源節(jié)點之間的一種對應(yīng)關(guān)系。在已知通信軌跡圖和映射結(jié)構(gòu)的條件下，降低網(wǎng)絡(luò)延遲和功耗，尋找一種優(yōu)秀的映射方案。

為了詳細(xì)地說明映射和路由問題，本文用數(shù)學(xué)方式給出必要的定義表示NoC映射過程。

定義1 有一個任務(wù)圖G∈V，應(yīng)用特征圖的每一個頂點vi∈V代表一個任務(wù)，并且每一條邊ei, j∈E代表兩個任務(wù)vi和vj間的通信，vi和vj間的數(shù)據(jù)傳輸量作為通信的權(quán)重。

定義2 有一個任務(wù)圖M(T,P),拓?fù)浣Y(jié)構(gòu)中的每一個點ti∈T代表一條邊，pi, j∈P代表ti到tj的一條通信路徑。gi, j代表ti到tj發(fā)送一位數(shù)據(jù)的平均功耗。

1.2 能耗模型

本文的研究目標(biāo)是在NoC體系結(jié)構(gòu)的網(wǎng)絡(luò)資源中最大限度地減少所消耗的能量。網(wǎng)絡(luò)結(jié)構(gòu)中的功耗與網(wǎng)絡(luò)中的通信量有直接關(guān)系。為了估計NoC體系結(jié)構(gòu)的功耗，應(yīng)該使用一個基于總傳輸量的功耗模型，其定義如下：

ETbit=ESbit+EBbit+EWbit+ELbit

(1)

式中:ESbit、EBbit、EWbit、ELbit分別代表交換機(jī)、緩沖器、結(jié)構(gòu)中的內(nèi)部線和鏈接所消耗的能量，則1 bit數(shù)據(jù)在NoC傳輸一個基本長度的能耗可以表示為：

ETbit=ESbit+EBbit+EWbit

(2)

同時來自緩沖和內(nèi)部線的能源消耗可以忽略不計，所以可將式(2)修改為：

ETbit=ESbit+ELbit

(3)

然后，從核心i到核心j發(fā)送1 bit數(shù)據(jù)的平均能量消耗的計算公式為：

(4)

(ni, j+1)代表數(shù)據(jù)在傳送過程中數(shù)據(jù)經(jīng)過的路由器的數(shù)量，如果1 bit數(shù)據(jù)通過(ni, j+1)個路由器，顯然，它還通過(ni, j+1)條鏈接，這是所謂的核心i到核心j之間的距離跳數(shù)。式(4)表明，最小化通信核心的距離跳數(shù)可以最小化核心i到核心j之間發(fā)送1 bit數(shù)據(jù)的功耗。

1.3 種群個體向量表示

經(jīng)典應(yīng)用特征圖PIP(Picture-In-Picture)包含8個節(jié)點，如圖1所示，圖中的IP核用數(shù)字1到8表示，將PIP中的節(jié)點映射到2×2×2的3D Mesh結(jié)構(gòu)上。假設(shè)個體Y=(y0，y1，y2，…，yM-1)，M為任務(wù)圖的IP核個數(shù)，yi為IP核編號。

將PIP映射到2×2×2的3DNoC上，3DNoC上的每個處理單元(ProcessingElement,PE)用數(shù)字t1到t8表示。

t1到t4表示第1層(圖2(a))，t5到t8表示第2層(圖2(b))。個體y=(6,1,2,4,8,5,7,3)，表示將IP核集(2,3,4,1,8,9,5,10,11,7,6,12)分別映射到PE集(1,2,3,4,5,6,7,8)上，映射結(jié)果如圖3所示。

圖1 任務(wù)通信圖PIP

圖2 NoC拓?fù)浣Y(jié)構(gòu)

圖3 映射結(jié)果

2 映射算法基礎(chǔ)

優(yōu)秀的映射算法可以讓系統(tǒng)在能耗[4-5]、延時[6]等方面的性能大為改善。近年來國內(nèi)外研究學(xué)者已提出多種算法并應(yīng)用于NoC映射中。目前，3DNoC的映射算法有許多種分類方法，近年來在學(xué)術(shù)界比較公認(rèn)的有以下四種。

2.1 基于禁忌搜索算法

禁忌搜索(TabuSearch或TabooSearch，TS)是擴(kuò)展局部領(lǐng)域搜索之后的一種全局逐步尋優(yōu)算法。它的主體思想是對已搜索的局部最優(yōu)解的對象進(jìn)行標(biāo)記，并在以后的迭代搜索中盡量地不出現(xiàn)這些對象，從而盡量做到探索不同的有效搜索途徑。

常政威等[7]提出了一種有效的改進(jìn)禁忌搜索(TabuSearchforNoCMapping,TSNM)算法。采用禁忌搜索和遺傳算法混合優(yōu)化策略，先對RoTS(RobustTabuSearch)進(jìn)行簡化，再實現(xiàn)對求解空間局部區(qū)域的集中搜索，并用COHX(COHesivecrossover)交叉操作完成分散搜索。

2.2 基于蟻群算法

蟻群優(yōu)化(AntColonyOptimization,ACO)算法是通過模擬自然界中的螞蟻的尋找路徑的方式而得出的一種優(yōu)化算法。

南京大學(xué)微電子設(shè)計研究所的楊盛光等基于二維網(wǎng)格結(jié)構(gòu)NoC平臺[8]，建立了統(tǒng)一的目標(biāo)函數(shù)，降低了系統(tǒng)通信功耗和執(zhí)行的時間，提出了一種通過優(yōu)化鏈路負(fù)載分布進(jìn)而間接降低延時的方法，并且通過蟻群算法實現(xiàn)了前面提到的面向能耗和延時的NoC映射。

南京大學(xué)物理系微電子設(shè)計研究所的王佳文等[9]基于基本蟻群算法(AntColonyAlgorithm,ACA)，總結(jié)出一種動態(tài)蟻群算法(DynamicAntColonyAlgorithm,DACA)。

李東生等[10]基于2DNoC的映射規(guī)則，總結(jié)出了針對3D網(wǎng)格NoC的通信能耗模型，并運用蟻群算法實現(xiàn)了面向通信能耗的NoC映射。

2.3 基于粒子群算法

粒子群算法是通過模擬自然界中的鳥類覓食行為而得出的一種優(yōu)化算法，Eberhart和Kennedy從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。

黃翠[11]利用量子粒子群算法具有全局收斂性、收斂速度快、尋優(yōu)能力強(qiáng)、控制參數(shù)少以及魯棒性等諸多優(yōu)點，首次將量子粒子群算法應(yīng)用到三維片上網(wǎng)絡(luò)低功耗映射問題中，但當(dāng)應(yīng)用特征圖規(guī)模較大時，功耗優(yōu)化效率降低。針對這一問題，她又提出一種基于多樣性控制量子粒子群的三維片上網(wǎng)絡(luò)低功耗映射算法。

楊微等[12]提出一種改進(jìn)的粒子群算法以及相應(yīng)的算法評估模型。該算法通過引入非支配解(Pareto解)的概念對粒子群算法進(jìn)行改進(jìn)，使得算法能對多個評估模型參數(shù)同時優(yōu)化，并且還能根據(jù)特定的應(yīng)用對單個評估模型參數(shù)進(jìn)行優(yōu)化。

2.4 基于遺傳算法

遺傳算法(GeneticAlgorithm,GA)是通過模擬自然界中生物進(jìn)化的自然選擇和遺傳中發(fā)生的繁殖、交叉和基因突變現(xiàn)象而得到的優(yōu)化算法。

Lei等[13]采用分步式遺傳算法進(jìn)行映射處理，并且先后從粗、細(xì)2種粒度上進(jìn)行，通過參數(shù)化的任務(wù)圖的描述，算法找到一個映射的任務(wù)圖的頂點的映射，使任務(wù)圖的整體執(zhí)行時間被最小化。

Ascia等[14]用遺傳算法求解多目標(biāo)優(yōu)化的NoC映射，它提出了一種多目標(biāo)探索映射空間網(wǎng)狀網(wǎng)絡(luò)基礎(chǔ)上的芯片架構(gòu)。該方法可以高效、準(zhǔn)確地來獲得帕累托映射優(yōu)化性能和功耗。

張濤濤[15]提出的映射算法的設(shè)計主要依據(jù)混合型3DNoC-Bus拓?fù)浣Y(jié)構(gòu)中垂直總線的相關(guān)特征，創(chuàng)造優(yōu)化算法的計算模型，通過遺傳算法和回溯算法來尋找最優(yōu)解。

Addo-Quaye[16]把遺傳算法應(yīng)用到三維片上網(wǎng)絡(luò)映射問題，并進(jìn)行求解，提出了一種基于3DMesh,降低芯片溫度與網(wǎng)絡(luò)通信開銷的映射算法。

Ying等[17]提出了一種基于遺傳算法的映射優(yōu)化方案，這個方案主要研究了硅穿孔(ThroughSiliconVia,TSV)數(shù)目和系統(tǒng)性能的關(guān)系。

Wang等[18]針對3DNoC延遲感知提出基于排序的多任務(wù)遺傳算法。

林華洲等[19]指出：隨著3DNoC集成度的提高，低功耗映射逐漸受到了關(guān)注。他將遺傳算法和貪心算法結(jié)合為一種改進(jìn)的遺傳算法，用以解決3DNoC低功耗映射問題。與基本遺傳算法相比，基于貪心算法的改進(jìn)遺傳算法的搜索能力更加優(yōu)秀。

3 遺傳算法及改進(jìn)

3.1 基本遺傳算法

1975年，美國的Holland教授[20]提出了遺傳算法(GA)的概念，遺傳算法是通過模擬自然界中生物進(jìn)化的自然選擇和遺傳中發(fā)生的繁殖、交叉和基因突變現(xiàn)象而得到的優(yōu)化算法。隨機(jī)初始化群體，利用此群體進(jìn)行迭代，每次迭代后保留一組最優(yōu)候選解，利用選擇、交叉、變異對解空間中的解集進(jìn)行組合，產(chǎn)生新的解空間，直到滿足停止準(zhǔn)則[21]。

3.2 Prim算法

基本思想 假設(shè)G=(V,E)是連通的，TE是G上最小生成樹中邊的集合。算法從U={u0}(u0∈V)、TE={}開始。重復(fù)執(zhí)行下列操作：

在所有u∈U，v∈V-U的邊(u,v)∈E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中，同時v0并入U，直到V=U為止。

此時，TE中必有n-1條邊，T=(V,TE)為G的最小生成樹。

3.3 改進(jìn)遺傳算法

3.3.1 改進(jìn)遺傳算法的提出

類似于其他尋找最優(yōu)組合的問題，尋找從G(V,E)到P(U,F)的映射最優(yōu)解，是一類NP難問題。本文的目的是要尋找一個或者一些能夠在性能和尋優(yōu)計算時間上獲得平衡的方案。遺傳算法在這兩方面表現(xiàn)出它的優(yōu)勢。遺傳算法適合解決3DNoC映射問題，其他優(yōu)化算法在解決3DNoC映射問題上也有各自的優(yōu)點，但本文主要是針對初始種群的優(yōu)化，并不涉及采用何種優(yōu)化算法對實驗結(jié)果的影響，因此本文采用遺傳算法解決3DNoC映射問題。

基本遺傳算法的初始種群是隨機(jī)生成的，這使得初始種群存在個體分布不均勻、初始種群質(zhì)量偏低的問題。本文針對隨機(jī)生成初始種群的缺陷，提出了一種采用Prim算法思想生成初始種群的改進(jìn)遺傳算法，Prim算法思想體現(xiàn)在生成種群個體上。算法的流程如圖4所示。

圖4 基于Prim算法的改進(jìn)遺傳算法流程

3.3.2 生成初始種群

基本遺傳算法隨機(jī)產(chǎn)生初始種群，產(chǎn)生的初始種群質(zhì)量偏低，基于Prim算法的改進(jìn)遺傳算法體現(xiàn)在生成初始種群個體上，算法核心思想描述如下：假設(shè)有一個由N個IP核組成的任務(wù)圖，將這些IP核從1到N進(jìn)行編號，這N個正整數(shù)構(gòu)成了IP核集合，首先將i放入3D NoC的第一個位置(i表示正在生成的第i個個體)，然后將i從IP核集合中刪去，對此任務(wù)圖運行以i為第一個節(jié)點的Prim算法產(chǎn)生最小生成樹，按順序記錄選擇節(jié)點的數(shù)組。之后在3D NoC的其他可用位置(未被占用的位置)按數(shù)組遍歷放入未使用的IP核的編號并計算適應(yīng)值，選擇一個使得適應(yīng)值最大的IP核的編號放入3D NoC的相應(yīng)位置，然后將該IP核的編號從IP核集合中刪去，用同種方法確定其他未被占用位置放入的IP核的編號，依此類推，最終得到一個采用Prim算法得到的個體。用同樣的方法生成N個個體，然后對這N個個體進(jìn)行變異操作，使之生成一定數(shù)量的鄰居個體，最后對所有已生成的個體根據(jù)適應(yīng)值進(jìn)行排序，選擇適應(yīng)值最大的一定數(shù)量的個體作為初始種群。

本文提出基于Prim算法思想的初始化方法產(chǎn)生種群pop，主要過程如圖5所示。

圖5 初始化種群流程

步驟1 隨機(jī)生成一個數(shù)r(1≤r≤N)，然后將這個隨機(jī)數(shù)r映射個體X的第1個位置，用Prim算法產(chǎn)生以r為第1個節(jié)點的最小生成樹的數(shù)組；

步驟2 初始化可用集P={1，2，…，N}，將r從P集合中刪去；

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

步驟4 遍歷集合F，找到fit值最大的一組元素〈n,m,fit〉，把n放到個體X的第m個位置，把n從可用集P中刪去，把m從可用位置中刪去；

步驟5 重復(fù)步驟3和步驟4，直到可用集P為空，當(dāng)P為空時，表示產(chǎn)生了一個個體X，把X加入臨時種群tempPop；

步驟6 將個體X的任意兩個坐標(biāo)數(shù)字對換，即生成一個X的鄰居個體。對上述步驟生成的個體X用此方法生成20個鄰居個體，將這些鄰居個體都放入臨時種群tempPop中；

步驟7 重復(fù)上述所有步驟N次，即生成了N個由Prim算法得到的個體和這些個體的20個鄰居個體；

步驟8 從tempPop中選取適應(yīng)值最大的多個個體放入pop中作為初始種群。

下面用一個任務(wù)圖規(guī)模為7，往一個拓?fù)浼軜?gòu)為2×2×2的片上網(wǎng)絡(luò)做映射為例詳細(xì)說明映射過程。

1)給任務(wù)圖每個節(jié)點編號：0，1，2，3，4，5，6。

2)給片上網(wǎng)絡(luò)每個處理單元編號：0，1，2，3，4，5，6，7對應(yīng)(0，0，0)、(0，0，1)、(0，1，0)、(0，1，1)、(1，0，0)、(1，0，1)、(1，1，0)、(1，1，1)。

3)將任務(wù)圖節(jié)點0，放到片上網(wǎng)絡(luò)的第0號處理單元上，剩下的任務(wù)圖節(jié)點有(1，2，3，4，5，6)，剩下的片上網(wǎng)絡(luò)可用位置有(1，2，3，4，5，6，7)，利用Prim算法得出遍歷數(shù)組(0，1，2，5，3，4，6，7)。

4)把任務(wù)圖節(jié)點1，放到片上網(wǎng)絡(luò)的所有可用位置：

(0，1，，，，，，)對應(yīng)適應(yīng)值13

(0，，1，，，，，)對應(yīng)適應(yīng)值12

(0，，，1，，，，)對應(yīng)適應(yīng)值14

(0，，，，1，，，)對應(yīng)適應(yīng)值17

(0，，，，，1，，)對應(yīng)適應(yīng)值18

(0，，，，，，1，)對應(yīng)適應(yīng)值19

(0，，，，，，，1)對應(yīng)適應(yīng)值12

選取適應(yīng)值最大的一組(0，，，，，，1，)對應(yīng)適應(yīng)值19，剩下的任務(wù)圖節(jié)點有(2，3，4，5，6)，剩下的片上網(wǎng)絡(luò)可用位置有(1，2，3，4，5，7)。

5)把任務(wù)圖節(jié)點2，放到片上網(wǎng)絡(luò)的所有可用位置：

(0，2，，，，，1，)對應(yīng)適應(yīng)值16

(0，，2，，，，1，)對應(yīng)適應(yīng)值18

(0，，，2，，，1，)對應(yīng)適應(yīng)值24

(0，，，，2，，1，)對應(yīng)適應(yīng)值27

(0，，，，，2，1，)對應(yīng)適應(yīng)值21

(0，，，，，，1，2)對應(yīng)適應(yīng)值29

選取適應(yīng)值最大的一組(0，，，，，，1，2)對應(yīng)適應(yīng)值29。

6)重復(fù)上述步驟，就可以得到一個體，例如(0，3，4，6，5，7，1，2)。

7)把第一次放入片上網(wǎng)絡(luò)第0號位置的數(shù)字0換成1，重復(fù)上述步驟就可以得到(1，2,…)開頭的Prim個體。

8)重復(fù)上述步驟7次，就可以得到7個Prim算法得到的個體，分別以0,1,2,3,4,5,6開頭的Prim個體。

9)因為初始種群規(guī)模肯定比7大，所以，每個用Prim算法得到的個體都要進(jìn)行變異操作，得到更多的個體。

10)一般是這7個個體都變異M次，解空間>種群規(guī)模F，然后從解空間中選取適應(yīng)值最大的F個作為初始種群。

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

本文提出的基于遺傳算法的三維片上網(wǎng)絡(luò)映射算法，運行環(huán)境是Ubuntu13操作系統(tǒng)，編程語言采用C++語言，編程工具是codeblocks12.11，最后采用AccessNoxim進(jìn)行仿真實驗得出數(shù)據(jù)。

AccessNoxim是一個由Jheng等[22]開發(fā)的將網(wǎng)絡(luò)模型(networkmodel)、功率模型(powermodel)和熱模型(thermalmodel)相結(jié)合的3DNoC系統(tǒng)協(xié)同仿真平臺。在仿真實驗的運行過程中，流量活動被網(wǎng)絡(luò)模型聚集起來并輸入到功率模型，功率模型會產(chǎn)生整個片上網(wǎng)絡(luò)系統(tǒng)的空間和時間功耗，然后進(jìn)行能量跟蹤，根據(jù)給定的能量跟蹤所得出的溫度計算出熱模型。他們基于Intel的80-core處理器的功率模型對Noxim和Hotspot進(jìn)行功能上的整合，Hotspot的作用是提供架構(gòu)級熱模型。由于合并條件的限制，NoC仿真器需要用芯片級物理布局和功率追蹤來對其架構(gòu)級布局和功率跟蹤進(jìn)行替換。第一步加入基礎(chǔ)三維路由器模型和垂直交叉的路由器，擴(kuò)大Noxim生成三維基于用戶定義的參數(shù)尺寸的NoC架構(gòu)，然后插入一個模塊插入結(jié)構(gòu)自動轉(zhuǎn)換成物理布局，這樣才能很好地與HotSpot進(jìn)行結(jié)合。

4.1 參數(shù)設(shè)計

拓?fù)浣Y(jié)構(gòu)采用3Dmesh結(jié)構(gòu)，路由算法采用經(jīng)典算法，最后采用AccessNoxim進(jìn)行仿真實驗得出數(shù)據(jù)。仿真器參數(shù)如表1所示。

表1 仿真器參數(shù)

4.2 實驗結(jié)果對比與分析

本次實驗對2種算法進(jìn)行功耗對比，分別是基于Prim算法的改進(jìn)遺傳算法的映射算法和基于遺傳算法的映射算法。

4.2.1 兩種映射算法針對經(jīng)典APCG仿真功耗對比

本次仿真實驗使用了3種經(jīng)典任務(wù)圖(VOPD(VideoObjectPlaneDecoder)、DVOPD(DoubleVideoObjectPlaneDecoder)和MWD(Multi-WindowDisplayer))，如圖6所示。

圖6 經(jīng)典任務(wù)圖

針對不同的APCG(ApplicationCharacteristicGraph)，采用兩種算法分別求解10次。

4.2.2 改進(jìn)算法與基本遺傳算法數(shù)據(jù)對比

仿真實驗中，分別采用基于Prim算法的改進(jìn)遺傳算法與基本遺傳算法對該任務(wù)圖進(jìn)行映射操作，用得到的最優(yōu)解生成通信模式文件，仿真器AccessNoxim通過讀取通信模式文件進(jìn)行映射仿真，得到映射功耗。用實驗數(shù)據(jù)分別對3種映射算法得到的最小功耗、平均功耗和最大功耗進(jìn)行了比較，如圖7～9所示。

圖7 針對經(jīng)典APCG的平均功耗比較

圖8 針對經(jīng)典APCG的最小功耗比較

圖9 針對經(jīng)典APCG的最大功耗比較

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

分析針對DVOPD的2種映射算法仿真結(jié)果可見，采用基于Prim算法的改進(jìn)遺傳算法的功耗更低，并且降低的幅度較大；這是由于DVOPD有32個節(jié)點，任務(wù)規(guī)模較大，采用改進(jìn)策略得到的初始種群不容易陷入局部最優(yōu)。由以上實驗和分析可見，當(dāng)任務(wù)圖規(guī)模增大時，基于Prim算法的改進(jìn)遺傳算法的優(yōu)勢更為明顯。由實驗結(jié)果可知:基于Prim算法的改進(jìn)遺傳算法相對于基本遺傳算法最小功耗減少了12.46%，平均功耗減少16.13%，最大功耗減少了17.4%。

分析針對MWD的2種映射算法仿真結(jié)果可見，基于Prim算法的改進(jìn)遺傳算法相對于基本遺傳算法最小功耗減少了5.71%，平均功耗減少13.04%，最大功耗減少了12.24%。

Prim算法思想體現(xiàn)在生成種群個體上，提高其初始種群的質(zhì)量，使得IP核布局更合理，核之間的遠(yuǎn)距離通信減少而芯片功耗降低。

4.2.3 基于隨機(jī)任務(wù)圖的功耗對比

采用任務(wù)生成器TGFF生成IP核數(shù)分別為13，21，41，82和101的隨機(jī)APCG，針對不同IP核數(shù)的隨機(jī)APCG，采用兩種算法分別求解10次。采用基于Prim算法的改進(jìn)遺傳算法和基于遺傳的映射算法對比結(jié)果如圖10～12所示。

圖10 針對隨機(jī)APCG的平均功耗比較

圖11 針對隨機(jī)APCG的最小功耗比較

圖12 針對隨機(jī)APCG的最大功耗比較

4.2.4 平均功耗對比

當(dāng)IP核數(shù)較少時，基于Prim算法的改進(jìn)遺傳算法相對于基本遺傳算法的最小功耗降低幅度較小，在10%以內(nèi)。其中，82個IP核時，基于Prim算法的改進(jìn)遺傳算法比基本遺傳算法的功耗低了41.5%，這是由于IP核數(shù)目較少，容易導(dǎo)致兩種算法均陷入局部最優(yōu)，因此出現(xiàn)了在82個IP核時基于Prim算法的改進(jìn)遺傳算法的功耗降低幅度較大。從整體趨勢來看，隨著IP核數(shù)的增加，功耗降低幅度增加。

4.2.5 最小功耗比較

13個IP核時，基于Prim算法的改進(jìn)遺傳算法比基本遺傳算法的功耗低了30%；41個核時，基于Prim算法的改進(jìn)遺傳算法與基本遺傳算法的功耗基本相等；101個核時，基于Prim算法的改進(jìn)遺傳算法比基本遺傳算法的功耗低了32%。

4.2.6 最大功耗比較

13個IP核時，基于Prim算法的改進(jìn)遺傳算法與基本遺傳算法的功耗基本相等；41個核時，基于Prim算法的改進(jìn)遺傳算法比基本遺傳算法的功耗低了25%；101個核時，基于Prim算法的改進(jìn)遺傳算法比基本遺傳算法的功耗低了33%。

5 結(jié)語

本文介紹的改進(jìn)的遺傳算法在保留原始遺傳算法具有的快速隨機(jī)搜索特性基礎(chǔ)上針對其隨機(jī)生成初始種群過程中的缺陷，提出了一種采用Prim算法生成初始種群的方法，Prim算法思想體現(xiàn)在生成種群個體上，提高其初始種群的質(zhì)量，使得IP核布局更合理，核之間的遠(yuǎn)距離通信減少而降低芯片功耗。通過仿真實驗驗證，本文提出的基于Prim算法的改進(jìn)遺傳算法與基本的遺傳算法的3DNoC映射算法相比，仿真結(jié)果顯示基于Prim算法的改進(jìn)遺傳算法平均功耗更低。從總體趨勢來看隨著處理單元數(shù)量的增加與功耗降低幅度成正相關(guān)，在101個處理單元情況下，平均功耗比基本遺傳算法降低32%。

在今后的研究中發(fā)熱是需要考慮的問題，隨著研究的深入，將進(jìn)行3DNoC發(fā)熱方面的優(yōu)化問題研究；并且目前實際面向應(yīng)用的芯片往往都是針對于異構(gòu)的拓?fù)浣Y(jié)構(gòu)，但是大部分3DNoC映射算法都是為解決三維規(guī)則拓?fù)浣Y(jié)構(gòu)上的映射提出的，因此，對于異構(gòu)3D拓?fù)浣Y(jié)構(gòu)下低功耗映射算法的研究也將是國內(nèi)外研究學(xué)者在3DNoC映射問題的一個研究重點。

)

[1] 張大坤,黃翠,宋國治.三維片上網(wǎng)絡(luò)研究綜述[J].軟件學(xué)報,2016,27(1):155-187.(ZHANGDK,HUANGC,SONGGZ.Asurveyofthreedimensionalnetworkonchip[J].JournalofSoftware, 2016, 27(1): 155-187.)

[2]MORGANAA,ELMILIGIH,EL-KHARASHIMW,etal.Multi-objectiveoptimizationfornetworks-on-chiparchitecturesusinggeneticalgorithms[C]//ISCAS2010:Proceedingsof2010IEEEInternationalSymposiumonCircuitsandSystems.Piscataway,NJ:IEEE, 2010: 3725-3728.

[3] 劉炎華,劉靜,賴宗聲,等.基于遺傳蟻群算法的片上網(wǎng)絡(luò)映射研究[J].計算機(jī)工程，2010,36(22):262-264.(LIUYH,LIUJ,LAIZS,etal.Researchofnetworkonchipmappingbasedongeneticandantcolonyalgorithm[J].ComputerEngineering, 2010, 36(22): 262-264.)

[4]HUJ,MARCULESCUR.Energy-andperformance-awaremappingforregularNoCarchitectures[J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2006, 24(4): 551-562.

[5] 林樺,李險峰,佟冬,等.保證QoS的片上網(wǎng)絡(luò)低能耗映射與路由方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2008,20(4):425-431.(LINH,LIXF,TONGD,etal.Alowenergymappingandroutingapproachfornetwork-on-chipwithQoSguarantees[J].JournalofComputer-AidedDesign&ComputerGraphics, 2008, 20(4): 425-431.)

[6] 王雷,凌翔,胡劍浩.異構(gòu)多核協(xié)作系統(tǒng)的混沌離散粒子群NoC映射算法[J].計算機(jī)科學(xué),2011,38(9):298-303.(WANGL,LINGX,HUJH.NoCmappingforheterogeneousmulti-corecooperativesystembasedonchaoticdiscreteparticleswarmoptimization[J].ComputerScience, 2011, 38(9): 298-303.)

[7] 常政威,謝曉娜,桑楠,等.片上網(wǎng)絡(luò)映射問題的改進(jìn)禁忌搜索算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2008,20(2):155-160.(CHANGZW,XIEXN,SANGN,etal.Animprovedtabusearchalgorithmfornetwork-on-chipmapping[J].JournalofComputer-AidedDesignandComputerGraphics, 2008, 20(2): 155-160.)

[8] 楊盛光,李麗,高明倫,等.面向能耗和延時的NoC映射方法[J].電子學(xué)報,2008,36(5):937-942.(YANGSG,LIL,GAOML,etal.Anenergyanddelay-awaremappingmethodofNoC[J].ActaElectronicaSinica, 2008, 36(5): 937-942.)

[9] 王佳文,李麗,易偉,等.3DNoC映射問題的動態(tài)蟻群算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2011,23(9):1614-1620.(WANGJW,LIL,YIW,etal.Adynamicantcolonyoptimizationalgorithmfor3DNoCmapping[J].JournalofComputer-AidedDesign&ComputerGraphics, 2011, 23(9): 1614-1620.)

[10] 李東生,劉琪.面向通信能耗的3DNoC映射研究[J].半導(dǎo)體技術(shù),2012(7)：504-507.(LIDS,LIUQ.Researchonmapping3Dnetworkonchipforcommunicationenergy-aware[J].SemiconductorTechnology,2012(7)： 504-507.)

[11] 黃翠.基于量子粒子群的三維片上網(wǎng)絡(luò)低功耗映射算法研究[D].天津:天津工業(yè)大學(xué),2015.(HUANGC,Researchonalow-powermappingalgorithmfor3DNoCbasedondiversity-controlledquantum-behavedparticleswarmoptimization[D].Tianjin:TianjinPolytechnicUniversity, 2015.)

[12] 楊微,張振,劉怡俊.基于改進(jìn)粒子群的3D-MeshCMP片上網(wǎng)絡(luò)映射算法[J].計算機(jī)應(yīng)用研究,2013,30(5):1345-1348.(YANGW,ZHANGZ,LIUYJ.Improvedparticleswarmoptimizationalgorithmbasedmappingalgorithmfor3D-MeshCMP[J].ApplicationResearchofComputers, 2013, 30(5): 1345-1348.)

[13]LEIT,KUMARS.Atwo-stepgeneticalgorithmformappingtaskgraphstoanetworkonchiparchitecture[C]//DSD’ 03:ProceedingsoftheEuromicroSymposiumonDigitalSystemsDesign.Washington,DC:IEEEComputerSociety, 2003: 180-187.

[14]ASCIAG,CATANIAV,PALESIM.Multi-objectivemappingformesh-basedNoCarchitectures[C]//CODES+ISSS’ 04:Proceedingsofthe2ndIEEE/ACM/IFIPInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis.NewYork:ACM, 2004: 182-187.

[15] 張濤濤.熱/流均衡的混合型3DNoC拓?fù)浣Y(jié)構(gòu)設(shè)計與映射算法研究[D].南京:南京航空航天大學(xué),2014.(ZHANGTT.Explorationoftopologyandmappingalgorithmforthermaltrafficbalanced3DNoCbushybridarchitecture[D].Nanjing:NanjingUniversityofAeronauticsandAstronautics, 2014.)

[16]ADDO-QUAYEC.Thermal-awaremappingandplacementfor3-DNoCdesigns[C]//Proceedings2005IEEEInternationalSOCConference.Piscataway,NJ:IEEE, 2005: 25-28.

[17]YINGH,HEIDK,HOLLSTEINT,etal.Ageneticalgorithmbasedoptimizationmethodforlowverticallinkdensity3-dimensionalnetworks-on-chipmanycoresystems[C]//NORCHIP2012:Proceedingsofthe30thNorchipConference.Piscataway,NJ:IEEE, 2012: 1-4.

[18]WANGJ,LIL,PANH,etal.Latency-awaremappingfor3DNoCusingrank-basedmulti-objectivegeneticalgorithm[C]//ASICON2011:Proceedingsofthe2011IEEE9thInternationalConferenceonASIC.Piscataway,NJ:IEEE, 2011: 413-416.

[19] 林華洲,張大坤,黃翠.基于Prim算法的改進(jìn)遺傳算法的3DNoC低功耗映射研究[J].計算機(jī)工程與應(yīng)用,2016,52(1):76-80.(LINHZ,ZHANGDK,HUANGC.Researchonlow-powermappingforthree-dimensionalnetwork-on-chipbasedonimprovedgeneticalgorithm[J].ComputerEngineeringandApplications, 2016, 52(1): 76-80.)

[20]HOLLANDJH.AdaptationinNaturalandArtificialSystems:AnIntroductoryAnalysiswithApplicationstoBiology,Control,andArtificialIntelligence[M].Cambridge:TheMITPress, 1992.

[21] 馬永杰,云文霞.遺傳算法研究進(jìn)展[J].計算機(jī)應(yīng)用研究,2012,29(4):1201-1206.(MAYJ,YUNWX.Researchprogressofgeneticalgorithm[J].ApplicationResearchofComputers, 2012, 29(4): 1201-1206.)

[22]JHENGKY,CHAOCH,WANGHY,etal.Traffic-thermalmutual-couplingco-simulationplatformforthree-dimensionalnetwork-on-chip[C]//VLSI-DAT2010:Proceedingsofthe2010InternationalSymposiumonVLSIDesignAutomationandTest.Piscataway,NJ:IEEE, 2010: 135-138.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61272006),NationalUndergraduateTrainingProgramforInnovationandEntrepreneurship(201510058050).

SONG Guozhi, born in 1977, Ph.D., associate professor.His research interests include 3D network-on-chip, heterogeneous wireless network integration.

WANG Cheng, born in 1995.His research interests include 3D network-on-chip.

TU Yao, born in 1992, M.S.candidate.His research interests include 3D network-on-chip floorplanning.

ZHANG Dakun, born in 1960, Ph.D., professor.Her research interests include 3D network-on-chip, virtual reality, combinational algorithm.

Low power mapping based on improved genetic algorithm with Prim initial population selection for 3D network-on-chip

SONG Guozhi1*, WANG Cheng1,2, TU Yao1, ZHANG Dakun1

(1.SchoolofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387,China;2.SchoolofInformationScienceandEngineering,YunnanUniversity,KunmingYunnan650091,China)

To solve the problem of properly mapping the computational task onto a three-dimensional Network-on-Chip (NoC), an improved algorithm based on Genetic Algorithm (GA) was proposed.GA has the fast random searching ability and Prim algorithm can get the minimal spanning tree of a weighted connected graph.By combining the two algorithms’ advantages, the improved algorithm could properly assign computational tasks onto each network node, achieving a high efficiency on solving network power consumption and heat problems.The simulation experiments were carried out to compare the proposed improved GA based on Prim algorithm with GA based 3D NoC mapping algorithm.The simulation results indicate that the average power consumption of the improved GA based on Prim algorithm is lower: from the overall trend, the reduction on power consumption is positive correlated to the increase of the number of processing units, and when there are 101 processing units, the average power consumption is 32% lower than that of the traditional GA.

three-dimensional Network-on-Chip (3D NoC); low power consumption; mapping algorithm; Genetic Algorithm (GA); Prim algorithm

2016-07-30;

2016-08-07。

國家自然科學(xué)基金資助項目(61272006)；國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(201510058050)。

宋國治(1977—)，男，黑龍江哈爾濱人，副教授，博士，CCF會員，主要研究方向：三維片上網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)、異構(gòu)網(wǎng)絡(luò)融合；王鋮(1995—)，男，安徽阜陽人，主要研究方向：三維片上網(wǎng)絡(luò)； 涂遙(1992—)，男，安徽淮南人，碩士研究生，主要研究方向：三維片上網(wǎng)絡(luò)布局優(yōu)化； 張大坤(1960—)，女，遼寧阜新人，教授，博士，主要研究方向：三維片上網(wǎng)絡(luò)、虛擬現(xiàn)實、組合算法。

1001-9081(2017)01-0090-07

10.11772/j.issn.1001-9081.2017.01.0090

TP393.01

A