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

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

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

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

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

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

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

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

三維片上網絡；低功耗；映射算法；遺傳算法；Prim算法

0 引言

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

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

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

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

1.1 基本概念

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

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

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

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

1.2 能耗模型

本文的研究目標是在NoC體系結構的網絡資源中最大限度地減少所消耗的能量。網絡結構中的功耗與網絡中的通信量有直接關系。為了估計NoC體系結構的功耗，應該使用一個基于總傳輸量的功耗模型，其定義如下：

ETbit=ESbit+EBbit+EWbit+ELbit

(1)

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

ETbit=ESbit+EBbit+EWbit

(2)

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

ETbit=ESbit+ELbit

(3)

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

(4)

(ni, j+1)代表數(shù)據(jù)在傳送過程中數(shù)據(jù)經過的路由器的數(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 種群個體向量表示

經典應用特征圖PIP(Picture-In-Picture)包含8個節(jié)點，如圖1所示，圖中的IP核用數(shù)字1到8表示，將PIP中的節(jié)點映射到2×2×2的3D Mesh結構上。假設個體Y=(y0，y1，y2，…，yM-1)，M為任務圖的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)上，映射結果如圖3所示。

圖1 任務通信圖PIP

圖2 NoC拓撲結構

圖3 映射結果

2 映射算法基礎

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

2.1 基于禁忌搜索算法

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

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

2.2 基于蟻群算法

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

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

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

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

2.3 基于粒子群算法

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

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

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

2.4 基于遺傳算法

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

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

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

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

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

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

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

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

3 遺傳算法及改進

3.1 基本遺傳算法

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

3.2 Prim算法

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

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

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

3.3 改進遺傳算法

3.3.1 改進遺傳算法的提出

類似于其他尋找最優(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)化算法對實驗結果的影響，因此本文采用遺傳算法解決3DNoC映射問題。

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

圖4 基于Prim算法的改進遺傳算法流程

3.3.2 生成初始種群

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

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

圖5 初始化種群流程

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

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

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

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

步驟5 重復步驟3和步驟4，直到可用集P為空，當P為空時，表示產生了一個個體X，把X加入臨時種群tempPop；

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

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

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

下面用一個任務圖規(guī)模為7，往一個拓撲架構為2×2×2的片上網絡做映射為例詳細說明映射過程。

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

2)給片上網絡每個處理單元編號：0，1，2，3，4，5，6，7對應(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)將任務圖節(jié)點0，放到片上網絡的第0號處理單元上，剩下的任務圖節(jié)點有(1，2，3，4，5，6)，剩下的片上網絡可用位置有(1，2，3，4，5，6，7)，利用Prim算法得出遍歷數(shù)組(0，1，2，5，3，4，6，7)。

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

(0，1，，，，，，)對應適應值13

(0，，1，，，，，)對應適應值12

(0，，，1，，，，)對應適應值14

(0，，，，1，，，)對應適應值17

(0，，，，，1，，)對應適應值18

(0，，，，，，1，)對應適應值19

(0，，，，，，，1)對應適應值12

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

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

(0，2，，，，，1，)對應適應值16

(0，，2，，，，1，)對應適應值18

(0，，，2，，，1，)對應適應值24

(0，，，，2，，1，)對應適應值27

(0，，，，，2，1，)對應適應值21

(0，，，，，，1，2)對應適應值29

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

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

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

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

9)因為初始種群規(guī)?？隙ū?大，所以，每個用Prim算法得到的個體都要進行變異操作，得到更多的個體。

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

4 仿真實驗與結果分析

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

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

4.1 參數(shù)設計

拓撲結構采用3Dmesh結構，路由算法采用經典算法，最后采用AccessNoxim進行仿真實驗得出數(shù)據(jù)。仿真器參數(shù)如表1所示。

表1 仿真器參數(shù)

4.2 實驗結果對比與分析

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

4.2.1 兩種映射算法針對經典APCG仿真功耗對比

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

圖6 經典任務圖

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

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

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

圖7 針對經典APCG的平均功耗比較

圖8 針對經典APCG的最小功耗比較

圖9 針對經典APCG的最大功耗比較

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

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

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

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

4.2.3 基于隨機任務圖的功耗對比

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

圖10 針對隨機APCG的平均功耗比較

圖11 針對隨機APCG的最小功耗比較

圖12 針對隨機APCG的最大功耗比較

4.2.4 平均功耗對比

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

4.2.5 最小功耗比較

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

4.2.6 最大功耗比較

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

5 結語

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

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

)

[1] 張大坤,黃翠,宋國治.三維片上網絡研究綜述[J].軟件學報,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] 劉炎華,劉靜,賴宗聲,等.基于遺傳蟻群算法的片上網絡映射研究[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的片上網絡低能耗映射與路由方法[J].計算機輔助設計與圖形學學報,2008,20(4):425-431.(LINH,LIXF,TONGD,etal.Alowenergymappingandroutingapproachfornetwork-on-chipwithQoSguarantees[J].JournalofComputer-AidedDesign&ComputerGraphics, 2008, 20(4): 425-431.)

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

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

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

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

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

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

[12] 楊微,張振,劉怡俊.基于改進粒子群的3D-MeshCMP片上網絡映射算法[J].計算機應用研究,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拓撲結構設計與映射算法研究[D].南京:南京航空航天大學,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算法的改進遺傳算法的3DNoC低功耗映射研究[J].計算機工程與應用,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].計算機應用研究,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。

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

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

1001-9081(2017)01-0090-07

10.11772/j.issn.1001-9081.2017.01.0090

TP393.01

A