異構(gòu)三維片上網(wǎng)絡(luò)布局優(yōu)化的超圖劃分算法*

宋國(guó)治，張大坤，馬杰超，涂　遙，劉　暢天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387

?

異構(gòu)三維片上網(wǎng)絡(luò)布局優(yōu)化的超圖劃分算法*

宋國(guó)治+，張大坤，馬杰超，涂遙，劉暢
天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 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.

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

關(guān)鍵詞：三維片上網(wǎng)絡(luò)；異構(gòu)布局；超圖劃分；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　引言

隨著芯片制造業(yè)的迅速發(fā)展，芯片規(guī)模日益擴(kuò)大，原有的總線(xiàn)結(jié)構(gòu)和點(diǎn)到點(diǎn)的互連已經(jīng)不能滿(mǎn)足通信的需求。因此，片上網(wǎng)絡(luò)應(yīng)運(yùn)而生。

由于片上網(wǎng)絡(luò)本身的規(guī)模十分龐大，并且受到現(xiàn)有計(jì)算機(jī)計(jì)算能力的限制，需要將網(wǎng)絡(luò)上原有的單元進(jìn)行重新劃分布局，來(lái)提高該片上網(wǎng)絡(luò)的性能。超圖具有的一些特征可以用來(lái)表示一些非規(guī)則問(wèn)題中的結(jié)構(gòu)，例如分布式數(shù)據(jù)庫(kù)中的數(shù)據(jù)相關(guān)性，超大規(guī)模集成電路（very large scale integration，VLSI）中元件的連通性[1]等。超圖能夠很好地反映超大規(guī)模集成元件的劃分布局。

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

Fig.1　3D NoC with heterogeneous floorplan圖1　基于異構(gòu)布局的三維片上網(wǎng)絡(luò)

在過(guò)去的幾十年間，已經(jīng)有許多國(guó)內(nèi)外該領(lǐng)域的相關(guān)學(xué)者對(duì)圖的劃分問(wèn)題開(kāi)展了廣泛深入的研究，特別是超圖劃分算法的研究已引起越來(lái)越多業(yè)界人士的關(guān)注。早在20世紀(jì)70年代美國(guó)的普林斯頓大學(xué)的Kernighan和Lin就提出了組遷移（group migration）算法的思想[4]，并設(shè)計(jì)了經(jīng)典的KL算法。該算法的主要思想是將一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)圖分割成兩個(gè)相等的節(jié)點(diǎn)集合，使得連接兩個(gè)集合的邊權(quán)最小。KL算法是基于無(wú)向二分圖劃分的第一個(gè)有效的啟發(fā)式算法。

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

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

本文將片上網(wǎng)絡(luò)中的單元映射成超圖，介紹了基于超圖劃分的多級(jí)劃分算法框架，對(duì)這些常用的劃分算法進(jìn)行了分析改進(jìn)，并且將其運(yùn)用到片上網(wǎng)絡(luò)的設(shè)計(jì)中，以提高片上網(wǎng)絡(luò)的性能。在得到一個(gè)劃分完的二分超圖后，將兩個(gè)子圖分別進(jìn)行合理的分配，以求得到較好的網(wǎng)絡(luò)性能。在實(shí)驗(yàn)中采用了模擬退火算法來(lái)對(duì)該子圖進(jìn)行合理的布局。而片上網(wǎng)絡(luò)的吞吐量和網(wǎng)絡(luò)的運(yùn)行時(shí)間被用作衡量整個(gè)算法框架的標(biāo)準(zhǔn)。

2　超圖多級(jí)劃分的基本框架

2.1超圖的基本概念

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

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

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

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

定義2（超邊切）對(duì)于超邊e，如果其所包含的頂點(diǎn)存在于其他不同的超邊之中，稱(chēng)該超邊為其他超邊的超邊切[11]。

在將超圖進(jìn)行切割時(shí)，每一條超邊看作一個(gè)子圖，其中子圖中每?jī)蓚€(gè)定點(diǎn)都是相互連接的，連接的權(quán)值為超邊的權(quán)重比上超邊的勢(shì)（cardinality）。所謂勢(shì)，是指該超邊所包含的頂點(diǎn)的個(gè)數(shù)。該子圖被切割為H1和H2。超圖的超邊切可定義為：

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

Fig.2　Mapping of devices on 3D network-on-chip圖2　三維片上網(wǎng)絡(luò)中元件的映射

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

2.2hMetis算法框架

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

hMetis劃分算法框架可分為3個(gè)階段，粗化階段，初始劃分階段，遷移優(yōu)化階段，如圖3所示[9]。在粗化階段，將某些超圖的節(jié)點(diǎn)結(jié)合在一起，得到下一級(jí)粗化超圖，重復(fù)此過(guò)程直到粗化超圖足夠小為止，即得到一個(gè)最小的超圖。在初始劃分階段，對(duì)該最小超圖進(jìn)行對(duì)分，得到一個(gè)初始劃分。因?yàn)樵S多超圖劃分算法在超圖比較大的情況下得不到較好的劃分性能，所以在最后的遷移優(yōu)化階段，將劃分從最小的超圖投影回原始的超圖，在每一水平層的粗化超圖中，對(duì)劃分進(jìn)行遷移優(yōu)化。

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

本文2.2.1小節(jié)介紹粗化階段所使用的粗化算法，2.2.2小節(jié)介紹初始劃分階段的具體實(shí)現(xiàn)，2.2.3小節(jié)介紹遷移優(yōu)化的相關(guān)算法。

2.2.1粗化階段算法

在粗化階段，超圖中的一系列頂點(diǎn)被合并成一個(gè)頂點(diǎn)，生成一系列的逐漸變小的超圖，而這些粗化后的超圖的性能不會(huì)明顯比原圖差。因?yàn)閷⒃瑘D進(jìn)行多級(jí)劃分的目的是為了能在遷移優(yōu)化階段得到一種更好的超圖劃分?；贙L-FM等系列的啟發(fā)式算法能在較小的超圖中發(fā)揮較好的性能，但是隨著超圖的頂點(diǎn)數(shù)和邊數(shù)的增大，這些啟發(fā)式優(yōu)化算法將不再適用。

本文將介紹3種常見(jiàn)的粗化階段頂點(diǎn)不同的合并算法。（1）邊粗化（edge coarsening，EC）選擇在同一超邊內(nèi)的兩個(gè)頂點(diǎn)，將它們合并成一個(gè)頂點(diǎn)。（2）超邊粗化（hyperedge coarsening，HEC）將屬于同一個(gè)超邊中所有獨(dú)立的頂點(diǎn)合并成一個(gè)頂點(diǎn)。（3）改進(jìn)超邊粗化（modified hyperedge coarsening，MHEC）是基于第二種方法的優(yōu)化，因?yàn)橐坏⒊瑘D中的所有頂點(diǎn)合并后，和該超邊相關(guān)但是沒(méi)有被合并的頂點(diǎn)與合并后的頂點(diǎn)在權(quán)值上會(huì)有很大的差異，這將會(huì)降低超圖的劃分效率。為了在優(yōu)化階段得到更好的劃分，可以將超圖中未被合并的那一部分頂點(diǎn)進(jìn)行合并。該3種算法的具體合并方式如下。

（1）邊粗化

在邊粗化方案中，各個(gè)頂點(diǎn)被隨機(jī)地訪(fǎng)問(wèn)，對(duì)于任意一個(gè)頂點(diǎn)v，所有和v屬于同一個(gè)超邊并且尚未被其他頂點(diǎn)匹配的頂點(diǎn)將在v的匹配序列之內(nèi)，在此序列中，可以將計(jì)算出的能與v匹配合并后得到最大權(quán)值的頂點(diǎn)進(jìn)行匹配合并，而合并后所得到的權(quán)值為兩個(gè)頂點(diǎn)的權(quán)值之和。合并后超邊的權(quán)值為：

其中，e為超邊所表示的勢(shì)的大小。

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

（2）超邊粗化

盡管邊粗化方案能夠逐漸地生成可以很好地?fù)碛性瑘D特征的許多更小的超圖，但是該方案每次粗化只能合并兩個(gè)匹配的頂點(diǎn)，該過(guò)程需要粗化許多次才能得到一個(gè)較小的超圖。因此，該方案并不能很快地得到足夠小的超圖。

在超邊粗化方案中是將屬于同一個(gè)超邊中的所有頂點(diǎn)合并為一個(gè)頂點(diǎn)。具體的實(shí)現(xiàn)方式如下：該方案將超邊以權(quán)重的非遞增順序排列并依次訪(fǎng)問(wèn)，當(dāng)遇到超邊的權(quán)重相同時(shí)，以超邊大小的非遞減順序訪(fǎng)問(wèn)。按照此訪(fǎng)問(wèn)順序，對(duì)于每一個(gè)超邊中還未被匹配的所有頂點(diǎn)，將此頂點(diǎn)集進(jìn)行合并。因此，該方案優(yōu)先選擇那些具有較大權(quán)值和較小大小的超邊。最后，直到所有的超邊完全被訪(fǎng)問(wèn)，然后可以將這些被匹配完并且合并后的頂點(diǎn)作為下一級(jí)將被粗化的超圖。而那些未被合并的頂點(diǎn)將會(huì)簡(jiǎn)單地被復(fù)制到下一級(jí)被粗化的超圖。

（3）改進(jìn)超邊粗化

超邊粗化算法能夠顯著地減小超邊的權(quán)重，然而在每個(gè)粗化階段，大多數(shù)超邊并沒(méi)有被合并，因?yàn)閷儆谒鼈兊捻旤c(diǎn)已經(jīng)由其他的超邊進(jìn)行了合并。這導(dǎo)致了兩個(gè)問(wèn)題：第一，超邊的大小減小得并不充分，使得基于FM-KL系列算法的遷移優(yōu)化階段變得困難。第二，頂點(diǎn)的權(quán)重（即已被合并的頂點(diǎn)的權(quán)重）被粗化的程度顯著不同，導(dǎo)致超圖形狀的扭曲。

為了解決這一問(wèn)題，可以在進(jìn)行完HEC方案后，重新按照序列中的訪(fǎng)問(wèn)次序訪(fǎng)問(wèn)超邊，并且對(duì)那些沒(méi)有被合并的頂點(diǎn)進(jìn)行合并。

2.2.2初始劃分階段算法

經(jīng)過(guò)粗化階段以后，會(huì)得到一個(gè)足夠小的超圖，通常來(lái)說(shuō)頂點(diǎn)數(shù)|V|<100為一個(gè)比較合適的標(biāo)準(zhǔn)值。而在初始劃分階段，通常進(jìn)行二分法，即使用一條線(xiàn)將超圖分割為兩個(gè)部分。在初始劃分中考慮負(fù)載的平衡和頂點(diǎn)之間的通信。

在后面實(shí)驗(yàn)部分所使用的是一種較為簡(jiǎn)單并且效果比較好的劃分算法。其主要思想是任意選取一個(gè)頂點(diǎn)，并由該頂點(diǎn)開(kāi)始，依據(jù)圖的連通性，逐漸地生長(zhǎng)，直到生長(zhǎng)出來(lái)半數(shù)原圖的頂點(diǎn)。

具體的算法描述如下：

步驟1任意選取超圖的一個(gè)頂點(diǎn)，記為0。

步驟2按照廣度優(yōu)先遍歷方式，從頂點(diǎn)0開(kāi)始遍歷圖，與頂點(diǎn)0相鄰的頂點(diǎn)均記為1；循環(huán)此過(guò)程，與頂點(diǎn)i相鄰的頂點(diǎn)均記為i+1。

步驟3當(dāng)所有訪(fǎng)問(wèn)過(guò)的頂點(diǎn)數(shù)目等于頂點(diǎn)總數(shù)的一半的時(shí)候，算法結(jié)束。

然而，該算法所得出的二分圖并不是最優(yōu)解，下面將從兩個(gè)角度出發(fā)，考慮對(duì)其進(jìn)行優(yōu)化。

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

第二，在初始劃分階段所得到的擁有最小超邊切的劃分方式，在經(jīng)過(guò)遷移優(yōu)化階段投射為原超圖后，也許并不是原超圖所擁有的最小超邊切方式。也許在該階段擁有非最小超邊切數(shù)量的劃分算法在經(jīng)過(guò)遷移優(yōu)化后得到原超圖的最優(yōu)劃分。因此，這里不僅只選擇在此階段的一個(gè)最優(yōu)的劃分方式，而是選擇多個(gè)在此階段劃分結(jié)果較好的幾種方式。但是，同時(shí)計(jì)算多種方式會(huì)大大增加該框架的運(yùn)行時(shí)間。

在實(shí)驗(yàn)開(kāi)始時(shí)先隨機(jī)生成10種不同的初始劃分，并且淘汰掉那些超邊切數(shù)量多于最小超邊切數(shù)量10%的初始劃分。這樣就過(guò)濾掉那些確實(shí)比較差的劃分方式，并且減少在遷移優(yōu)化階段的運(yùn)行總時(shí)間。

2.2.3遷移優(yōu)化階段算法

（1）KL算法

Kernighan和Lin提出了組遷移算法[4]思想，并設(shè)計(jì)了KL算法。該算法是將一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)圖分割成兩個(gè)相等的節(jié)點(diǎn)集合，使得連接兩個(gè)集合的邊權(quán)最小。該算法是基于無(wú)向二分圖劃分的第一個(gè)有效的啟發(fā)式算法，以后的圖劃分算法大多數(shù)是對(duì)KL算法進(jìn)行的改進(jìn)。

KL算法從一個(gè)等分的初始劃分入手，通過(guò)兩個(gè)劃分中的結(jié)點(diǎn)互換減少邊割線(xiàn)的數(shù)目，比較遷移前后的增益，循環(huán)此步驟，直到?jīng)]有任何改進(jìn)為止。在遷移過(guò)程中的增益（gain）可以被定義為：

其中函數(shù)P(j)返回一個(gè)頂點(diǎn)j的當(dāng)前部分。

（2）FM算法

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

FM算法的主要思想是每次將割線(xiàn)一側(cè)的頂點(diǎn)遷移到割線(xiàn)的另一側(cè)。交換的標(biāo)準(zhǔn)為：

①該頂點(diǎn)交換以后，圖的負(fù)載平衡性改進(jìn)為最大，即使此改進(jìn)是負(fù)的。

②如果頂點(diǎn)交換以后圖的負(fù)載改進(jìn)不變，則選擇交換以后能夠使圖的割邊權(quán)最小的頂點(diǎn)。

將負(fù)載平衡作為第一標(biāo)準(zhǔn)是因?yàn)镕M算法不像KL算法那樣，每次交換一個(gè)頂點(diǎn)對(duì)卻不會(huì)有交換后負(fù)載差異變大的情況。

因此，F(xiàn)M算法的時(shí)間復(fù)雜度為O(P)，其中P為電路線(xiàn)網(wǎng)端點(diǎn)（PIN）的數(shù)目。對(duì)于大多數(shù)圖來(lái)說(shuō)，這是一個(gè)相當(dāng)不錯(cuò)的改進(jìn)。因?yàn)橹挥型耆珗D的邊數(shù)才能達(dá)到O(|V2|)，其中||V 為頂點(diǎn)數(shù)，所以O(shè)(P)<< O(|V|2)。但是實(shí)際上，每次交換完畢一個(gè)頂點(diǎn)以后，更新頂點(diǎn)增益權(quán)值，仍然需要O(|V|)，因此實(shí)際上FM算法仍然有相當(dāng)大的改進(jìn)空間。

（3）EEFM算法

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

3　hMetis框架算法的分析與改進(jìn)

3.1粗化階段算法分析與改進(jìn)

研究發(fā)現(xiàn)，在上文所述的3種粗化算法中有一些算法存在一些潛在的問(wèn)題，本文將針對(duì)上述算法進(jìn)行潛在問(wèn)題分析，并對(duì)其做出適當(dāng)?shù)母倪M(jìn)。

在EC算法中，無(wú)論是圖的粗化還是超圖的粗化，都會(huì)導(dǎo)致一個(gè)潛在的問(wèn)題。這個(gè)問(wèn)題就是EC方案著力于尋找一個(gè)最小超邊切的粗化方式，而并不是去尋找一種最好的粗化方式。當(dāng)超圖中原來(lái)就存在一種較好的圖的劃分，但是如果是基于EC算法，直接尋找最大權(quán)值的頂點(diǎn)并且合并，將會(huì)破壞原來(lái)較好的劃分，從而增加了遷移優(yōu)化階段的難度。在原圖中存在一個(gè)較好的劃分，而兩個(gè)子圖只被一個(gè)超邊所連接。如果基于EC算法，會(huì)發(fā)現(xiàn)原超圖的一個(gè)較好的劃分被破壞。這將導(dǎo)致在隨后的遷移優(yōu)化階段已合并后的EF頂點(diǎn)不論如何遷移，都不能減少超邊切數(shù)量。

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

（1）First Choice（FC）

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

（2）Hybrid-First Choice（HFC）

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

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

Fig.4　FC algorithm圖4FC算法

3.2遷移優(yōu)化階段算法分析與改進(jìn)（1-way FM）

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

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

在1-way FM算法中，規(guī)定在每一次循環(huán)中，頂點(diǎn)的遷移只能沿同一個(gè)方向進(jìn)行。顯然，這樣的策略能夠有效地跳出局部最優(yōu)。

4　實(shí)驗(yàn)結(jié)果與分析

4.1測(cè)試用例

本文實(shí)驗(yàn)中所使用的6個(gè)測(cè)試用例，以及它們的屬性值如表1所示。該測(cè)試用例采用的是傳統(tǒng)的MCNC用例，面積被擴(kuò)展來(lái)獲得一個(gè)大約1 cm×1 cm的平均尺寸，采用與參考文獻(xiàn)[3]相同的參數(shù)配置，以此為基準(zhǔn)計(jì)算通信量和模塊間的初始連接與用例布局。

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

本文將使用三維片上網(wǎng)絡(luò)的吞吐量和該片上網(wǎng)絡(luò)所運(yùn)行的時(shí)間來(lái)衡量該片上網(wǎng)絡(luò)的性能。吞吐量的計(jì)算主要關(guān)注的是每個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)獲得的網(wǎng)絡(luò)吞吐量的值，以及整個(gè)網(wǎng)絡(luò)的平均吞吐量。

4.2粗化階段算法對(duì)性能的影響

本文將粗化階段的算法EC和HEC與改進(jìn)后的算法FC和HEC進(jìn)行比較，所比較的性能標(biāo)準(zhǔn)為該三維片上網(wǎng)絡(luò)的運(yùn)行時(shí)間和網(wǎng)絡(luò)吞吐量。

由圖5可見(jiàn)，對(duì)于不同的測(cè)試用例，該算法所運(yùn)行的時(shí)間差別非常大。其中ami49在不同的粗化算法下差別較大，而xerox隨著粗化算法的不同變化幅度較小。

Fig.5　Comparison of runtime with different coarsening algorithms for 3D NoCs圖5　不同粗化算法在片上網(wǎng)絡(luò)的運(yùn)行時(shí)間

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

可以很容易地觀(guān)察到在運(yùn)行時(shí)間的效率上FC算法和基于FC算法的改進(jìn)算法HFC要優(yōu)于原有的兩種粗化算法。

另一個(gè)衡量算法性能的重要指標(biāo)為該芯片的吞吐量。在本文實(shí)驗(yàn)中將選取3個(gè)最優(yōu)的劃分進(jìn)行吞吐量的計(jì)算，并且統(tǒng)計(jì)該3個(gè)劃分的平均吞吐量，具體數(shù)值如圖6所示。

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

從圖6中可以看出，各個(gè)算法在xerox用例中的吞吐量都較小，而在apte上的吞吐量相對(duì)較大，對(duì)于ami25，相比于EC算法，改進(jìn)的FC算法反而降低了網(wǎng)絡(luò)的吞吐量，但隨著IP單元片數(shù)目的遞增，F(xiàn)C算法比EC算法的吞吐量更大。

然而，相比于HEC算法，EC和FC算法在對(duì)于網(wǎng)絡(luò)吞吐量上性能大大優(yōu)于HEC算法，在各個(gè)數(shù)據(jù)集上的吞吐量都高于HEC算法。而FC相對(duì)于EC算法在網(wǎng)絡(luò)吞吐量上得到了更大的提升。綜上所述可以得出，針對(duì)網(wǎng)絡(luò)平均吞吐量經(jīng)過(guò)優(yōu)化后的粗化算法FC要略微優(yōu)于EC算法，并且相對(duì)于HEC算法有較大的提升。

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

4.3遷移優(yōu)化階段算法對(duì)性能的影響

本節(jié)將基于不同遷移優(yōu)化階段的算法對(duì)片上網(wǎng)絡(luò)的運(yùn)行時(shí)間和吞吐量進(jìn)行比較分析。

表2的結(jié)果表明，在片上網(wǎng)絡(luò)的運(yùn)行時(shí)間方面，基于跳出局部最優(yōu)的1-way FM算法相對(duì)于EEFM算法有較大的改進(jìn)，而相對(duì)于FM算法只有較少的提升。對(duì)于IP單元片數(shù)目較少的集成網(wǎng)絡(luò)，1-way FM算法相對(duì)于其他兩種算法，所提升的性能并不是太大，但是一旦所處理的集成網(wǎng)絡(luò)規(guī)模巨大，可以看到基于1-way FM算法的網(wǎng)絡(luò)能夠大大地減少片上網(wǎng)絡(luò)所運(yùn)行的時(shí)間。

Table 2　Impact of different migration optimization algorithms for 3D NoCs表2　不同遷移優(yōu)化算法在片上網(wǎng)絡(luò)的影響

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

4.4hMetis算法框架對(duì)性能的影響

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

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

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

與上述時(shí)間性能方面的計(jì)算方式相同，在對(duì)吞吐量進(jìn)行評(píng)估比較時(shí)，對(duì)于不同的數(shù)據(jù)集，也會(huì)有相應(yīng)的最優(yōu)劃分來(lái)得到一個(gè)較大吞吐量的劃分框架（參見(jiàn)表4）。例如apte數(shù)據(jù)集的最大吞吐量為56.13 Kb/s，所得到的較優(yōu)hMetis框架算法為EC+1-way FM。

5　結(jié)束語(yǔ)

本文研究了針對(duì)異構(gòu)三維片上網(wǎng)絡(luò)設(shè)計(jì)的一種超圖劃分框架，并且對(duì)現(xiàn)有的超圖劃分中每一步驟中算法進(jìn)行分析與改進(jìn)。在粗化階段，提出常見(jiàn)的粗化算法的不足之處，并且對(duì)其進(jìn)行修改，提高片上網(wǎng)絡(luò)的性能；在遷移優(yōu)化階段，對(duì)FM算法進(jìn)行改進(jìn)，并且對(duì)不同的細(xì)化算法進(jìn)行比較分析。最后將不同的粗化細(xì)化算法進(jìn)行實(shí)驗(yàn)比較分析，得出一個(gè)較好的基于hMetis的算法框架。然后將得到的較好的hMetis框架算法應(yīng)用到異構(gòu)三維片上網(wǎng)絡(luò)中，分析該算法的性能效果，并且使用運(yùn)行時(shí)間和網(wǎng)絡(luò)吞吐量的性能指標(biāo)來(lái)衡量利用該算法框架設(shè)計(jì)的三維片網(wǎng)性能的優(yōu)劣。

由于本文使用的細(xì)化階段算法為1982年Fiduccia和Mattheyses提出的FM算法，經(jīng)過(guò)三十多年，雖然該領(lǐng)域內(nèi)提出了許多圖劃分的算法，但基本上都以此算法為基礎(chǔ)而進(jìn)行的改進(jìn)。因此，尋找一種更好的劃分來(lái)提高片上網(wǎng)絡(luò)的性能將是下一步的工作。另外，由于本文所研究的片上網(wǎng)絡(luò)性能指標(biāo)只有網(wǎng)絡(luò)的運(yùn)行時(shí)間和吞吐量，但真正的片上網(wǎng)絡(luò)受許多因素的影響，下一步還可以用其他更多的影響因素來(lái)衡量算法的優(yōu)劣。

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.

附中文參考文獻(xiàn):

[1]盧玥,曹建文.超圖多級(jí)劃分算法框架及對(duì)劃分結(jié)果的多階段優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(4):800-802.

[9]汪淼,唐玉華.面向OpenFOAM的并行圖劃分與超圖劃分方法設(shè)計(jì)與實(shí)現(xiàn)[D].長(zhǎng)沙:國(guó)防科技大學(xué),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.

宋國(guó)治（1977—），男，黑龍江哈爾濱人，2009年于英國(guó)倫敦大學(xué)瑪麗王后學(xué)院電子工程專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為天津工業(yè)大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)，異構(gòu)無(wú)線(xiàn)網(wǎng)絡(luò)整合，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)等。發(fā)表學(xué)術(shù)論文40余篇，獲發(fā)明專(zhuān)利6項(xiàng)，軟件著作權(quán)1項(xiàng)，主持或參加過(guò)多項(xiàng)國(guó)家自然科學(xué)基金、國(guó)家科技支撐計(jì)劃及天津市教委項(xiàng)目等。

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年于東北大學(xué)計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)，組合算法設(shè)計(jì)，虛擬現(xiàn)實(shí)技術(shù)等。發(fā)表學(xué)術(shù)論文30余篇，主持并承擔(dān)過(guò)多項(xiàng)國(guó)家自然科學(xué)基金、國(guó)家863計(jì)劃及省部級(jí)課題。

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—），男，浙江寧波人，中山大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)，超圖劃分等。

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—），男，安徽淮南人，天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)布局規(guī)劃問(wèn)題。

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—），女，黑龍江大慶人，天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院學(xué)生，主要研究領(lǐng)域?yàn)槠暇W(wǎng)絡(luò)的布局劃分。

*The National Natural Science Foundation of China under Grant No.61272006(國(guó)家自然科學(xué)基金);the National Training Program of Innovation and Entrepreneurship for Undergraduates under Grant No.201510058050(國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-08-12,http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1652.010.html

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

文獻(xiàn)標(biāo)志碼：A

中圖分類(lèi)號(hào)：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