異構三維片上網絡布局優化的超圖劃分算法*

宋國治，張大坤，馬杰超，涂　遙，劉　暢天津工業大學 計算機科學與軟件學院，天津 300387

?

異構三維片上網絡布局優化的超圖劃分算法*

宋國治+，張大坤，馬杰超，涂遙，劉暢
天津工業大學 計算機科學與軟件學院，天津 300387

SONG Guozhi,ZHANG Dakun,MA Jiechao,et al.Hyper-graph partition algorithms for heterogeneous 3D network-on-chip floorplanning optimization.Journal of Frontiers of Computer Science and Technology, 2016,10(6):811-821.

摘要：片上網絡作為一種將大量嵌入式內核集成到單個晶圓片上的可行性技術，與傳統片上系統相比，更能應對未來需要更大規模集成內核的挑戰，從而得到了更廣泛的應用。然而，目前大多數對片上網絡的研究是在規則的架構上進行的，即假定所有單元片面積相同，但是這種假設過于理想化。因此，基于異構布局的三維片上網絡的研究是非常有必要的，而其中網絡單元的合理劃分對片上網絡的性能有著重要的影響。介紹了基于異構布局的三維片上網絡架構，并將超大規模集成網絡中的單元映射成一張超圖，并且對此超圖進行了多級劃分。在算法框架的不同階段，介紹了常見的算法，并且對相應算法的潛在問題進行分析，隨后對這幾種算法進行改進以提高片上網絡的性能。最后，通過對幾個常見的超大規模集成單元數據集進行實驗分析，比較了不同階段的算法對該片上網絡各個性能的影響，并得出各個數據集上最優的hMetis算法框架。

關鍵詞：三維片上網絡；異構布局；超圖劃分；hMetis

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science andTechnology

1673-9418/2016/10(06)-0811-11

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

隨著芯片制造業的迅速發展，芯片規模日益擴大，原有的總線結構和點到點的互連已經不能滿足通信的需求。因此，片上網絡應運而生。

由于片上網絡本身的規模十分龐大，并且受到現有計算機計算能力的限制，需要將網絡上原有的單元進行重新劃分布局，來提高該片上網絡的性能。超圖具有的一些特征可以用來表示一些非規則問題中的結構，例如分布式數據庫中的數據相關性，超大規模集成電路（very large scale integration，VLSI）中元件的連通性[1]等。超圖能夠很好地反映超大規模集成元件的劃分布局。

對于三維片上網絡，之前的許多研究都假設所有單元片的面積都是相同的，即同構結構，但是不同的公司所生產的不同型號的IP（intellectual property）單元片面積各不相同，因此這種假設是很不實際的。針對這一類單元片面積不同的片上網絡，美國北達科他州立大學的de Paulo和Ababei提出了一種基于異構布局的二層片上網絡架構[2]和三層片上網絡架構[3]，分別如圖1（b）和圖（c）所示。此架構的特點在于將單元片和路由器進行分離處理，在基于異構布局的二層片上網絡架構中，Layer 2為均勻規則分布的Mesh架構的路由器，而在Layer 1上是面積不規則的單元片。在基于異構的三層片上網絡架構中，Layer 2為規則的路由器，Layer 1和Layer 3為異構的單元片。然而，對于如何將原片上網絡單元片劃分到Layer 1和Layer 3，有著眾多的劃分方式。不同的劃分方法對片上網絡最終性能有著很大的影響。對于該步驟的劃分問題可以被抽象為是對超圖進行的二分問題。圖1為基于異構布局的三維片上網絡，其中（a）為初始不帶路由器的布圖；（b）為二層架構；（c）為三層架構；（d）為每個IP核面積擴展以容納網絡接口、路由器及物理連接布線后的二維實現。

Fig.1　3D NoC with heterogeneous floorplan圖1　基于異構布局的三維片上網絡

在過去的幾十年間，已經有許多國內外該領域的相關學者對圖的劃分問題開展了廣泛深入的研究，特別是超圖劃分算法的研究已引起越來越多業界人士的關注。早在20世紀70年代美國的普林斯頓大學的Kernighan和Lin就提出了組遷移（group migration）算法的思想[4]，并設計了經典的KL算法。該算法的主要思想是將一個網絡節點圖分割成兩個相等的節點集合，使得連接兩個集合的邊權最小。KL算法是基于無向二分圖劃分的第一個有效的啟發式算法。

之后Fiduccia和Mattheyses[5]提出了著名的FM算法，在該算法中，主要引入了單元增益值和面積約束函數。該算法也是首先產生一個初始劃分，然后進行頂點的遷移，并且每次遷移以單元的形式從一個子集遷移到另一個子集當中，而且元件的移動要考慮是否滿足約束函數，是否降低了域的解空間。

最近，Karypis和Kumar提出了一種基于圖的多級劃分算法[6-7]，隨后他們又將該理論應用到超圖的多級劃分中[8]，基于超圖的多級劃分算法可以得到一個較好的二分超圖。

本文將片上網絡中的單元映射成超圖，介紹了基于超圖劃分的多級劃分算法框架，對這些常用的劃分算法進行了分析改進，并且將其運用到片上網絡的設計中，以提高片上網絡的性能。在得到一個劃分完的二分超圖后，將兩個子圖分別進行合理的分配，以求得到較好的網絡性能。在實驗中采用了模擬退火算法來對該子圖進行合理的布局。而片上網絡的吞吐量和網絡的運行時間被用作衡量整個算法框架的標準。

2　超圖多級劃分的基本框架

2.1超圖的基本概念

所謂超圖（hyper-graph），是對圖的一種擴展。在超圖中，一條邊連接著任意多個點，每條超邊是超圖點集的一個非空子集。超圖H可以定義為一對邊和頂點的集合H=(X,E)[9]，其中X為頂點的集合，E為X的非空子集。

本文將具體的電路映射成為超圖，具體映射方法可參照圖2[10]。圖2（a）表示片上網絡中的電路邏輯圖，每個元件都是從左端輸入，從右端輸出。對于每一個元件，以該元件的輸出端為輸入信號的所有元件可以組成一條超邊。以圖2（b）中的B元件為例，以B元件的輸出端為輸入信號的有D、E、F，因此可以將B與D、E、F組成一個超邊，而其中這4個元件被映射為超邊中的4個頂點。于是圖2（a）中的各個元件可以被映射成為一張超圖，如圖2（b）所示。

下面給出在超圖模型中所涉及的兩個定義：

定義1（頂點權重）對于超圖H=(X，E)的權值，頂點集V的權值之和稱為超圖的權值。其中超邊集E的權重即為該超邊中的頂點的權值之和。在電路劃分問題中，一般將單元片的面積作為超圖中頂點的權值。

定義2（超邊切）對于超邊e，如果其所包含的頂點存在于其他不同的超邊之中，稱該超邊為其他超邊的超邊切[11]。

在將超圖進行切割時，每一條超邊看作一個子圖，其中子圖中每兩個定點都是相互連接的，連接的權值為超邊的權重比上超邊的勢（cardinality）。所謂勢，是指該超邊所包含的頂點的個數。該子圖被切割為H1和H2。超圖的超邊切可定義為：

其中，w(e)為該超邊的權重；||H1、||H2為被切割后兩個子圖的勢； ||e為切割前原超邊的勢。

Fig.2　Mapping of devices on 3D network-on-chip圖2　三維片上網絡中元件的映射

由于超邊切的數量和超邊的大小成正比關系[12]，想要得到一種較好的劃分，應研究如何能夠更好地降低超邊的大小。

2.2hMetis算法框架

多級劃分的算法框架首先在圖劃分問題中由明尼蘇達大學的Karypis等人[7,10,13]提出，并且將此框架推廣到了超圖劃分的問題中。此框架使用不同的算法將超圖的邊和頂點進行合并，從而得到一個有原超圖特征的較小的超圖。

hMetis劃分算法框架可分為3個階段，粗化階段，初始劃分階段，遷移優化階段，如圖3所示[9]。在粗化階段，將某些超圖的節點結合在一起，得到下一級粗化超圖，重復此過程直到粗化超圖足夠小為止，即得到一個最小的超圖。在初始劃分階段，對該最小超圖進行對分，得到一個初始劃分。因為許多超圖劃分算法在超圖比較大的情況下得不到較好的劃分性能，所以在最后的遷移優化階段，將劃分從最小的超圖投影回原始的超圖，在每一水平層的粗化超圖中，對劃分進行遷移優化。

Fig.3　Various phases of multilevel graph bisection圖3　hMetis框架算法的不同階段

本文2.2.1小節介紹粗化階段所使用的粗化算法，2.2.2小節介紹初始劃分階段的具體實現，2.2.3小節介紹遷移優化的相關算法。

2.2.1粗化階段算法

在粗化階段，超圖中的一系列頂點被合并成一個頂點，生成一系列的逐漸變小的超圖，而這些粗化后的超圖的性能不會明顯比原圖差。因為將原超圖進行多級劃分的目的是為了能在遷移優化階段得到一種更好的超圖劃分?；贙L-FM等系列的啟發式算法能在較小的超圖中發揮較好的性能，但是隨著超圖的頂點數和邊數的增大，這些啟發式優化算法將不再適用。

本文將介紹3種常見的粗化階段頂點不同的合并算法。（1）邊粗化（edge coarsening，EC）選擇在同一超邊內的兩個頂點，將它們合并成一個頂點。（2）超邊粗化（hyperedge coarsening，HEC）將屬于同一個超邊中所有獨立的頂點合并成一個頂點。（3）改進超邊粗化（modified hyperedge coarsening，MHEC）是基于第二種方法的優化，因為一旦將超圖中的所有頂點合并后，和該超邊相關但是沒有被合并的頂點與合并后的頂點在權值上會有很大的差異，這將會降低超圖的劃分效率。為了在優化階段得到更好的劃分，可以將超圖中未被合并的那一部分頂點進行合并。該3種算法的具體合并方式如下。

（1）邊粗化

在邊粗化方案中，各個頂點被隨機地訪問，對于任意一個頂點v，所有和v屬于同一個超邊并且尚未被其他頂點匹配的頂點將在v的匹配序列之內，在此序列中，可以將計算出的能與v匹配合并后得到最大權值的頂點進行匹配合并，而合并后所得到的權值為兩個頂點的權值之和。合并后超邊的權值為：

其中，e為超邊所表示的勢的大小。

在邊粗化算法中，是將超圖中的超邊間接地看作一般圖中的邊，然而這里并沒有真正地將超邊轉化為一般的邊，因此被粗化后的超圖仍能較好地保有原超圖的特征。

（2）超邊粗化

盡管邊粗化方案能夠逐漸地生成可以很好地擁有原超圖特征的許多更小的超圖，但是該方案每次粗化只能合并兩個匹配的頂點，該過程需要粗化許多次才能得到一個較小的超圖。因此，該方案并不能很快地得到足夠小的超圖。

在超邊粗化方案中是將屬于同一個超邊中的所有頂點合并為一個頂點。具體的實現方式如下：該方案將超邊以權重的非遞增順序排列并依次訪問，當遇到超邊的權重相同時，以超邊大小的非遞減順序訪問。按照此訪問順序，對于每一個超邊中還未被匹配的所有頂點，將此頂點集進行合并。因此，該方案優先選擇那些具有較大權值和較小大小的超邊。最后，直到所有的超邊完全被訪問，然后可以將這些被匹配完并且合并后的頂點作為下一級將被粗化的超圖。而那些未被合并的頂點將會簡單地被復制到下一級被粗化的超圖。

（3）改進超邊粗化

超邊粗化算法能夠顯著地減小超邊的權重，然而在每個粗化階段，大多數超邊并沒有被合并，因為屬于它們的頂點已經由其他的超邊進行了合并。這導致了兩個問題：第一，超邊的大小減小得并不充分，使得基于FM-KL系列算法的遷移優化階段變得困難。第二，頂點的權重（即已被合并的頂點的權重）被粗化的程度顯著不同，導致超圖形狀的扭曲。

為了解決這一問題，可以在進行完HEC方案后，重新按照序列中的訪問次序訪問超邊，并且對那些沒有被合并的頂點進行合并。

2.2.2初始劃分階段算法

經過粗化階段以后，會得到一個足夠小的超圖，通常來說頂點數|V|<100為一個比較合適的標準值。而在初始劃分階段，通常進行二分法，即使用一條線將超圖分割為兩個部分。在初始劃分中考慮負載的平衡和頂點之間的通信。

在后面實驗部分所使用的是一種較為簡單并且效果比較好的劃分算法。其主要思想是任意選取一個頂點，并由該頂點開始，依據圖的連通性，逐漸地生長，直到生長出來半數原圖的頂點。

具體的算法描述如下：

步驟1任意選取超圖的一個頂點，記為0。

步驟2按照廣度優先遍歷方式，從頂點0開始遍歷圖，與頂點0相鄰的頂點均記為1；循環此過程，與頂點i相鄰的頂點均記為i+1。

步驟3當所有訪問過的頂點數目等于頂點總數的一半的時候，算法結束。

然而，該算法所得出的二分圖并不是最優解，下面將從兩個角度出發，考慮對其進行優化。

第一，初始頂點的選取角度。容易得出，當所選的頂點位于圖的邊緣部分，將能得到一個較好的二分圖。與之相反，如果所選取的頂點位于圖的中間部分，那么該圖并不能被很好地平衡劃分。因此可以對該算法進行限制。假定初始所選取的頂點在一個特定的區域之中（圖的邊界范圍），然后隨機選取該范圍內的頂點作為初始頂點。

第二，在初始劃分階段所得到的擁有最小超邊切的劃分方式，在經過遷移優化階段投射為原超圖后，也許并不是原超圖所擁有的最小超邊切方式。也許在該階段擁有非最小超邊切數量的劃分算法在經過遷移優化后得到原超圖的最優劃分。因此，這里不僅只選擇在此階段的一個最優的劃分方式，而是選擇多個在此階段劃分結果較好的幾種方式。但是，同時計算多種方式會大大增加該框架的運行時間。

在實驗開始時先隨機生成10種不同的初始劃分，并且淘汰掉那些超邊切數量多于最小超邊切數量10%的初始劃分。這樣就過濾掉那些確實比較差的劃分方式，并且減少在遷移優化階段的運行總時間。

2.2.3遷移優化階段算法

（1）KL算法

Kernighan和Lin提出了組遷移算法[4]思想，并設計了KL算法。該算法是將一個網絡節點圖分割成兩個相等的節點集合，使得連接兩個集合的邊權最小。該算法是基于無向二分圖劃分的第一個有效的啟發式算法，以后的圖劃分算法大多數是對KL算法進行的改進。

KL算法從一個等分的初始劃分入手，通過兩個劃分中的結點互換減少邊割線的數目，比較遷移前后的增益，循環此步驟，直到沒有任何改進為止。在遷移過程中的增益（gain）可以被定義為：

其中函數P(j)返回一個頂點j的當前部分。

（2）FM算法

Fiduccia和Mattheyses[14]提出了著名的FM算法，該算法是對KL算法的一次較大的改進。在該算法中，主要引入了單元的增益值和面積的約束函數。該算法也是首先產生一個初始劃分，然后進行頂點遷移，并且每次遷移以單元的形式從一個子集遷移到另一個子集當中，而且元件的移動要考慮是否滿足約束函數，是否降低了域的解空間。雖然FM算法速度很快（為線性時間復雜度），但是FM算法很容易陷入局部最優[15]。

FM算法的主要思想是每次將割線一側的頂點遷移到割線的另一側。交換的標準為：

①該頂點交換以后，圖的負載平衡性改進為最大，即使此改進是負的。

②如果頂點交換以后圖的負載改進不變，則選擇交換以后能夠使圖的割邊權最小的頂點。

將負載平衡作為第一標準是因為FM算法不像KL算法那樣，每次交換一個頂點對卻不會有交換后負載差異變大的情況。

因此，FM算法的時間復雜度為O(P)，其中P為電路線網端點（PIN）的數目。對于大多數圖來說，這是一個相當不錯的改進。因為只有完全圖的邊數才能達到O(|V2|)，其中||V 為頂點數，所以O(P)<< O(|V|2)。但是實際上，每次交換完畢一個頂點以后，更新頂點增益權值，仍然需要O(|V|)，因此實際上FM算法仍然有相當大的改進空間。

（3）EEFM算法

EEFM算法（early-exit FM）是基于FM的一種算法，該算法是在每次進行FM算法循環之前先判斷該劃分是否能相對地提高增益值。如果是在超圖頂點較小的情況下，并且該劃分并不能很好地提高增益，FM算法便直接退出循環。

3　hMetis框架算法的分析與改進

3.1粗化階段算法分析與改進

研究發現，在上文所述的3種粗化算法中有一些算法存在一些潛在的問題，本文將針對上述算法進行潛在問題分析，并對其做出適當的改進。

在EC算法中，無論是圖的粗化還是超圖的粗化，都會導致一個潛在的問題。這個問題就是EC方案著力于尋找一個最小超邊切的粗化方式，而并不是去尋找一種最好的粗化方式。當超圖中原來就存在一種較好的圖的劃分，但是如果是基于EC算法，直接尋找最大權值的頂點并且合并，將會破壞原來較好的劃分，從而增加了遷移優化階段的難度。在原圖中存在一個較好的劃分，而兩個子圖只被一個超邊所連接。如果基于EC算法，會發現原超圖的一個較好的劃分被破壞。這將導致在隨后的遷移優化階段已合并后的EF頂點不論如何遷移，都不能減少超邊切數量。

類似的情況在HEC算法中也存在，因此需要尋找一種較好的方法來提高粗化階段的性能。

（1）First Choice（FC）

FC粗化算法基于上文所述的EC算法，與之不同的是FC算法降低了EC算法中的要求。在EC算法中，頂點只能與未被匹配的其他頂點進行匹配，而這會導致上述對較好原圖劃分的破壞。因此，在FC算法中，對于任意的頂點v，所有的頂點（被匹配的和未被匹配的頂點）將會被加入到v的待匹配序列，在此序列中可以尋找一個權值最大的頂點來和v進行匹配并合并。如果該頂點原先已經被匹配，本文會計算兩種不同匹配方案的增益，并且選取更有利于遷移優化的方案進行合并。該算法的偽代碼如圖4所示。

（2）Hybrid-First Choice（HFC）

該算法是基于FC算法的一種改進算法，由于FC算法是為了防止EC算法中打破原超圖中天然的劃分，而EC算法是一種基于貪心的算法，從而FC算法防止了頂點的貪心合并，在超邊切的數量上會有所增加。

因此，本文將貪心算法和對EC算法改進后的FC算法進行組合，從而得到HFC算法。在此算法中，頂點的合并沿著最快地減小超邊數量的方向進行。

Fig.4　FC algorithm圖4FC算法

3.2遷移優化階段算法分析與改進（1-way FM）

從上文FM算法的分析可以得出，算法在每次交換完畢一個頂點以后，都需要更新一次頂點的增益權值，因此該算法的復雜度仍然需要O(|V|)，從而FM算法仍然有相當大的改進空間。

前面提到的KL和FM算法能在遷移優化階段得到很好的二分優化，但是這僅僅是二分子圖中的最優的劃分方案。而往往局部的最優并不代表是原超圖的最優劃分，于是盡量避免使遷移優化過程陷入局部最優就成為關鍵問題。

在1-way FM算法中，規定在每一次循環中，頂點的遷移只能沿同一個方向進行。顯然，這樣的策略能夠有效地跳出局部最優。

4　實驗結果與分析

4.1測試用例

本文實驗中所使用的6個測試用例，以及它們的屬性值如表1所示。該測試用例采用的是傳統的MCNC用例，面積被擴展來獲得一個大約1 cm×1 cm的平均尺寸，采用與參考文獻[3]相同的參數配置，以此為基準計算通信量和模塊間的初始連接與用例布局。

Table 1　Property values used in test cases表1　使用的測試用例的屬性值

本文將使用三維片上網絡的吞吐量和該片上網絡所運行的時間來衡量該片上網絡的性能。吞吐量的計算主要關注的是每個結點到其他結點獲得的網絡吞吐量的值，以及整個網絡的平均吞吐量。

4.2粗化階段算法對性能的影響

本文將粗化階段的算法EC和HEC與改進后的算法FC和HEC進行比較，所比較的性能標準為該三維片上網絡的運行時間和網絡吞吐量。

由圖5可見，對于不同的測試用例，該算法所運行的時間差別非常大。其中ami49在不同的粗化算法下差別較大，而xerox隨著粗化算法的不同變化幅度較小。

Fig.5　Comparison of runtime with different coarsening algorithms for 3D NoCs圖5　不同粗化算法在片上網絡的運行時間

原始的HEC算法所使用的時間在大多數情況下（除了xerox）比原始的EC算法所使用的時間多。而經過改進的FC算法在IP單元片數較大或者較小的時候能夠得到一個較好的劃分。而基于FC算法進行改進的HFC算法能在各種環境下得到一個較好的劃分，并且能夠大幅度地減少所使用的時間。例如在ami49中，IP單元片的數量為49，而HFC算法能夠很好地處理該超大規模集成芯片。

可以很容易地觀察到在運行時間的效率上FC算法和基于FC算法的改進算法HFC要優于原有的兩種粗化算法。

另一個衡量算法性能的重要指標為該芯片的吞吐量。在本文實驗中將選取3個最優的劃分進行吞吐量的計算，并且統計該3個劃分的平均吞吐量，具體數值如圖6所示。

Fig.6　Comparison of throughput with differentcoarsening algorithms for 3D NoCs圖6 不同粗化算法的3D NoC吞吐量

從圖6中可以看出，各個算法在xerox用例中的吞吐量都較小，而在apte上的吞吐量相對較大，對于ami25，相比于EC算法，改進的FC算法反而降低了網絡的吞吐量，但隨著IP單元片數目的遞增，FC算法比EC算法的吞吐量更大。

然而，相比于HEC算法，EC和FC算法在對于網絡吞吐量上性能大大優于HEC算法，在各個數據集上的吞吐量都高于HEC算法。而FC相對于EC算法在網絡吞吐量上得到了更大的提升。綜上所述可以得出，針對網絡平均吞吐量經過優化后的粗化算法FC要略微優于EC算法，并且相對于HEC算法有較大的提升。

基于FC算法的HEC算法比原FC算法有著更好的劃分。在吞吐量上也比上述3種粗化算法更加高效。

4.3遷移優化階段算法對性能的影響

本節將基于不同遷移優化階段的算法對片上網絡的運行時間和吞吐量進行比較分析。

表2的結果表明，在片上網絡的運行時間方面，基于跳出局部最優的1-way FM算法相對于EEFM算法有較大的改進，而相對于FM算法只有較少的提升。對于IP單元片數目較少的集成網絡，1-way FM算法相對于其他兩種算法，所提升的性能并不是太大，但是一旦所處理的集成網絡規模巨大，可以看到基于1-way FM算法的網絡能夠大大地減少片上網絡所運行的時間。

Table 2　Impact of different migration optimization algorithms for 3D NoCs表2　不同遷移優化算法在片上網絡的影響

在片上網絡的吞吐量方面，可以得出和上述運行時間相同的結論，即1-way FM算法相對于EEFM算法有著較好的性能提升，而相對于FM算法，提升的幅度并不大。然而可以發現，一旦所處理的網絡規模變得十分巨大，基于EEFM算法的片上網絡的吞吐量變得十分小。因此可以得出結論，EEFM算法并不能夠很好地處理巨大規模的片上網絡。相反，1-way FM算法能夠在較大規模集成網絡上保持較好的性能。但也需要注意的是1-way FM算法的高性能是以增加算法復雜度為代價的。

4.4hMetis算法框架對性能的影響

根據表3、表4得出若干結論：在時間性能方面，對于不同的測試數據集可以得到不同的hMetis算法框架來對該數據集進行劃分，所得到的最優劃分如表中所示。例如對于apte這個數據集，可以在粗化階段使用HEC粗化算法對其進行粗化，并且在遷移優化階段使用FM算法來進行優化，從而能得出該電路較好的hMetis算法框架。而該電路的最優劃分所需要的時間為43.07 s（參見表3），而具有較好性能的算法框架為HFC+1-way FM。

Table 3　Comparison of CPU time with different algorithms used at different phases表3　不同階段不同算法所使用的CPU時間　s

Table 4　Comparison of network throughput with different algorithms used at different phases表4　不同階段不同算法網絡的吞吐量大小　Kb/s

與上述時間性能方面的計算方式相同，在對吞吐量進行評估比較時，對于不同的數據集，也會有相應的最優劃分來得到一個較大吞吐量的劃分框架（參見表4）。例如apte數據集的最大吞吐量為56.13 Kb/s，所得到的較優hMetis框架算法為EC+1-way FM。

5　結束語

本文研究了針對異構三維片上網絡設計的一種超圖劃分框架，并且對現有的超圖劃分中每一步驟中算法進行分析與改進。在粗化階段，提出常見的粗化算法的不足之處，并且對其進行修改，提高片上網絡的性能；在遷移優化階段，對FM算法進行改進，并且對不同的細化算法進行比較分析。最后將不同的粗化細化算法進行實驗比較分析，得出一個較好的基于hMetis的算法框架。然后將得到的較好的hMetis框架算法應用到異構三維片上網絡中，分析該算法的性能效果，并且使用運行時間和網絡吞吐量的性能指標來衡量利用該算法框架設計的三維片網性能的優劣。

由于本文使用的細化階段算法為1982年Fiduccia和Mattheyses提出的FM算法，經過三十多年，雖然該領域內提出了許多圖劃分的算法，但基本上都以此算法為基礎而進行的改進。因此，尋找一種更好的劃分來提高片上網絡的性能將是下一步的工作。另外，由于本文所研究的片上網絡性能指標只有網絡的運行時間和吞吐量，但真正的片上網絡受許多因素的影響，下一步還可以用其他更多的影響因素來衡量算法的優劣。

References:

[1]Lu Yue,Cao Jianwen.Multilevel hypergraph partitioning and multi-phase refinement[J].Computer Engineering and Design,2009,30(4):800-802.

[2]de Paulo V,Ababei C.A framework for 2.5D NoC exploration using homogeneous networks over heterogeneous floorplans[C]//Proceedings of the 2009 International Conference on Reconfigurable Computing and FPGAs,Cancun,Mexico, 2009.Washington,USA:IEEE Computer Society,2009: 267-272.

[3]de Paulo V,Ababei C.3D network-on-chip architectures using homogeneous meshes and heterogeneous floorplans[J].International Journal of Reconfigurable Computing,2010(1):1.

[4]Kernighan B W,Lin S.An efficient heuristic procedure for partitioning graphs[J].The Bell System Technical Journal, 1970,49(2):291-307.

[5]Fiduccia C M,Mattheyses R M.A linear-time heuristic for improving network partitions[C]//Proceedings of the 19th IEEE Conference on Design Automation,Las Vegas,USA, Jun 14-16,1982.Piscataway,USA:IEEE,1982:175-181.

[6]Karypis G,Kumar V.METIS 3.0:unstructured graph partitioning and sparse matrix ordering system,Technical report 97-061[R].1997.

[7]Karypis G,Kumar V.A fast and highly quality multilevel scheme for partitioning irregular graph[J].SIAM Journal on Scientific Computing,1998,20(1):359-392.

[8]Karypis G,Kumar V.Multilevel k-way hypergraph partitioning[C]//Proceedings of the 36th Annual ACM/IEEE Design Automation Conference,New Orleans,USA,1999. New York,USA:ACM,1999:343-348.

[9]Wang Miao,Tang Yuhua.Design and implementation of parallel graph-partitioning and hypergraph-partitioning methods for OpenFOAM[D].Changsha:National University of Defense Technology,2012.

[10]Karypis G,Aggarwal R,Kumar V,et al.Multilevel hypergraph partitioning:applications in VLSI domain[J].IEEE Transactions on Very Large Scale Integration Systems, 1999,7(1):69-79.

[11]Karypis G,Kumar V.Analysis of multilevel graph partitioning [C]//Proceedings of the 1995 IEEE/ACM SC95 Conference on Supercomputing,San Diego,USA,Dec 4-8,1995.Piscataway,USA:IEEE,1995:29.

[12]Cai Wenzan,Young E F Y.A fast hypergraph bipartitioning algorithm[C]//Proceedings of the 2014 IEEE Computer Society Annual Symposium on VLSI,Tampa,USA,Jul 9-11, 2014.Piscataway,USA:IEEE,2014:607-612.

[13]Zhao Zhizi,Tao Lixin,Zhao Yongchang.An effective algorithm for multiway hypergraph partitioning[J].IEEE Transactions on Circuits and Systems I:Fundamental Theory and Applications,2002,49(8):1079-1092.

[14]Flajolet P,Martin G N.Probabilistic counting algorithm for data base applications[J].Journal of Computer and System Sciences,1985,31(2):182-209.

[15]Huang Yuchi,Liu Qingshan,Lv Fengjun,et al.Unsupervised image categorization by hypergraph partition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(6):1266-1273.

附中文參考文獻:

[1]盧玥,曹建文.超圖多級劃分算法框架及對劃分結果的多階段優化[J].計算機工程與設計,2009,30(4):800-802.

[9]汪淼,唐玉華.面向OpenFOAM的并行圖劃分與超圖劃分方法設計與實現[D].長沙:國防科技大學,2012.

SONG Guozhi was born in 1977.He received the Ph.D.degree in electronic engineering from Queen Mary University of London in 2009.Now he is an associate professor and M.S.supervisor at Tianjin Polytechnic University.His research interests include 3D network-on-chip,heterogeneous wireless network integration and wireless sensor networks,etc.

宋國治（1977—），男，黑龍江哈爾濱人，2009年于英國倫敦大學瑪麗王后學院電子工程專業獲得博士學位，現為天津工業大學副教授、碩士生導師，主要研究領域為三維片上網絡，異構無線網絡整合，無線傳感器網絡等。發表學術論文40余篇，獲發明專利6項，軟件著作權1項，主持或參加過多項國家自然科學基金、國家科技支撐計劃及天津市教委項目等。

ZHANG Dakun was born in 1960.She received the Ph.D.degree in computer application from Northeastern University in 2004.Now she is a professor and M.S.supervisor at Tianjin Polytechnic University.Her research interests include 3D network-on-chip,combinational algorithm and virtual reality technology,etc.

張大坤（1960—），女，遼寧阜新人，2004年于東北大學計算機應用專業獲得博士學位，現為天津工業大學計算機科學與軟件學院教授、碩士生導師，主要研究領域為三維片上網絡，組合算法設計，虛擬現實技術等。發表學術論文30余篇，主持并承擔過多項國家自然科學基金、國家863計劃及省部級課題。

MA Jiechao was born in 1991.He is a postgraduate student at Sun Yat-Sen University.His research interests include 3D network-on-chip and hyper-graph partition,etc.

馬杰超（1991—），男，浙江寧波人，中山大學碩士研究生，主要研究領域為三維片上網絡，超圖劃分等。

TU Yao was born in 1992.He is a postgraduate student at School of Computer Science and Software Engineering, Tianjin Polytechnic University.His research interest is 3D network-on-chip floorplanning.

涂遙（1992—），男，安徽淮南人，天津工業大學計算機科學與軟件學院碩士研究生，主要研究領域為三維片上網絡布局規劃問題。

LIU Chang was born in 1994.She is a student at School of Computer Science and Software Engineering,Tianjin Polytechnic University.Her research interest is 3D network-on-chip floorplanning.

劉暢（1994—），女，黑龍江大慶人，天津工業大學計算機科學與軟件學院學生，主要研究領域為片上網絡的布局劃分。

*The National Natural Science Foundation of China under Grant No.61272006(國家自然科學基金);the National Training Program of Innovation and Entrepreneurship for Undergraduates under Grant No.201510058050(國家級大學生創新創業訓練計劃項目).

Received 2015-06,Accepted 2015-08.

CNKI網絡優先出版:2015-08-12,http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1652.010.html

+Corresponding author:E-mail:guozhi.song@gmail.com

文獻標志碼：A

中圖分類號：TP393.0

doi:10.3778/j.issn.1673-9418.1507041

Hyper-Graph PartitionAlgorithms for Heterogeneous 3D Network-on-Chip Floorplanning Optimization?

SONG Guozhi+,ZHANG Dakun,MAJiechao,TU Yao,LIU Chang
School of Computer Science&Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China

Abstract:Network-on-chip(NoC)is a feasible technology with a large number of embedded cores integrated into a single wafer.Compared with the traditional system-on-chip,it can better meet the challenges of the future need for more large-scale integration of the kernel,resulting in a wider range of applications.However,most of the research is based on homogeneous architecture assuming that all the tiles have the same area.But this assumption is not realistic. Therefore,the research on heterogeneous 3D NoCs is very necessary.With heterogeneous 3D NoCs,a reasonable division of network elements has a significant impact on the performance of heterogeneous 3D NoCs.This paper firstly describes the floorplanning based on 3D NoC of heterogeneous network architecture,and maps VLSI(very large scale integration)into a hyper-graph,then divides the hyper-graph into multi-levels.Secondly,this paper introduces varivarious of common algorithms in the different phases,analyzes the potential problems of the algorithms,and puts forward several new algorithms to improve the performance of NoC.Finally,a number of simulation experiments are conducted based on a few conventional VLSI data sets to compare the performance of the different phases with different algorithms and choose the best hMetis algorithm framework on the data sets.

Key words:3D network-on-chip;heterogeneous floorplanning;hyper-graph partition;hMetis