改進的三級遺傳算法定制特定應用片上網絡拓撲

熊　昕　賴國明

1(廣州番禺職業技術學院現代教育技術與信息中心　廣東 廣州 511483) 2(惠州學院信息科學技術學院　廣東 惠州 516007)

0　引　言

集成電路的發展已經達到了深亞微米及納米級別階段，但仍然遵循著著名的摩爾定律：芯片上晶體管數量每18個月翻一番，且仍將按這個規律所指示的方向推進。為此，單芯片上晶體管的規模達到數億個，從而其計算能力的提高為嵌入系統帶來了根本性變革。首先，嵌入系統的功能越來越強大，系統復雜度也越來越高；其次，IC芯片的集成度越來越高，系統體積也越來越小。嵌入式系統向著微型化方面的發展使得將整個嵌入式系統集成單塊芯片上形成所謂的片上系統SoC(System on Chip)。片上系統SoC是指在單個芯片上集成了專用處理器、通用處理器，DSP、共享內存塊、專用內存塊、I/O部件等多個知識產權(IP)核的復雜系統，其具有更強大的功能、更低的成本、更小的產品體積、更好的可靠性和更靈活的配置，從而成為新一代應用電子技術的核心。片上系統SOC為集成電路技術的應用和集成電路產業發展提供了的廣闊市場和全新的發展機遇，是當今大規模集成電路(VLSI)技術的主要發展趨勢和發展主流[1]。

今后高端的SoC片內互連的處理核數量都很多，例如Intel實驗室已經有80核心的SoC,片內的通信就會成為SoC的主要性能瓶頸，如何解決其高通信需求是當前高端SoC面臨的迫切問題，片上網絡NoC為解決SoC的通信問題提供了新的有效途徑。網絡拓撲結構中處理核的相對位置及其之間的連接方式極大地影響著片上網絡的時延、功耗等性能指標[2]。網絡拓撲結構是網絡路由算法設計、緩沖區分配、容錯處理等的其他后繼相關研究的前提和基礎。由于SoC主要是面向特定應用或者少數應用類的，一旦應用通信特征圖確定，其所需要的節點間的通信帶寬和時延限制就基本確定，因此，片上網絡的設計必須利用特定應用的通信特征來定制片上網絡的拓撲才能設計出符合特定應用通信特征需求的優化片上網絡[3]。近年來，特定應用的拓撲優化得到了許多研究人員的深入研究，Srinivasan[4]提出了一種基于整數線性規劃的拓撲綜合方法，Murali[5]介紹一種定制可靠和高效的片上網絡拓撲結構方法。為了更好地利用特定應用的通信特征信息來定制和優化特定應用片上網絡的拓撲結構，必須根據應用的通信特征來優化其拓撲。Leary等[6]提出了基于三級遺傳算法的片上網絡體系結構設計。本文主要針對其進行改進，提出了一種改進的三級遺傳算法來定制特定應用片上網絡拓撲結構，相對于Leary等的算法，我們的算法取得了較好的優化效果和運行效率。

1　Leary等的三級遺傳算法及不足

2009年，Leary等在IEEE Transactions on Very Large Scale Integration (VLSI) Systems的第17卷第5期中提出了一個三級的遺傳算法來解特定應用片上網絡拓撲優化問題。該算法以應用通信特征圖ACCG、互連部件特性參數和系統平面布局為輸入，首先初始化種群個體，計算個體的適應度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值和相應的固定路由。該遺傳算法采用如圖1所示的三層結構。

圖1　Leary的三級層次表示圖[6]

這三個層次分別是路由器的選擇層、節點與路由端口的映射層和通信交通層。其中第一層次的路由器選擇層表示從所有可能的路由器集合中選取出一定數量的可用路由器。第二級別表示應用通信特征圖中的結點到選中的路由器端口的映射。第三層表示應用通信交通從源點到目的點經過中間路由器端口的可能通信路由路徑。但是，他們的方法存在著明顯的不足：

(1) 在第二層的節點與路由器端口的映射層，他們對所選的路由器的所有端口進行統一編號，然后把節點與端口之間進行映射來實現節點與路由器連接。由于路由器有多個端口，同一個節點n1與路由器r1的不同端口進行映射就是不同的種群個體。例如，假設路由器r1有5個端口，節點n1與這5端口的映射是5個不同的個體。然而，由于路由器的尺寸遠比節點的尺寸小，同一節點映射在同一路由器的不同端口其連接線的長度應該是一樣的，所以，可以把它們看作是同一個映射，即節點與路由器的映射，這樣，節點n1與路由器r1的映射只需1個個體來表示。

由于遺傳算法所有可能的不同個體集合構成了算法的搜索空間，不同個體的數量越多，算法的搜索空間就越大，從而算法的運行時間就越長。此外，一個網絡的拓撲結構決定于三個方面：路由器的選擇、節點與路由器的連接和路由器與路由器的連接，Leary的方法不僅增加了遺傳算法的搜索空間，第三層采用通信交通層也與拓撲的三個方面沒有直觀的聯系。受此啟發，我們提出了一種新的三級遺傳算法，它的三個層次分別為：路由器選擇層、節點與路由器映射層和路由器與路由器映射層。這三個層次不僅直觀反映網絡拓撲的三個方面，同時也可以有效地減小GA搜索空間，加快仿真速度。

2　改進三級GA的拓撲結構優化技術

網絡拓撲優化問題是一個典型的多目標優化問題，它是斯坦納樹的變形，是一個NP難問題[3]。遺傳算法GA適合于解這類NP難問題，用GA解NoC拓撲定制問題的流程如圖2所示，算法以應用通信特征圖ACCG、互連部件特性參數和系統平面布局為輸入。算法首先初始化種群個體，計算個體的適應度值，然后不斷迭代交叉、變異和選擇操作直到滿足終止條件為止，并輸出最小能耗值。為了有效地應用GA技術，必須定義問題解的染色體有效表示方法，以及選擇、交叉及變異的基因操作，這里給出我們的GA算法的相關技術。

圖2　GA的流程圖

2.1　解染色體串的數據結構

我們的GA技術采用三級層次化的數據結構如圖3所示。

圖3　層次化個體表示

第一級是路由器選擇級別，用來表示在最大數量的路由器中哪些路由器被選擇來構成NoC的拓撲結構。第二級的染色體串用來表示哪個節點與哪個路由器相連接，是表示節點與路由器的映射級別。第三級是路由器與路由器的映射級別，用來表示路由器間的相互連接方式，而不同于Leary方法的通信交通量的由路由端口組成的通信路徑。

2.1.1路由器選擇級(第一級)數據結構

改進的GA技術把路由器選擇級別的數據結構表示成一組常量個數的一維二進制數組arstr[maxrouter]，其變量maxrouter是系統中所有可能的最大路由器個數，由于我們假定路由器分配在IP核的四個角落，所以總的最大可用路由器數量是IP核的四倍。arstr數組元素是隨機產生的0或者1，第i個元素是1或者0分別表示第i個路由器被選擇或者沒有被選擇來構成網絡拓撲，i∈[0..max]內的整數。圖3所示的第一層個體的數據結構如圖4所示，圖中arstr[i]=1表示第i個路由器被選擇到網絡體系結構中，否則 arstr[i]=0表示未選中。本文中的GA技術保持常數J個arstr個體。所有選擇出來的路由器從0開始統一進行編號，為了建立所選擇的路由器與原來總的路由器之間的關系，這里我們要定義一個輔助的數據結構routid的一維數組來存儲所選路由器在原來總路由器中的編號。

圖4　個體染色體的數據結構

2.1.2節點/路由器映射級(第二級)數據結構

第二級個體用染色體nrstr表示節點/路由器映射，整數數組nrstr[nodenum]用來表示節點/路由器的映射，其中nodenum代表ACCG圖中IP核的個數。在圖3中，節點2，3分別映射到路由器1。由于路由器有多個端口，不同的節點可以映射到同一個路由器，所以，數組nrstr中的元素可以重復，但節點/路由器的映射必須滿足一定的合法性條件，這些合法性條件將在下一節中介紹。

2.1.3路由器/路由器映射級別(第三級)數據結構

在第三級別上，我們的GA技術與G.Leary的第三級使用不同的數據結構。我們使用路由器/路由器的映射來決定路由器之間的連接。這里，我們使用二維的二進制矩陣rrstr來表示路由器之間的連接，矩陣rrstr是一個對稱矩陣，上三角矩陣元素rrstr[i][j](i

2.2　解表示法的合法性條件

NoC拓撲結構要求滿足一些充分必要的合法性條件，下面分別介紹三個級別解表示法的合法性條件。

2.2.1路由器選擇的合法性條件

第一級的合法性條件是：

為了保證網絡的連通性，避免路由器的選擇不當導致成為孤島，必須滿足：

r×p≥n+2×(r-1)

(1)

式中：n為全連通的網絡中節點數；r為所選的路由器數；p為每個路由器有端口數。

即：由r個路由器構成一個全連通的網絡至少需要用去2×(r-1)個端口。

2.2.2節點/路由器映射級的合法性條件

在第二級別，需滿足下列合法性條件：

? 節點與路由器的映射關系是一對一的關系，即一個節點都必須映射到一個路由器，且只能映射給NoC結構中的一個路由器；而路由器與節點的關系是一對多的關系，即一個路由器可以連接到多個節點。

? 如果所選擇的路由器數量大于1個，每個路由器至少有一個端口空出來，用于把該路由器與其他路由器相連，以保證網絡的連通性。

2.2.3路由器/路由器映射級的合法性條件

本級需滿足下列合法性條件：

? 路由器至少必須與另一個路由器相連以保證網絡連通性。

? 由于受限于路由器的最大端口數，每個路由器的最大端口數需大于路由器的連接總數。一個路由器的總連接數包含節點與路由器的連接和路由器與路由器的連接。

? 為確保單時鐘周期信號的傳播，兩個相鄰接路由器之間的曼哈頓距離需在所允許的通信距離之內。

? 路由器端口的最大帶寬限制必須不能違規。

2.3　初始種群的產生和適合度函數

2.3.1初始種群的產生

初始時，改進的GA技術產生J個路由器選擇數組arstr，K個節點/路由器映射數組nrstr和L個路由器/路由器映射二維二進制數組rrstr初始種群。對于J個路由器選擇級的個體，每個arstr數組都是通過隨機地賦值“0”或者“1”給每個數組元素來產生的。如果所產生的染色體數組不符合第一級的合法性，則通過隨機地把某個值為“0”的數組元素改變為1，直到滿足合法性條件。節點j路由器的染色體nrstr是選擇一個節點i，并隨機地把它分配給一個選擇出來的路由器，把該路由器的編號存儲在nrstr[i]中。同樣節點/路由器映射必須滿足上述的第二級合法性條件。最后，路由器/路由器映射是一個二維對稱的二進制數組rrstr，這一級的初始個體是通過隨機地賦值“0”或者“1”給矩陣的上三角元素，隨后下三角元素賦值為對應上三角元素的值來產生的。如果矩陣元素rrstr[i][j]=1，則意味著路由器i與路由器j間有一條物理鏈路直接相連，反之，rrstr[i][j]=0則沒有直接鏈路存在。矩陣的主對角元素rrstr[i][i]都被賦值為“0”，表示一個路由器不能通過一條線路連接到自身。矩陣的階數等于對應的arstr中路由器個數。隨機產生的連接矩陣不一定符合第三級的合法性條件，如果違背合法性條件，我們GA調用一個叫adjustment的過程來調整矩陣元素以滿足第三級的合法性條件。

2.3.2適應度函數

GA的選擇操作是根據適應度函數值來選擇最適應的個體來產生下一代種群。我們的GA優化目標是最小化功耗和路由器資源，適應度函數定義如下：

(2)

式中：p是個體所表示的拓撲對所有通信交通所消耗的總能量;r是拓撲中使用的路由器數量;α和β則分別是p和r的權重。一旦個體所對應的拓撲結構臨時確定之后，也就是一旦路由器已經選擇、節點與路由器的連接和路由器與路由器的連接已經完成，在滿足最大帶寬限制的前提下，采用Dijkstra最短路徑算法，可以對所有通信交通進行路由，因此，每個通信交通的能量消耗能夠被計算出來。個體的能耗是ACCG中所有通信交通所消耗能量之和。

對于一個通信交通e從路由器r1流到r2的功耗可以式(3)來計算：

(3)

這里dist(r1，r2)是路由器r1與r2之間的曼哈頓距離。對于某個通信交通，如果兩個節點之間沒有路徑可達，則假定其功耗為無窮大，因此該個體的適應度最小，在選擇過程中，該個體就會被淘汰。

2.4　三個級別的遺傳基因操作

GA技術要求有選擇、交叉和變異三個基因操作。

2.4.1選擇操作

根據個體的適應度值從當前種群和新產生的個體中選擇指定數量最適應的個體來產生下一代種群，在下一代個體的產生中自動完成。

2.4.2交叉操作

交叉操作是隨機地從當前種群中選擇兩個個體(即雙親)進行交配來產生下一代個體。在我們的GA技術中，我們使用均勻完全交叉操作。

2.4.3變異操作

變異操作隨機地對個體中的某些基因執行異向轉化。

3　實驗結果及討論

3.1　實驗設置

本文以MPEG4[7]，MWD[7]，VOPD[7]，DSP[8]四種多媒體應用標準測試程序來定制不規則拓撲結構，并給出最小的能耗值。所有的處理核的尺寸都是隨機生成的，面積大約為1.5×1.5=2.25 mm2，路由器的輸入和輸出端口的功耗估計分別為328和65.5 nw/Mb/s，而鏈路的單位功耗為79.6 nW/Mb/s/mm。MPEG4和DSP的應用通信特征圖ACCG如圖5所示。VOPD，MWD的應用通信特征圖如圖6所示。

圖5　MPEG4[7]，DSP[8]應用通信特征圖ACCG

圖6　VOPD[7],MWD[7]應用通信特征圖ACCG

3.2　實驗結果分析

針對上面的標準測試程序，在Windows 7平臺上，用Visusal C++6.0進行編程實現，其中遺傳算法的各級交叉概率為90%，變異概率為0.5%，各個級別的個體數量均為1 000個，實驗的結果如表1所示。本文改進的遺傳算法定制NoC拓撲結構時，功耗有一定的改進，雖然相對Leary方法改進不大，平均能耗改進只有3.74%，其主要原因是因為Leary方法已經是較好的優化結果。但是，在仿真時間由309.125秒減少至254.2秒，卻有較大的減少，平均提高17.4%，其原因是遺傳算法的不同個體的數量越多，算法的搜索空間就越大，從而算法的運行時間就越長。本文的改進方面在遺傳算法的搜索空間上有較大的改進，相比Leary方法在搜索空間上有較大的減少，從而減少搜索時間。

表1　實驗結果

4　結　語

片上網絡(NoC)是將來眾核片上系統通信問題的有效解決方案，而特定應用拓撲優化能夠充分利用應用的通信特征來定制優化片上網絡的拓撲結構。有約束的特定應用片上網絡拓撲優化定制是一種NP完全的問題，目前沒有有效的優化方法。本文針對Leary[6]等提出了基于三級遺傳算法的片上網絡體系結構設計中不足進行改進，提出了一種改進的三級遺傳算法來優化定制特定應用片上網絡拓撲。以MPEG4[7]等四種標準多媒體應用通信特征來測試，實驗結果表明本文的方法在仿真時間上有較大的改進，平均提高17.4%。

[1] 鄭靈翔. 嵌入式系統設計與應用開發[M]. 北京:北京航空航天大學出版社，2006:1-7.

[2] Hemani A, Jantsch A, Postula A, et al. 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, Srinivasan K, Mehta K, et al. Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique[J]. IEEE Transactions on Very Large Scale Integration Systems, 2009, 17(5):674-687.

[7] Jalabert A, Murali S, Benini L, et al. 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]. Lecture Notes in Engineering & Computer Science, 2014, 2213(1):301-314.

[10] Wu J, Dong D, Liao X, et al. Energy-efficient NoC with multi-granularity power optimization[J]. Journal of Supercomputing, 2016, 73(4):1-18.