改進(jìn)的三級(jí)遺傳算法定制片上網(wǎng)絡(luò)拓?fù)浞抡?/h1>
2018-05-21 07:40:07賴國(guó)明
實(shí)驗(yàn)室研究與探索 2018年3期
熊 昕， 賴國(guó)明
(1.廣州番禺職業(yè)技術(shù)學(xué)院 現(xiàn)代教育技術(shù)與信息中心，廣州 511483; 2.惠州學(xué)院 信息科學(xué)技術(shù)學(xué)院，廣東 惠州 516007)
0 引 言
片上系統(tǒng)SoC是指在單個(gè)芯片上集成了專用處理器、通用處理器、DSP、共享內(nèi)存塊、專用內(nèi)存塊、I/O部件等多個(gè)IP核的復(fù)雜系統(tǒng)，具有更強(qiáng)大的功能、更低的成本、更小的產(chǎn)品體積、更好的可靠性和更靈活的配置，從而成為新一代應(yīng)用電子技術(shù)的核心。片上系統(tǒng)SoC為集成電路技術(shù)的應(yīng)用和集成電路產(chǎn)業(yè)發(fā)展提供了廣闊市場(chǎng)和全新的發(fā)展機(jī)遇，是當(dāng)今大規(guī)模集成電路(VLSI)技術(shù)的主要發(fā)展趨勢(shì)和發(fā)展主流[1]。
高端的SoC片內(nèi)互連的處理核數(shù)量很多，例如Intel實(shí)驗(yàn)室已經(jīng)有80核心的SoC,片內(nèi)的通信就會(huì)成為SoC的主要性能瓶頸，如何解決其高通信需求是當(dāng)前高端SoC面臨的迫切問題，片上網(wǎng)絡(luò)NoC為解決SoC的通信問題提供了新的有效途徑。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中處理核的相對(duì)位置以及其連接方式極大地影響著片上網(wǎng)絡(luò)的時(shí)延、功耗等性能指標(biāo)[2]。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是網(wǎng)絡(luò)路由算法設(shè)計(jì)、緩沖區(qū)分配、容錯(cuò)處理等的其他后繼相關(guān)研究的前提和基礎(chǔ)。由于SoC主要是面向特定應(yīng)用或者少數(shù)應(yīng)用類的，一旦應(yīng)用通信特征圖確定，其所需要的節(jié)點(diǎn)間的通信帶寬和時(shí)延限制就基本確定，因此，片上網(wǎng)絡(luò)的設(shè)計(jì)必須利用特定應(yīng)用的通信特征來定制片上網(wǎng)絡(luò)的拓?fù)?才能設(shè)計(jì)出符合特定應(yīng)用通信特征需求的優(yōu)化片上網(wǎng)絡(luò)[3]。近年來，特定應(yīng)用的拓?fù)鋬?yōu)化得到了許多研究人員的深入研究，Srinivasan等[4]提出了一種基于整數(shù)線性規(guī)劃的拓?fù)渚C合方法，Murali[5]介紹一種定制可靠和高效的片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方法。為了更好地利用特定應(yīng)用的通信特征信息來定制和優(yōu)化特定應(yīng)用片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，必須根據(jù)應(yīng)用的通信特征來優(yōu)化其拓?fù)洹eary[6]等提出了基于3級(jí)遺傳算法的片上網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計(jì)。本文主要針對(duì)其進(jìn)行改進(jìn)，提出了一種改進(jìn)的3級(jí)遺傳算法來定制特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，相對(duì)于Leary等的算法，本算法取得了較好的優(yōu)化效果和運(yùn)行效率。
1 Leary的3級(jí)遺傳算法及不足
2009年，Leary等提出了一個(gè)3級(jí)的遺傳算法來解特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題，該算法以應(yīng)用通信特征圖ACCG、互連部件特性參數(shù)和系統(tǒng)平面布局為輸入，算法首先初始化種群個(gè)體，計(jì)算個(gè)體的適應(yīng)度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值和相應(yīng)的固定路由，該遺傳算法采用如圖1所示的3層結(jié)構(gòu)。這3個(gè)層次分別是路由器的選擇層、節(jié)點(diǎn)與路由端口的映射層和通信交通層。其中第1級(jí)別的路由器選擇層表示從所有可能的路由器集合中選取出一定數(shù)量的可用路由器,第2級(jí)別表示應(yīng)用通信特征圖中的結(jié)點(diǎn)到選中的路由器端口的映射，第3層表示應(yīng)用通信交通從源點(diǎn)到目的點(diǎn)經(jīng)過中間路由器端口的可能通信路由路徑。這種方法存在著明顯的不足：
(1) 在第2級(jí)的節(jié)點(diǎn)與路由器端口的映射層，對(duì)所選的路由器的所有端口進(jìn)行統(tǒng)一編號(hào)，然后把節(jié)點(diǎn)與端口之間進(jìn)行映射來實(shí)現(xiàn)節(jié)點(diǎn)與路由器連接。由于路由器有多個(gè)端口，同一個(gè)節(jié)點(diǎn)n1與路由器r1的不同端口進(jìn)行映射就是不同的種群個(gè)體。例如，假設(shè)路由器r1有5個(gè)端口，節(jié)點(diǎn)n1(圖中以帶圓圈的數(shù)字1表示,以下同)與這5端口的映射是5個(gè)不同的個(gè)體。然而，由于路由器的尺寸遠(yuǎn)比節(jié)點(diǎn)的尺寸小[24]，同一節(jié)點(diǎn)映射在同一路由器的不同端口其連接線的長(zhǎng)度應(yīng)該是一樣的，所以，可以把它們看作是同一個(gè)映射，即節(jié)點(diǎn)與路由器的映射，這樣，節(jié)點(diǎn)n1與路由器r1的映射只需1個(gè)個(gè)體來表示。
圖1 Leary的3級(jí)層次表示圖[6]
由于遺傳算法所有可能的不同個(gè)體集合構(gòu)成了算法的搜索空間，不同個(gè)體的數(shù)量越多，算法的搜索空間就越大，從而算法的運(yùn)行時(shí)間就越長(zhǎng)。此外，一個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定于3個(gè)方面：路由器的選擇、節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接，Leary的方法不僅增加了遺傳算法的搜索空間，第3級(jí)采用通信交通層也與拓?fù)涞?個(gè)方面沒有直觀的聯(lián)系。受到此啟發(fā)，本文提出了一種新的3級(jí)遺傳算法，它的3個(gè)層次分別為：路由器選擇層、節(jié)點(diǎn)與路由器映射層和路由器與路由器映射層。這3個(gè)層次不僅直觀反映網(wǎng)絡(luò)拓?fù)涞?個(gè)方面，同時(shí)也可以有效地減小GA搜索空間，加快仿真速度[11]。
2 改進(jìn)3級(jí)GA的拓?fù)浣Y(jié)構(gòu)優(yōu)化技術(shù)
網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題是一個(gè)典型的多目標(biāo)優(yōu)化問題，它是斯坦納樹(Steiner Tree)的變形，是一個(gè)NP難問題[3]。用GA解NoC拓?fù)涠ㄖ茊栴}的流程如圖2所示，算法以應(yīng)用通信特征圖ACCG、互連部件特性參數(shù)和系統(tǒng)平面布局為輸入。算法首先初始化種群個(gè)體，計(jì)算個(gè)體的適應(yīng)度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值。為了有效地應(yīng)用GA技術(shù)，必須定義問題解的染色體有效表示方法，以及選擇、交叉及變異的基因操作[12]。
圖2 GA的流程圖
2.1 解染色體串的數(shù)據(jù)結(jié)構(gòu)
GA技術(shù)采用3級(jí)層次化的數(shù)據(jù)結(jié)構(gòu)如,圖3所示。
第1級(jí)是路由器選擇級(jí)別，用來表示在最大數(shù)量的路由器中哪些路由器被選擇來構(gòu)成NoC的拓?fù)浣Y(jié)構(gòu)。第2級(jí)的染色體串用來表示哪個(gè)節(jié)點(diǎn)與哪個(gè)路由器相連接，是表示節(jié)點(diǎn)與路由器的映射級(jí)別。第三級(jí)是路由器與路由器的映射級(jí)別，用來表示路由器間的相互連接方式，而不同于Leary方法的通信交通量的由路由端口組成的通信路徑。
(1) 路由器選擇級(jí)(第1級(jí))數(shù)據(jù)結(jié)構(gòu)。改進(jìn)的GA技術(shù)[13]把路由器選擇級(jí)別的數(shù)據(jù)結(jié)構(gòu)表示成一組常量個(gè)數(shù)的一維二進(jìn)制數(shù)組arstr[maxrouter]，其變量maxrouter是系統(tǒng)中所有可能的最大路由器個(gè)數(shù)，由于假定路由器分配在IP核的4個(gè)角落，所以總的最大可用路由器數(shù)量是IP核的4倍。arstr數(shù)組元素是隨機(jī)產(chǎn)生的0或者1，第i個(gè)元素是1或者0分別表示第i
圖3 層次化個(gè)體表示
個(gè)路由器被選擇或者沒有被選擇來構(gòu)成網(wǎng)絡(luò)拓?fù)洌琲∈[0..maxrouter]內(nèi)的整數(shù)。圖3所示的第1層個(gè)體的數(shù)據(jù)結(jié)構(gòu)如圖4所示，圖中arstr[i]=1表示第i個(gè)路由器被選擇到網(wǎng)絡(luò)體系結(jié)構(gòu)中，否則arstr[i]=0表示未選中。本文中的GA技術(shù)保持常數(shù)J個(gè)arstr個(gè)體。所有選擇出來的路由器從0開始統(tǒng)一進(jìn)行編號(hào)，為了建立所選擇的路由器與原來總的路由器之間的關(guān)系，定義一個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)routid的一維數(shù)組來存儲(chǔ)所選路由器在原來總路由器中的編號(hào)。
(2) 節(jié)點(diǎn)/路由器映射級(jí)(第2級(jí))數(shù)據(jù)結(jié)構(gòu)。第2級(jí)個(gè)體用染色體nrstr表示節(jié)點(diǎn)/路由器映射，整數(shù)數(shù)組nrstr[nodenum]用來表示節(jié)點(diǎn)/路由器的映射，其中nodenum代表ACCG圖中IP核的個(gè)數(shù)。在圖3中，節(jié)點(diǎn)2，3分別映射到路由器1。由于路由器有多個(gè)端口，不同的節(jié)點(diǎn)可以映射到同一個(gè)路由器，所以，數(shù)組nrstr中的元素可以重復(fù)，但節(jié)點(diǎn)/路由器的映射必須滿足一定的合法性條件[14]，這些合法性條件將在下一小節(jié)中介紹。在這一節(jié)中，為了記錄每個(gè)路由器與幾個(gè)節(jié)點(diǎn)相連接。
(3) 路由器/路由器映射級(jí)別(第3級(jí))數(shù)據(jù)結(jié)構(gòu)。在第3級(jí)別上，GA技術(shù)與Leary的第3級(jí)使用不同的數(shù)據(jù)結(jié)構(gòu)，使用路由器/路由器的映射來決定路由器之間的連接。這里，使用二維的二進(jìn)制矩陣rrstr來表示路由器之間的連接，矩陣rrstr是一個(gè)對(duì)稱矩陣，上三角矩陣元素rrstr[i][j](i
圖4 個(gè)體染色體的數(shù)據(jù)結(jié)構(gòu)
2.2 解表示法的合法性條件
NoC拓?fù)浣Y(jié)構(gòu)要求滿足一些充分必要的合法性條件，下面分別介紹3個(gè)級(jí)別解表示法的合法性條件。
(1) 路由器選擇的合法性條件。第1級(jí)的合法性條件是：為了保證網(wǎng)絡(luò)的連通性，避免路由器的選擇不當(dāng)導(dǎo)致成為孤島，必須滿足:
rp≥n+2(r-1)
(1)
式中：n為全連通的網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)；r為所選的路由器數(shù)；p為每個(gè)路由器有端口數(shù)。
即：由r個(gè)路由器構(gòu)成一個(gè)全連通的網(wǎng)絡(luò)至少需要用去2×(r-1)個(gè)端口。
(2) 節(jié)點(diǎn)/路由器映射級(jí)的合法性條件。在第2級(jí)別，需滿足下列合法性條件：節(jié)點(diǎn)與路由器的映射關(guān)系是一對(duì)一的關(guān)系，即一個(gè)節(jié)點(diǎn)都必須映射到一個(gè)路由器，且只能映射給NoC結(jié)構(gòu)中的一個(gè)路由器；而路由器與節(jié)點(diǎn)的關(guān)系是一對(duì)多的關(guān)系，即一個(gè)路由器可以連接到多個(gè)節(jié)點(diǎn)。
如果所選擇的路由器數(shù)量大于1個(gè)，每個(gè)路由器至少有一個(gè)端口空出來，用于把該路由器與其它路由器相連，以保證網(wǎng)絡(luò)的連通性。
(3) 路由器/路由器映射級(jí)的合法性條件。本級(jí)需滿足下列合法性條件：路由器至少必須與另一個(gè)路由器相連以保證網(wǎng)絡(luò)連通性。
由于受限于路由器的最大端口數(shù)，每個(gè)路由器的最大端口數(shù)需大于路由器的連接總數(shù)。一個(gè)路由器的總連接數(shù)包含節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接。
為確保單時(shí)鐘周期信號(hào)的傳播，兩個(gè)相鄰接路由器之間的曼哈頓距離需在所允許的通信距離之內(nèi)。
路由器端口的最大帶寬限制必須不能違規(guī)。
2.3 初始種群的產(chǎn)生和適合度函數(shù)
(1) 初始種群的產(chǎn)生。初始時(shí)，改進(jìn)的GA技術(shù)產(chǎn)生J個(gè)路由器選擇數(shù)組arstr，K個(gè)節(jié)點(diǎn)/路由器映射數(shù)組nrstr和L個(gè)路由器/路由器映射二維二進(jìn)制數(shù)組rrstr初始種群。對(duì)于J個(gè)路由器選擇級(jí)的個(gè)體，每個(gè)arstr數(shù)組都是通過隨機(jī)地賦值“0”或者“1”給每個(gè)數(shù)組元素來產(chǎn)生的。如果所產(chǎn)生的染色體數(shù)組不符合第一級(jí)的合法性，則通過隨機(jī)地把某個(gè)值為“0”的數(shù)組元素改變?yōu)?，直到滿足合法性條件。節(jié)點(diǎn)j路由器的染色體nrstr是選擇一個(gè)節(jié)點(diǎn)i，并隨機(jī)地把它分配給一個(gè)選擇出來的路由器，把該路由器的編號(hào)存儲(chǔ)在nrstr[i]中。同樣節(jié)點(diǎn)/路由器映射必須滿足上述的第2級(jí)合法性條件。最后，路由器/路由器映射是一個(gè)二維對(duì)稱的二進(jìn)制數(shù)組rrstr，這一級(jí)的初始個(gè)體是通過隨機(jī)地賦值“0”或者“1”給矩陣的上三角元素，隨后下三角元素賦值為對(duì)應(yīng)上三角元素的值來產(chǎn)生的。如果矩陣元素rrstr[i][j]=1，則意味著路由器i與路由器j間有一條物理鏈路直接相連，反之，rrstr[i][j]=0則沒有直接鏈路存在。矩陣的主對(duì)角元素rrstr[i][i]都被賦值為“0”，表示一個(gè)路由器不能通過一條線路連接到自身。矩陣的階數(shù)等于對(duì)應(yīng)的arstr中路由器個(gè)數(shù)。隨機(jī)產(chǎn)生的連接矩陣不一定符合第3級(jí)的合法性條件，如果違背合法性條件，則GA調(diào)用一個(gè)叫adjustment的過程來調(diào)整矩陣元素以滿足第3級(jí)的合法性條件。
(2) 適應(yīng)度函數(shù)。GA的選擇操作是根據(jù)適應(yīng)度函數(shù)值來選擇最適應(yīng)的個(gè)體來產(chǎn)生下一代種群。GA優(yōu)化目標(biāo)是最小化功耗和路由器資源，適應(yīng)度函數(shù)定義如下：
(2)
式中:p是個(gè)體所表示的拓?fù)鋵?duì)所有通信交通所消耗的總能量;r是拓?fù)渲惺褂玫穆酚善鲾?shù)量;α和β則分別是p和r的權(quán)重。一旦個(gè)體所對(duì)應(yīng)的拓?fù)浣Y(jié)構(gòu)臨時(shí)確定之后，也就是一旦路由器已經(jīng)選擇、節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接已經(jīng)完成，在滿足最大帶寬限制的前提下，采用Dijkstra最短路徑算法，可以對(duì)所有通信交通進(jìn)行路由，因此，每個(gè)通信交通的能量消耗能夠被計(jì)算出來。個(gè)體的能耗是ACCG中所有通信交通所消耗能量之和。
對(duì)于一個(gè)通信交通e從路由器r1流到r2的功耗可以下式計(jì)算：
(3)
式中,dist(r1，r2)是路由器r1與r2之間的曼哈頓距離。對(duì)于某個(gè)通信交通，如果兩個(gè)節(jié)點(diǎn)之間沒有路徑可達(dá)，則假定其功耗為無窮大，因此該個(gè)體的適應(yīng)度最小，在選擇過程中，該個(gè)體就會(huì)被淘汰。
2.4 3個(gè)級(jí)別的遺傳基因操作
(1) 選擇操作。根據(jù)個(gè)體的適應(yīng)度值從當(dāng)前種群和新產(chǎn)生的個(gè)體中選擇指定數(shù)量最適應(yīng)的個(gè)體來產(chǎn)生下一代種群，在下一代個(gè)體的產(chǎn)生中自動(dòng)完成。
(2) 交叉操作。交叉操作是隨機(jī)地從當(dāng)前種群中選擇兩個(gè)個(gè)體(即雙親)進(jìn)行交配來產(chǎn)生下一代個(gè)體。在我們的GA技術(shù)中，我們使用均勻完全交叉操作。
(3) 變異操作。變異操作隨機(jī)地對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。
3 實(shí)驗(yàn)結(jié)果及討論
3.1 實(shí)驗(yàn)設(shè)置
本文以MPEG4[7]，MWD[7]，VOPD[7]，DSP[8]4種多媒體應(yīng)用標(biāo)準(zhǔn)測(cè)試程序來定制不規(guī)則拓?fù)浣Y(jié)構(gòu)，并給出最小的能耗值。所有的處理核的尺寸都是隨機(jī)生成的，面積大約為1.5 mm×1.5 mm=2.25 mm2，路由器的輸入和輸出端口的功耗估計(jì)分別為328和65.5 nW/(Mb·s-1)，而鏈路的單位功耗為79.6 (nW·Mb-1)/(s·mm-1)。MPEG4和DSP的應(yīng)用通信特征圖ACCG如圖5所示，VOPD、MWD的應(yīng)用通信特征圖如圖6所示。
(a)MPEG4 (b)DSP
圖5 MPEG4[7]，DSP[8]應(yīng)用通信特征圖ACCG
3.2 實(shí)驗(yàn)結(jié)果分析
針對(duì)上面的標(biāo)準(zhǔn)測(cè)試程序，在Window7平臺(tái)上，用Visusal C++6.0進(jìn)行編程實(shí)現(xiàn)，其中遺傳算法的各級(jí)交叉概率為90%，變異概率為0.5%，各個(gè)級(jí)別的個(gè)體數(shù)量均為1 000個(gè)，實(shí)驗(yàn)的結(jié)果如表1所示，可見，本文改進(jìn)的遺傳算法定制NoC拓?fù)浣Y(jié)構(gòu)[9]時(shí)，功耗有一定的改進(jìn)，雖然相對(duì)Leary方法改進(jìn)不大，平均能耗改進(jìn)只有3.74%，其主要原因是因?yàn)長(zhǎng)eary方法已經(jīng)是較好的優(yōu)化結(jié)果。但是，在仿真時(shí)間由309.125 s減少至254.2 s，卻有較大的減少，平均提高17.4%，其原因是遺傳算法的不同個(gè)體的數(shù)量越多，算法的搜索空間就越大，從而算法的運(yùn)行時(shí)間就越長(zhǎng)。本文的改進(jìn)方面在遺傳算法的搜索空間上有較大的改進(jìn)[10]，相比Leary方法在搜索空間上有較大的減少，從而減少搜索時(shí)間。
(a)VOPD (b)MWD
圖6 VOPD[7]，MWD[7]應(yīng)用通信特征圖ACCG
表1 實(shí)驗(yàn)結(jié)果
4 結(jié) 語
片上網(wǎng)絡(luò)(NoC)是將來眾核片上系統(tǒng)通信問題的有效解決方案，而特定應(yīng)用拓?fù)鋬?yōu)化能夠充分利用應(yīng)用的通信特征來定制優(yōu)化片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。有約束的特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)鋬?yōu)化定制是一種NP完全的問題，目前沒有有效的優(yōu)化方法，本文針對(duì)Leary[6]等提出了基于3級(jí)遺傳算法的片上網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計(jì)中不足進(jìn)行改進(jìn)，提出了一種改進(jìn)的3級(jí)遺傳算法來優(yōu)化定制特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)洌訫PEG4[7]等4種標(biāo)準(zhǔn)多媒體應(yīng)用通信特征來測(cè)試，實(shí)驗(yàn)結(jié)果表明本文的方法在仿真時(shí)間上有較大的改進(jìn)，平均提高17.4%。
參考文獻(xiàn)(References)：
[1] 鄭靈翔. 嵌入式系統(tǒng)設(shè)計(jì)與應(yīng)用開發(fā)[M]. 北京:北京航空航天大學(xué)出版社，2006.
[2] Hemani A, Jantsch A, Kumar S,etal. Network on a Chip: An architecture for billion transistor era [C]//Proceeding of IEEE NorChip Conference, 2000:166-173.
[3] Garey M R, Johnson D S. Computers and intractability: A guide to the theory of NP-completeness [M]. Freeman, 1979: 121-130.
[4] Srinivasan K, Chatha K S, Konjevod G. Linear-programming-based techniques for synthesis of Network-on-Chip architectures [J]. IEEE Transaction on Very Large Scale Integration (VLSI), 2006, 14(4): 407-420.
[5] Murali S. Designing reliable and efficient networks on chips [J]. Lecture Notes in Electrical Engineering, 2009, 34:57-75.
[6] Leary G I, Srinivasan K, Mehta K,etal. Design of Network-on-Chip architectures with a Genetic Algorithm-based technique [J], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2009, 17(5): 674-687.
[7] Jalabert A, Murali S, Benini L,etal. XpipesCompiler: A tool for instantiating application specific Networks on Chip [C]//Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2004(2):884-889.
[8] Murali S, Micheli G D. SUNMAP: A tool for automatic topology selection and generation for NoCs [C]//Proceedings of 41st Design Automation Conference, 2004:914-919.
[9] Zhang Ying, Wu Ning, Ge Fen, Sectional NoC Mapping Scheme Optimized for Testing Time[J]. Transactions on Engineering TechnologiesWorld Congress on Engineering and Computer Science 2014,2015:301-314.
[10] Ji Wu, Dezun Dong, Xiangke Liao,etal. Energy-efficient NoC with multi-granularity power optimization[J]. The Journal of Supercomputing, 2015, 73(4):1654-1671.
[11] 鄧 可,賀向前.基于遺傳算法的自適應(yīng)控制系統(tǒng)[J]．實(shí)驗(yàn)室研究與探索，2007，26( 10) : 41-43，72．
[12] 趙文龍,黃 尋.基于遺傳計(jì)算模糊PID的數(shù)字隨動(dòng)系統(tǒng)設(shè)計(jì)[J]．實(shí)驗(yàn)室研究與探索，2017，36( 3) :143-147．
[13] 馬丹妮,李傳江.基于遺傳算法的七自由度機(jī)器人軌跡[J]．實(shí)驗(yàn)室研究與探索，2016，35( 9) :33-37．
[14] Elmiligi H,Gebali F,El-Kharashi M W.Power-awaremapping for 3D-NoC designs using genetic algorithms[J].Procedia Computer Science，2014，34：538-543.
[15] Wang J，Li L，Wang Z，etal.Energy-efficient mapping for 3D NoC using logistic function based adaptive geneticalgorithms[J].Chinese Journal of Electronics，2014，23(2)：254-262.
熊 昕， 賴國(guó)明
(1.廣州番禺職業(yè)技術(shù)學(xué)院 現(xiàn)代教育技術(shù)與信息中心，廣州 511483; 2.惠州學(xué)院 信息科學(xué)技術(shù)學(xué)院，廣東 惠州 516007)
0 引 言
片上系統(tǒng)SoC是指在單個(gè)芯片上集成了專用處理器、通用處理器、DSP、共享內(nèi)存塊、專用內(nèi)存塊、I/O部件等多個(gè)IP核的復(fù)雜系統(tǒng)，具有更強(qiáng)大的功能、更低的成本、更小的產(chǎn)品體積、更好的可靠性和更靈活的配置，從而成為新一代應(yīng)用電子技術(shù)的核心。片上系統(tǒng)SoC為集成電路技術(shù)的應(yīng)用和集成電路產(chǎn)業(yè)發(fā)展提供了廣闊市場(chǎng)和全新的發(fā)展機(jī)遇，是當(dāng)今大規(guī)模集成電路(VLSI)技術(shù)的主要發(fā)展趨勢(shì)和發(fā)展主流[1]。
高端的SoC片內(nèi)互連的處理核數(shù)量很多，例如Intel實(shí)驗(yàn)室已經(jīng)有80核心的SoC,片內(nèi)的通信就會(huì)成為SoC的主要性能瓶頸，如何解決其高通信需求是當(dāng)前高端SoC面臨的迫切問題，片上網(wǎng)絡(luò)NoC為解決SoC的通信問題提供了新的有效途徑。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中處理核的相對(duì)位置以及其連接方式極大地影響著片上網(wǎng)絡(luò)的時(shí)延、功耗等性能指標(biāo)[2]。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是網(wǎng)絡(luò)路由算法設(shè)計(jì)、緩沖區(qū)分配、容錯(cuò)處理等的其他后繼相關(guān)研究的前提和基礎(chǔ)。由于SoC主要是面向特定應(yīng)用或者少數(shù)應(yīng)用類的，一旦應(yīng)用通信特征圖確定，其所需要的節(jié)點(diǎn)間的通信帶寬和時(shí)延限制就基本確定，因此，片上網(wǎng)絡(luò)的設(shè)計(jì)必須利用特定應(yīng)用的通信特征來定制片上網(wǎng)絡(luò)的拓?fù)?才能設(shè)計(jì)出符合特定應(yīng)用通信特征需求的優(yōu)化片上網(wǎng)絡(luò)[3]。近年來，特定應(yīng)用的拓?fù)鋬?yōu)化得到了許多研究人員的深入研究，Srinivasan等[4]提出了一種基于整數(shù)線性規(guī)劃的拓?fù)渚C合方法，Murali[5]介紹一種定制可靠和高效的片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方法。為了更好地利用特定應(yīng)用的通信特征信息來定制和優(yōu)化特定應(yīng)用片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，必須根據(jù)應(yīng)用的通信特征來優(yōu)化其拓?fù)洹eary[6]等提出了基于3級(jí)遺傳算法的片上網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計(jì)。本文主要針對(duì)其進(jìn)行改進(jìn)，提出了一種改進(jìn)的3級(jí)遺傳算法來定制特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，相對(duì)于Leary等的算法，本算法取得了較好的優(yōu)化效果和運(yùn)行效率。
1 Leary的3級(jí)遺傳算法及不足
2009年，Leary等提出了一個(gè)3級(jí)的遺傳算法來解特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題，該算法以應(yīng)用通信特征圖ACCG、互連部件特性參數(shù)和系統(tǒng)平面布局為輸入，算法首先初始化種群個(gè)體，計(jì)算個(gè)體的適應(yīng)度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值和相應(yīng)的固定路由，該遺傳算法采用如圖1所示的3層結(jié)構(gòu)。這3個(gè)層次分別是路由器的選擇層、節(jié)點(diǎn)與路由端口的映射層和通信交通層。其中第1級(jí)別的路由器選擇層表示從所有可能的路由器集合中選取出一定數(shù)量的可用路由器,第2級(jí)別表示應(yīng)用通信特征圖中的結(jié)點(diǎn)到選中的路由器端口的映射，第3層表示應(yīng)用通信交通從源點(diǎn)到目的點(diǎn)經(jīng)過中間路由器端口的可能通信路由路徑。這種方法存在著明顯的不足：
(1) 在第2級(jí)的節(jié)點(diǎn)與路由器端口的映射層，對(duì)所選的路由器的所有端口進(jìn)行統(tǒng)一編號(hào)，然后把節(jié)點(diǎn)與端口之間進(jìn)行映射來實(shí)現(xiàn)節(jié)點(diǎn)與路由器連接。由于路由器有多個(gè)端口，同一個(gè)節(jié)點(diǎn)n1與路由器r1的不同端口進(jìn)行映射就是不同的種群個(gè)體。例如，假設(shè)路由器r1有5個(gè)端口，節(jié)點(diǎn)n1(圖中以帶圓圈的數(shù)字1表示,以下同)與這5端口的映射是5個(gè)不同的個(gè)體。然而，由于路由器的尺寸遠(yuǎn)比節(jié)點(diǎn)的尺寸小[24]，同一節(jié)點(diǎn)映射在同一路由器的不同端口其連接線的長(zhǎng)度應(yīng)該是一樣的，所以，可以把它們看作是同一個(gè)映射，即節(jié)點(diǎn)與路由器的映射，這樣，節(jié)點(diǎn)n1與路由器r1的映射只需1個(gè)個(gè)體來表示。
圖1 Leary的3級(jí)層次表示圖[6]
由于遺傳算法所有可能的不同個(gè)體集合構(gòu)成了算法的搜索空間，不同個(gè)體的數(shù)量越多，算法的搜索空間就越大，從而算法的運(yùn)行時(shí)間就越長(zhǎng)。此外，一個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定于3個(gè)方面：路由器的選擇、節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接，Leary的方法不僅增加了遺傳算法的搜索空間，第3級(jí)采用通信交通層也與拓?fù)涞?個(gè)方面沒有直觀的聯(lián)系。受到此啟發(fā)，本文提出了一種新的3級(jí)遺傳算法，它的3個(gè)層次分別為：路由器選擇層、節(jié)點(diǎn)與路由器映射層和路由器與路由器映射層。這3個(gè)層次不僅直觀反映網(wǎng)絡(luò)拓?fù)涞?個(gè)方面，同時(shí)也可以有效地減小GA搜索空間，加快仿真速度[11]。
2 改進(jìn)3級(jí)GA的拓?fù)浣Y(jié)構(gòu)優(yōu)化技術(shù)
網(wǎng)絡(luò)拓?fù)鋬?yōu)化問題是一個(gè)典型的多目標(biāo)優(yōu)化問題，它是斯坦納樹(Steiner Tree)的變形，是一個(gè)NP難問題[3]。用GA解NoC拓?fù)涠ㄖ茊栴}的流程如圖2所示，算法以應(yīng)用通信特征圖ACCG、互連部件特性參數(shù)和系統(tǒng)平面布局為輸入。算法首先初始化種群個(gè)體，計(jì)算個(gè)體的適應(yīng)度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值。為了有效地應(yīng)用GA技術(shù)，必須定義問題解的染色體有效表示方法，以及選擇、交叉及變異的基因操作[12]。
圖2 GA的流程圖
2.1 解染色體串的數(shù)據(jù)結(jié)構(gòu)
GA技術(shù)采用3級(jí)層次化的數(shù)據(jù)結(jié)構(gòu)如,圖3所示。
第1級(jí)是路由器選擇級(jí)別，用來表示在最大數(shù)量的路由器中哪些路由器被選擇來構(gòu)成NoC的拓?fù)浣Y(jié)構(gòu)。第2級(jí)的染色體串用來表示哪個(gè)節(jié)點(diǎn)與哪個(gè)路由器相連接，是表示節(jié)點(diǎn)與路由器的映射級(jí)別。第三級(jí)是路由器與路由器的映射級(jí)別，用來表示路由器間的相互連接方式，而不同于Leary方法的通信交通量的由路由端口組成的通信路徑。
(1) 路由器選擇級(jí)(第1級(jí))數(shù)據(jù)結(jié)構(gòu)。改進(jìn)的GA技術(shù)[13]把路由器選擇級(jí)別的數(shù)據(jù)結(jié)構(gòu)表示成一組常量個(gè)數(shù)的一維二進(jìn)制數(shù)組arstr[maxrouter]，其變量maxrouter是系統(tǒng)中所有可能的最大路由器個(gè)數(shù)，由于假定路由器分配在IP核的4個(gè)角落，所以總的最大可用路由器數(shù)量是IP核的4倍。arstr數(shù)組元素是隨機(jī)產(chǎn)生的0或者1，第i個(gè)元素是1或者0分別表示第i
圖3 層次化個(gè)體表示
個(gè)路由器被選擇或者沒有被選擇來構(gòu)成網(wǎng)絡(luò)拓?fù)洌琲∈[0..maxrouter]內(nèi)的整數(shù)。圖3所示的第1層個(gè)體的數(shù)據(jù)結(jié)構(gòu)如圖4所示，圖中arstr[i]=1表示第i個(gè)路由器被選擇到網(wǎng)絡(luò)體系結(jié)構(gòu)中，否則arstr[i]=0表示未選中。本文中的GA技術(shù)保持常數(shù)J個(gè)arstr個(gè)體。所有選擇出來的路由器從0開始統(tǒng)一進(jìn)行編號(hào)，為了建立所選擇的路由器與原來總的路由器之間的關(guān)系，定義一個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)routid的一維數(shù)組來存儲(chǔ)所選路由器在原來總路由器中的編號(hào)。
(2) 節(jié)點(diǎn)/路由器映射級(jí)(第2級(jí))數(shù)據(jù)結(jié)構(gòu)。第2級(jí)個(gè)體用染色體nrstr表示節(jié)點(diǎn)/路由器映射，整數(shù)數(shù)組nrstr[nodenum]用來表示節(jié)點(diǎn)/路由器的映射，其中nodenum代表ACCG圖中IP核的個(gè)數(shù)。在圖3中，節(jié)點(diǎn)2，3分別映射到路由器1。由于路由器有多個(gè)端口，不同的節(jié)點(diǎn)可以映射到同一個(gè)路由器，所以，數(shù)組nrstr中的元素可以重復(fù)，但節(jié)點(diǎn)/路由器的映射必須滿足一定的合法性條件[14]，這些合法性條件將在下一小節(jié)中介紹。在這一節(jié)中，為了記錄每個(gè)路由器與幾個(gè)節(jié)點(diǎn)相連接。
(3) 路由器/路由器映射級(jí)別(第3級(jí))數(shù)據(jù)結(jié)構(gòu)。在第3級(jí)別上，GA技術(shù)與Leary的第3級(jí)使用不同的數(shù)據(jù)結(jié)構(gòu)，使用路由器/路由器的映射來決定路由器之間的連接。這里，使用二維的二進(jìn)制矩陣rrstr來表示路由器之間的連接，矩陣rrstr是一個(gè)對(duì)稱矩陣，上三角矩陣元素rrstr[i][j](i 圖4 個(gè)體染色體的數(shù)據(jù)結(jié)構(gòu) NoC拓?fù)浣Y(jié)構(gòu)要求滿足一些充分必要的合法性條件，下面分別介紹3個(gè)級(jí)別解表示法的合法性條件。 (1) 路由器選擇的合法性條件。第1級(jí)的合法性條件是：為了保證網(wǎng)絡(luò)的連通性，避免路由器的選擇不當(dāng)導(dǎo)致成為孤島，必須滿足: rp≥n+2(r-1) (1) 式中：n為全連通的網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)；r為所選的路由器數(shù)；p為每個(gè)路由器有端口數(shù)。 即：由r個(gè)路由器構(gòu)成一個(gè)全連通的網(wǎng)絡(luò)至少需要用去2×(r-1)個(gè)端口。 (2) 節(jié)點(diǎn)/路由器映射級(jí)的合法性條件。在第2級(jí)別，需滿足下列合法性條件：節(jié)點(diǎn)與路由器的映射關(guān)系是一對(duì)一的關(guān)系，即一個(gè)節(jié)點(diǎn)都必須映射到一個(gè)路由器，且只能映射給NoC結(jié)構(gòu)中的一個(gè)路由器；而路由器與節(jié)點(diǎn)的關(guān)系是一對(duì)多的關(guān)系，即一個(gè)路由器可以連接到多個(gè)節(jié)點(diǎn)。 如果所選擇的路由器數(shù)量大于1個(gè)，每個(gè)路由器至少有一個(gè)端口空出來，用于把該路由器與其它路由器相連，以保證網(wǎng)絡(luò)的連通性。 (3) 路由器/路由器映射級(jí)的合法性條件。本級(jí)需滿足下列合法性條件：路由器至少必須與另一個(gè)路由器相連以保證網(wǎng)絡(luò)連通性。 由于受限于路由器的最大端口數(shù)，每個(gè)路由器的最大端口數(shù)需大于路由器的連接總數(shù)。一個(gè)路由器的總連接數(shù)包含節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接。 為確保單時(shí)鐘周期信號(hào)的傳播，兩個(gè)相鄰接路由器之間的曼哈頓距離需在所允許的通信距離之內(nèi)。 路由器端口的最大帶寬限制必須不能違規(guī)。 (1) 初始種群的產(chǎn)生。初始時(shí)，改進(jìn)的GA技術(shù)產(chǎn)生J個(gè)路由器選擇數(shù)組arstr，K個(gè)節(jié)點(diǎn)/路由器映射數(shù)組nrstr和L個(gè)路由器/路由器映射二維二進(jìn)制數(shù)組rrstr初始種群。對(duì)于J個(gè)路由器選擇級(jí)的個(gè)體，每個(gè)arstr數(shù)組都是通過隨機(jī)地賦值“0”或者“1”給每個(gè)數(shù)組元素來產(chǎn)生的。如果所產(chǎn)生的染色體數(shù)組不符合第一級(jí)的合法性，則通過隨機(jī)地把某個(gè)值為“0”的數(shù)組元素改變?yōu)?，直到滿足合法性條件。節(jié)點(diǎn)j路由器的染色體nrstr是選擇一個(gè)節(jié)點(diǎn)i，并隨機(jī)地把它分配給一個(gè)選擇出來的路由器，把該路由器的編號(hào)存儲(chǔ)在nrstr[i]中。同樣節(jié)點(diǎn)/路由器映射必須滿足上述的第2級(jí)合法性條件。最后，路由器/路由器映射是一個(gè)二維對(duì)稱的二進(jìn)制數(shù)組rrstr，這一級(jí)的初始個(gè)體是通過隨機(jī)地賦值“0”或者“1”給矩陣的上三角元素，隨后下三角元素賦值為對(duì)應(yīng)上三角元素的值來產(chǎn)生的。如果矩陣元素rrstr[i][j]=1，則意味著路由器i與路由器j間有一條物理鏈路直接相連，反之，rrstr[i][j]=0則沒有直接鏈路存在。矩陣的主對(duì)角元素rrstr[i][i]都被賦值為“0”，表示一個(gè)路由器不能通過一條線路連接到自身。矩陣的階數(shù)等于對(duì)應(yīng)的arstr中路由器個(gè)數(shù)。隨機(jī)產(chǎn)生的連接矩陣不一定符合第3級(jí)的合法性條件，如果違背合法性條件，則GA調(diào)用一個(gè)叫adjustment的過程來調(diào)整矩陣元素以滿足第3級(jí)的合法性條件。 (2) 適應(yīng)度函數(shù)。GA的選擇操作是根據(jù)適應(yīng)度函數(shù)值來選擇最適應(yīng)的個(gè)體來產(chǎn)生下一代種群。GA優(yōu)化目標(biāo)是最小化功耗和路由器資源，適應(yīng)度函數(shù)定義如下： (2) 式中:p是個(gè)體所表示的拓?fù)鋵?duì)所有通信交通所消耗的總能量;r是拓?fù)渲惺褂玫穆酚善鲾?shù)量;α和β則分別是p和r的權(quán)重。一旦個(gè)體所對(duì)應(yīng)的拓?fù)浣Y(jié)構(gòu)臨時(shí)確定之后，也就是一旦路由器已經(jīng)選擇、節(jié)點(diǎn)與路由器的連接和路由器與路由器的連接已經(jīng)完成，在滿足最大帶寬限制的前提下，采用Dijkstra最短路徑算法，可以對(duì)所有通信交通進(jìn)行路由，因此，每個(gè)通信交通的能量消耗能夠被計(jì)算出來。個(gè)體的能耗是ACCG中所有通信交通所消耗能量之和。 對(duì)于一個(gè)通信交通e從路由器r1流到r2的功耗可以下式計(jì)算： (3) 式中,dist(r1，r2)是路由器r1與r2之間的曼哈頓距離。對(duì)于某個(gè)通信交通，如果兩個(gè)節(jié)點(diǎn)之間沒有路徑可達(dá)，則假定其功耗為無窮大，因此該個(gè)體的適應(yīng)度最小，在選擇過程中，該個(gè)體就會(huì)被淘汰。 (1) 選擇操作。根據(jù)個(gè)體的適應(yīng)度值從當(dāng)前種群和新產(chǎn)生的個(gè)體中選擇指定數(shù)量最適應(yīng)的個(gè)體來產(chǎn)生下一代種群，在下一代個(gè)體的產(chǎn)生中自動(dòng)完成。 (2) 交叉操作。交叉操作是隨機(jī)地從當(dāng)前種群中選擇兩個(gè)個(gè)體(即雙親)進(jìn)行交配來產(chǎn)生下一代個(gè)體。在我們的GA技術(shù)中，我們使用均勻完全交叉操作。 (3) 變異操作。變異操作隨機(jī)地對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。 本文以MPEG4[7]，MWD[7]，VOPD[7]，DSP[8]4種多媒體應(yīng)用標(biāo)準(zhǔn)測(cè)試程序來定制不規(guī)則拓?fù)浣Y(jié)構(gòu)，并給出最小的能耗值。所有的處理核的尺寸都是隨機(jī)生成的，面積大約為1.5 mm×1.5 mm=2.25 mm2，路由器的輸入和輸出端口的功耗估計(jì)分別為328和65.5 nW/(Mb·s-1)，而鏈路的單位功耗為79.6 (nW·Mb-1)/(s·mm-1)。MPEG4和DSP的應(yīng)用通信特征圖ACCG如圖5所示，VOPD、MWD的應(yīng)用通信特征圖如圖6所示。 (a)MPEG4 (b)DSP 圖5 MPEG4[7]，DSP[8]應(yīng)用通信特征圖ACCG 針對(duì)上面的標(biāo)準(zhǔn)測(cè)試程序，在Window7平臺(tái)上，用Visusal C++6.0進(jìn)行編程實(shí)現(xiàn)，其中遺傳算法的各級(jí)交叉概率為90%，變異概率為0.5%，各個(gè)級(jí)別的個(gè)體數(shù)量均為1 000個(gè)，實(shí)驗(yàn)的結(jié)果如表1所示，可見，本文改進(jìn)的遺傳算法定制NoC拓?fù)浣Y(jié)構(gòu)[9]時(shí)，功耗有一定的改進(jìn)，雖然相對(duì)Leary方法改進(jìn)不大，平均能耗改進(jìn)只有3.74%，其主要原因是因?yàn)長(zhǎng)eary方法已經(jīng)是較好的優(yōu)化結(jié)果。但是，在仿真時(shí)間由309.125 s減少至254.2 s，卻有較大的減少，平均提高17.4%，其原因是遺傳算法的不同個(gè)體的數(shù)量越多，算法的搜索空間就越大，從而算法的運(yùn)行時(shí)間就越長(zhǎng)。本文的改進(jìn)方面在遺傳算法的搜索空間上有較大的改進(jìn)[10]，相比Leary方法在搜索空間上有較大的減少，從而減少搜索時(shí)間。 (a)VOPD (b)MWD 圖6 VOPD[7]，MWD[7]應(yīng)用通信特征圖ACCG 表1 實(shí)驗(yàn)結(jié)果 片上網(wǎng)絡(luò)(NoC)是將來眾核片上系統(tǒng)通信問題的有效解決方案，而特定應(yīng)用拓?fù)鋬?yōu)化能夠充分利用應(yīng)用的通信特征來定制優(yōu)化片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。有約束的特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)鋬?yōu)化定制是一種NP完全的問題，目前沒有有效的優(yōu)化方法，本文針對(duì)Leary[6]等提出了基于3級(jí)遺傳算法的片上網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計(jì)中不足進(jìn)行改進(jìn)，提出了一種改進(jìn)的3級(jí)遺傳算法來優(yōu)化定制特定應(yīng)用片上網(wǎng)絡(luò)拓?fù)洌訫PEG4[7]等4種標(biāo)準(zhǔn)多媒體應(yīng)用通信特征來測(cè)試，實(shí)驗(yàn)結(jié)果表明本文的方法在仿真時(shí)間上有較大的改進(jìn)，平均提高17.4%。 參考文獻(xiàn)(References)： [1] 鄭靈翔. 嵌入式系統(tǒng)設(shè)計(jì)與應(yīng)用開發(fā)[M]. 北京:北京航空航天大學(xué)出版社，2006. [2] Hemani A, Jantsch A, Kumar S,etal. Network on a Chip: An architecture for billion transistor era [C]//Proceeding of IEEE NorChip Conference, 2000:166-173. [3] Garey M R, Johnson D S. Computers and intractability: A guide to the theory of NP-completeness [M]. Freeman, 1979: 121-130. [4] Srinivasan K, Chatha K S, Konjevod G. Linear-programming-based techniques for synthesis of Network-on-Chip architectures [J]. IEEE Transaction on Very Large Scale Integration (VLSI), 2006, 14(4): 407-420. [5] Murali S. Designing reliable and efficient networks on chips [J]. Lecture Notes in Electrical Engineering, 2009, 34:57-75. [6] Leary G I, Srinivasan K, Mehta K,etal. Design of Network-on-Chip architectures with a Genetic Algorithm-based technique [J], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2009, 17(5): 674-687. [7] Jalabert A, Murali S, Benini L,etal. XpipesCompiler: A tool for instantiating application specific Networks on Chip [C]//Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2004(2):884-889. [8] Murali S, Micheli G D. SUNMAP: A tool for automatic topology selection and generation for NoCs [C]//Proceedings of 41st Design Automation Conference, 2004:914-919. [9] Zhang Ying, Wu Ning, Ge Fen, Sectional NoC Mapping Scheme Optimized for Testing Time[J]. Transactions on Engineering TechnologiesWorld Congress on Engineering and Computer Science 2014,2015:301-314. [10] Ji Wu, Dezun Dong, Xiangke Liao,etal. Energy-efficient NoC with multi-granularity power optimization[J]. The Journal of Supercomputing, 2015, 73(4):1654-1671. [11] 鄧 可,賀向前.基于遺傳算法的自適應(yīng)控制系統(tǒng)[J]．實(shí)驗(yàn)室研究與探索，2007，26( 10) : 41-43，72． [12] 趙文龍,黃 尋.基于遺傳計(jì)算模糊PID的數(shù)字隨動(dòng)系統(tǒng)設(shè)計(jì)[J]．實(shí)驗(yàn)室研究與探索，2017，36( 3) :143-147． [13] 馬丹妮,李傳江.基于遺傳算法的七自由度機(jī)器人軌跡[J]．實(shí)驗(yàn)室研究與探索，2016，35( 9) :33-37． [14] Elmiligi H,Gebali F,El-Kharashi M W.Power-awaremapping for 3D-NoC designs using genetic algorithms[J].Procedia Computer Science，2014，34：538-543. [15] Wang J，Li L，Wang Z，etal.Energy-efficient mapping for 3D NoC using logistic function based adaptive geneticalgorithms[J].Chinese Journal of Electronics，2014，23(2)：254-262.2.2 解表示法的合法性條件
2.3 初始種群的產(chǎn)生和適合度函數(shù)
2.4 3個(gè)級(jí)別的遺傳基因操作
3 實(shí)驗(yàn)結(jié)果及討論
3.1 實(shí)驗(yàn)設(shè)置
3.2 實(shí)驗(yàn)結(jié)果分析
4 結(jié) 語
