眾核處理器片上網(wǎng)絡的層次化全局自適應路由機制

張　洋　王　達　葉笑春　朱亞濤,3　范東?！±詈炅痢≈x向輝

1(計算機體系結(jié)構國家重點實驗室(中國科學院計算技術研究所)　北京　100190)2(中國科學院大學計算機與控制學院　北京　100049)3(河北農(nóng)業(yè)大學信息科學與技術學院　河北保定　071001)4(數(shù)學工程與先進計算國家重點實驗室　江蘇無錫　214125)(zhangyang@ict.ac.cn)

?

眾核處理器片上網(wǎng)絡的層次化全局自適應路由機制

張洋1,2王達1葉笑春1朱亞濤1,2,3范東睿1李宏亮4謝向輝4

1(計算機體系結(jié)構國家重點實驗室(中國科學院計算技術研究所)北京100190)2(中國科學院大學計算機與控制學院北京100049)3(河北農(nóng)業(yè)大學信息科學與技術學院河北保定071001)4(數(shù)學工程與先進計算國家重點實驗室江蘇無錫214125)(zhangyang@ict.ac.cn)

摘要Mesh和環(huán)拓撲結(jié)構以其實現(xiàn)簡單、易于擴展的特點成為眾核處理器片上網(wǎng)絡應用最為廣泛的拓撲結(jié)構.應用于Mesh結(jié)構中的健忘型路由算法在網(wǎng)絡流量較大時影響片上網(wǎng)絡的負載均衡，表現(xiàn)在降低吞吐量和增大數(shù)據(jù)包延遲.自適應算法中的本地自適應算法和區(qū)域自適應算法均存在不同程度的短視現(xiàn)象，不適合大規(guī)模的Mesh結(jié)構，而目前全局自適應算法又由于路由計算量大而速度緩慢.提出一種新的層次化全局自適應路由機制，包括一個全局擁塞信息傳播網(wǎng)絡Roof-Mesh和一個層次化全局自適應路由算法(global hierarchical adaptive routing algorithm, GHARA).通過全局擁塞信息傳播網(wǎng)絡得到擁塞信息，GHARA采用全網(wǎng)分區(qū)逐級計算路由的方式，減少了全局路由的計算步驟，從而減少了平均數(shù)據(jù)包延遲、提升了飽和帶寬.實驗結(jié)果表明GHARA表現(xiàn)優(yōu)于其他區(qū)域和全局自適應路由算法.在人工注入通信模式下，8×8 Mesh平均飽和帶寬比全局自適應算法GCA提高10.7%，16×16 Mesh平均飽和帶寬比全局自適應算法GCA提高14.7%.在運行真實測試程序集SPLASH-2模式下，數(shù)據(jù)包延遲最高比GCA提高40%，平均提升14%.

關鍵詞眾核處理器；片上網(wǎng)絡；負載均衡；全局擁塞信息傳播網(wǎng)絡；層次化全局自適應路由算法；Roof-Mesh

多核和眾核處理器已成為業(yè)界的主流.在多核、眾核處理器以及片上系統(tǒng)的設計中，片上網(wǎng)絡互聯(lián)結(jié)構以其高帶寬、低延遲、擴展性強，容錯性好等特點迅速取代了共享總線等其他片上連接模式，成為該領域的主流互聯(lián)方法.迄今為止，大部分片上網(wǎng)絡的拓撲結(jié)構的研究借鑒了并行計算體系結(jié)構中的網(wǎng)絡結(jié)構，而在實際應用中，Mesh[1-3]由于組成簡單、連線較短的特點，逐漸成為使用結(jié)構最為廣泛的結(jié)構.由于在此類拓撲結(jié)構中，從源節(jié)點到目的節(jié)點存在多條路徑，因此片上網(wǎng)絡的路由算法需要在眾多路徑中做出選擇.路由算法將影響整個網(wǎng)絡的負載均衡，具體體現(xiàn)在延遲和吞吐量的變化.

根據(jù)路由依據(jù)條件的不同，片上網(wǎng)絡的路由算法可簡單地分為健忘性算法和自適應算法.健忘性算法如維序路由(dimension ordered routing, DOR)在路由仲裁過程中完全不考慮網(wǎng)絡的擁塞狀態(tài)，只根據(jù)源節(jié)點和目的節(jié)點的位置確定路由.盡管健忘性算法的復雜度低，但是在網(wǎng)絡流量較大時卻會造成嚴重的擁塞而使得網(wǎng)絡負載不均衡[4].相反地，自適應算法根據(jù)網(wǎng)絡擁塞狀態(tài)，在源-目的節(jié)點之間動態(tài)選擇相對不擁塞的1條路徑來平衡網(wǎng)絡負載，較之健忘性負載，自適應算法能帶來更好的片上網(wǎng)絡性能，逐漸成為大規(guī)模片上網(wǎng)絡主流路由算法.但是自適應算法很難有效地獲得全局負載信息，即使一些算法可以獲得這部分信息，因為全局信息數(shù)據(jù)量龐大也影響到了計算路由的速度.

在自適應算法的實現(xiàn)過程中，不同的算法獲得擁塞信息的方法不同.依據(jù)獲得網(wǎng)絡節(jié)點信息規(guī)模的大小，可分為本地自適應(local adaptive)算法、區(qū)域自適應(regional adaptive)算法和全局自適應(global adaptive)算法[5].本地自適應算法用本地擁塞信息來決定路由，實現(xiàn)起來比較簡單.但是本地自適應算法會因為前期的短視現(xiàn)象導致后期不得不選擇高擁塞路徑.和本地自適應相比，區(qū)域自適應算法擴大了自適應范圍.但是由于依舊存在一定范圍的限制，仲裁出的路由仍然有可能將通信引入自適應范圍之外的擁塞區(qū).全局自適應算法能感知全局擁塞信息，進而指導路由，能最大程度避免負載均衡.但是目前已知的全局路由算法均存在不同程度的更新負載信息或者計算路由較慢的問題.

針對本地自適應算法和區(qū)域自適應算法很難有效獲得全局負載信息同時全局自適應算法計算路由速度慢的問題，本文提出一種全局擁塞信息傳播結(jié)構Roof-Mesh，同時基于這種Roof-Mesh結(jié)構提出一種層次化全局自適應路由算法(global hierar-chical adaptive routing algorithm, GHARA).本文的主要貢獻為：

1) 提出的全局擁塞信息傳播結(jié)構Roof-Mesh將N×N的Mesh網(wǎng)絡分為lbN-1級子網(wǎng)絡，每個子網(wǎng)都有一個附加網(wǎng)絡進行子網(wǎng)節(jié)點的擁塞信息的收集和傳播.每一級附加網(wǎng)絡對其下一級附加網(wǎng)絡的擁塞信息進行處理.

2) 本文基于Roof-Mesh提出一種混合精確粒度的層次化全局自適應路由算法GHARA.實驗結(jié)果表明GHARA表現(xiàn)優(yōu)于其他區(qū)域和全局自適應路由算法.在人工注入通信模式下，8×8 Mesh的平均飽和帶寬比全局擁塞感知(global congestion awareness, GCA)提高10.7%，16×16 Mesh平均飽和帶寬比GCA提高14.7%.而在運行真實測試程序集SPLASH-2[6]模式下，數(shù)據(jù)包延遲最高比GCA提高40%，平均提升14%.

1相關工作

Dally和Aoki[7]用當前節(jié)點空閑虛通道(virtual channel, VC)的數(shù)目來作為擁塞指標，路由器選擇擁有較多虛通道的輸出端口作為當前節(jié)點輸出方向.Li等人[8]在DyXY算法中，用節(jié)點的輸入緩沖隊列長度來表示1個節(jié)點的壓力值，節(jié)點通過監(jiān)視相鄰節(jié)點的壓力值來作為路由仲裁的依據(jù).這些方法只利用本地擁塞信息來決定路由，實現(xiàn)起來比較簡單，而且不會因為傳播擁塞信息而對網(wǎng)絡通信造成影響.但是從全局角度來看，本地自適應算法會因為前期的短視現(xiàn)象導致后期不得不選擇高擁塞路徑.在Gratz等人[9]提出的區(qū)域擁塞感知(regional congestion awareness, RCA)中，首次提出監(jiān)視范圍超越鄰居節(jié)點的路由機制.RCA通過一個額外網(wǎng)絡將局部擁塞信息傳播給更遠的節(jié)點.Ma等人[10]提出基于目的的自適應路由算法(destination-based adaptive routing, DBAR)改進了RCA，使得擁塞結(jié)果更為精確.和本地自適應相比，區(qū)域自適應擴大了自適應范圍，為路由仲裁提供了更好的依據(jù).但是由于依舊存在一定范圍的限制，按照擁塞結(jié)果仲裁出的路由仍然有可能將通信引入監(jiān)視范圍之外的擁塞區(qū).Manevich等人[11]提出自適應切換維度順序路由算法ATDOR(adaptive toggle dimension ordered routing)，在這個算法中，Manevich等人用1個附加網(wǎng)絡傳送各節(jié)點擁塞信息到1個表中，以此來為每個源-目的節(jié)點對選擇XY或者YX維序路由.這個方法得到即時全局擁塞信息非常精確，但是隨著網(wǎng)絡規(guī)模的增加，擁塞表更新的速度會變慢.在GCA中，Gratz等人[5]使用“背負式”(piggybacking)信息模式，將數(shù)據(jù)包所經(jīng)過的節(jié)點的擁塞信息嵌入到數(shù)據(jù)包頭中進行傳播.各節(jié)點提取經(jīng)過自己的數(shù)據(jù)包頭中的擁塞信息來更新各自的全局擁塞信息表.這個辦法的開銷很小，但是擁塞信息只能被數(shù)據(jù)經(jīng)過的節(jié)點感知，同時GCA由于計算路由的時間較長而影響了自身的性能.

本文提出一種全局擁塞信息傳播結(jié)構Roof-Mesh，以及基于Roof-Mesh結(jié)構的層次化全局自適應路由算法GHARA，減少了計算步驟，從而降低了網(wǎng)絡數(shù)據(jù)包延遲，提高了飽和帶寬.

2Roof-Mesh片上網(wǎng)絡

本文所提出的Roof-Mesh是一種多層次片上網(wǎng)絡全局擁塞信息傳播結(jié)構.理論上這種結(jié)構可以監(jiān)聽傳播所有片上網(wǎng)絡拓撲結(jié)構的擁塞信息，本文只針對Mesh這種結(jié)構的設計展開.為了便于描述，本文以一個8×8的Mesh網(wǎng)絡為例進行介紹.本文將在第4節(jié)中對在更大規(guī)模的網(wǎng)絡上應用基于該結(jié)構的算法進行評估.

2.1Roof-Mesh的基本組成

在Roof-Mesh結(jié)構中，節(jié)點的擁塞信息通過節(jié)點router內(nèi)各方向端口可用的輸入VC數(shù)衡量，1個方向上可用VC數(shù)越少，表示這個方向上擁塞程度等級越高.擁塞程度可分為多個不同等級，每個等級對應一組可用VC數(shù)量.VC數(shù)量上細微的差別對于網(wǎng)絡通信的影響不明顯[10]，為了節(jié)省傳遞擁塞信息的附加網(wǎng)絡的帶寬，在本文的設計中我們將擁塞程度分成2個等級：擁塞和不擁塞，可用VC數(shù)量少于VC總數(shù)的一半表示這個端口擁塞，反之可用VC數(shù)量超過VC總數(shù)的一半表示不擁塞.按照分層次擁塞傳播的思路，每4個節(jié)點組成1個G4組，4個G4組組成1個G16組.組擁塞狀態(tài)也分為類似開關的2個等級，以節(jié)省信息傳播開銷.每個節(jié)點router連接到1級附加網(wǎng)絡中的上行帶寬為4 b，為1組4個方向擁塞信息的等級值.下行5 b，其中2 b為擁塞信息類型，3 b為1組3個擁塞信息的等級值.對于1個8×8的Mesh結(jié)構來說，擁塞信息類型可分類為每個節(jié)點的擁塞信息，每4個節(jié)點組成的G4組擁塞信息和每16點組成的G16組擁塞信息.節(jié)點router上傳自己4個方向的擁塞信息，接收同在1個G4組內(nèi)的其他3個節(jié)點的擁塞信息， 同在一個G16組內(nèi)的其他3個G4組的擁塞信息以及其他3個G16的擁塞信息.

2.2多級擁塞傳播附加網(wǎng)絡

每16個節(jié)點組成的G16組，構成1個1級擁塞傳播附加網(wǎng)絡，如圖1所示.G16內(nèi)的所有節(jié)點將自己的擁塞信息傳給附加網(wǎng)絡中央的1級擁塞管理單元(CMU-L1)，CMU-L1存儲G16的所有節(jié)點詳細擁塞等級信息，根據(jù)各個節(jié)點的位置，CMU-L1返回給各個節(jié)點其他節(jié)點相應方向端口的擁塞信息以及由這些信息組成的4個G4組信息.CMU-L1的結(jié)構如圖2所示，16個節(jié)點將自己的擁塞信息傳入CMU-L1中的組內(nèi)節(jié)點擁塞信息寄存器，節(jié)點擁塞寄存器將內(nèi)容交予擁塞信息處理單元處理.處理工作包含將節(jié)點信息整合成G4組擁塞信息和G16組擁塞信息，以及將不同方向的節(jié)點擁塞信息分類傳給不同位置的節(jié)點.對于1個節(jié)點來說，其他節(jié)點哪個方向的擁塞值對他來說有意義取決于2個節(jié)點的位置.節(jié)點所在X和Y維將網(wǎng)絡分為4個象限，對于不同象限來說，節(jié)點關注它們不同方向的擁塞值.

Fig. 1　Roof-Mesh network.圖1　Roof-Mesh網(wǎng)絡

Fig. 2　CMU-L1 micro-architecture.圖2　CMU-L1 微結(jié)構

4個G16組成1個G64，每個G16的CMU-L1連接至1個2級擁塞監(jiān)控單元(CMU-L2)， 構成1個2級擁塞監(jiān)控網(wǎng)絡，如圖1左圖所示.CMU-L2的作用是收集并傳播G16的擁塞信息，由于G16在第3節(jié)提到的路由算法中屬于相對遠距離參考因素，因此我們僅收集和傳播G16組擁塞程度的加權平均信息.由于處于2個G16邊界的擁塞相對于全網(wǎng)邊緣的擁塞對路由的影響更大，我們在處理計算G16組平均擁塞時，對2個G16邊界的擁塞增加了1倍的權重.CMU-L2的結(jié)構如圖3所示.在8×8的Mesh結(jié)構中，2級擁塞傳播網(wǎng)絡即為頂層網(wǎng)絡.在頂層網(wǎng)絡的CMU中，擁塞信息處理單元將4組G16的擁塞信息分類傳回低一級CMU中.

Fig. 3　CMU-L2 micro-architecture.圖3　CMU-L2微結(jié)構

圖4表示在每個節(jié)點路由器內(nèi)的擁塞信息寄存器存儲了和此節(jié)點同一個G4組內(nèi)的其他節(jié)點的擁塞信息、此G4組同一個G16組內(nèi)其他G4組的擁塞信息以及其他G16組的擁塞信息.其中相鄰的節(jié)點、G4組或G16組擁塞信息存儲整體平均擁塞值，不相鄰的則存儲2個方向單獨的平均值.

Fig. 4　Congestion information register.圖4　擁塞信息寄存器

Fig. 5　Global hierarchical adaptive routing algorithm (GHARA).圖5　層次化全局自適應路由算法

3層次化全局自適應路由算法

基于全局范圍內(nèi)的擁塞信息, 我們提出一種層次化全局自適應路由算法GHARA.這種算法根據(jù)每個路由器從擁塞監(jiān)控網(wǎng)絡得到即時的全網(wǎng)絡范圍內(nèi)的擁塞狀態(tài)信息，選擇合適的輸出端口.由于該算法參考的信息為全局擁塞狀態(tài)信息，因此解決了本地和區(qū)域自適應路由算法的短視問題.

3.1GHARA算法

如圖5所示的G16 grouping圖，基于Roof-Mesh網(wǎng)絡，將8×8的Mesh網(wǎng)絡分割成4個4×4的區(qū)域，即第1節(jié)中提到的G16.每個G16分成4個2×2的區(qū)域G4.通過Roof-Mesh，每個節(jié)點中的擁塞信息寄存器得到2個相鄰節(jié)點的對應方向接口擁塞信息，以及在同一個G4組中對角線上節(jié)點對應2個方向擁塞信息.除此之外，得到同一個G16組內(nèi)其他G4組的平均擁塞信息以及其他3個G16組的平均擁塞信息.由于較遠的節(jié)點的即時擁塞信息可能在以后數(shù)據(jù)經(jīng)過時發(fā)生變化，同時出于開銷的考慮，在計算路由時，除了節(jié)點本身所在G4組內(nèi)的節(jié)點擁塞值使用精確信息以外，其他相對較遠的節(jié)點我們都用其組內(nèi)平均擁塞信息.

GHARA算法步驟如下：

1) GHARA計算2個節(jié)點之間的路由，首先判斷2個節(jié)點屬于哪2個G16組.

2) 把G16組抽象成多個節(jié)點，G16組的加權平均擁塞值視為抽象節(jié)點擁塞值.判斷源節(jié)點所在抽象節(jié)點到目的節(jié)點所在抽象節(jié)點的路由，即G16組級路由.

3) 通過抽象出的G16組級路由，在源節(jié)點所在G16組內(nèi)定位組級路由方向上的邊界節(jié)點集合.

4) 計算從源節(jié)點至G16組邊界節(jié)點集合的最小擁塞路徑.將G16內(nèi)的4個G4組抽象成4個節(jié)點，4個G4組各自的加權平均擁塞值視為抽象節(jié)點擁塞值.計算這4個抽象節(jié)點間至邊界的路由，即G4組級路由.

5) 通過抽象出的G4組級路由，在源節(jié)點所在G4組內(nèi)定位G4組級路由方向上的邊界節(jié)點集合.

6) 計算到邊界上2個節(jié)點的最小擁塞路徑.找到源節(jié)點的輸出端口.

算法1. GHARA算法.

①source=Group(source,n);*n為級數(shù)*

②destination=Group(destination,n);

③ ifsource=destination.neighbour

④temp=Direction(source,destination);

⑤ else

⑥temp1=Congestion(source.clockwise)+Congestion(destination.clockwise)+Congestion(source.leftneigbour);

⑦temp2=Congestion(source.anticlockwise)+Congestion(destination.anticlockwise)+Congestion(source.rightneigbour);

⑧ end if

⑨ iftemp1

⑩temp=source.leftneigbour;

下面舉例說明GHARA算法.圖5計算1個從(0,0)到(6,6)的路由，每一步計算路由的目標均用黑色標注.節(jié)點(0,0)所在G16組為G16-0，節(jié)點(6,6)所在G16組為G16-3.從擁塞信息寄存器中獲得G16-1和G16-2的擁塞值分別為1和0，因此路由選擇從G16-2區(qū)域經(jīng)過.在G16-0中，每一跳都將計算到區(qū)域G16-0和G16-2的邊境點(3,0), (3,1), (3,2), (3,3)之一的最小擁塞距離.在計算G16內(nèi)的最小擁塞路徑時，我們繼續(xù)將G16內(nèi)的G4組看作是4個節(jié)點進行計算，從擁塞信息寄存器中我們獲得G4-1，G4-2，G4-3的擁塞值分別為0，1，0.因此選擇從G4-1，G4-3抵達G16-0的邊境點(3,2)，(3,3).接下來在G4-0中要計算節(jié)點(0，0)到G4邊境節(jié)點(0，1)和(1，1)的最小擁塞.從擁塞信息寄存器中獲得節(jié)點(0，1)，(1，0)的擁塞信息分別0和1, 同時得到節(jié)點(1，1) 2個方向的擁塞信息為1和1.因此將選擇(0，1)為下一個節(jié)點，輸出端口為E.(0，1)為邊境目的節(jié)點則選擇過境，進入G4-1，之后重復在G4-0內(nèi)的計算過程，數(shù)據(jù)包進入G4-3，選擇邊境目的節(jié)點，到達G16邊境，然后進入G16-2開始下一輪路由計算.

3.2支持GHARA的路由器微結(jié)構

Fig. 6　GHARA router micro-architecture.圖6　GHARA 路由器微結(jié)構

GHARA的路由器如圖6所示，我們以Ma等人在文獻[10]提出的VC路由器作為基線路由器，其流水線分為路由計算(RC)、VC分配(VA)、交換分配(SA)和交換傳送(ST)這4級以及1個周期的LT(鏈路傳送).該路由器為了提高性能，利用lookahead路由模式將RC提前執(zhí)行以縮短流水線深度[12-13].同時，在ST流水級所在周期編碼目的節(jié)點地址信號和邊境目的地址信號，同時進行下一個路由器到全網(wǎng)各節(jié)點的輸出端口計算[14-15].在LT所在周期，下一個路由器通過上一周期產(chǎn)生的目的節(jié)點編碼信號和全網(wǎng)各節(jié)點路由表預取即將到來flit的輸出端口.

在基線處理器的基礎上，我們修改了原有的X維和Y維的擁塞寄存器，添加了1個第1節(jié)提到的全局擁塞信息寄存器.擁塞信息通過監(jiān)控網(wǎng)絡存儲在寄存器中，根據(jù)寄存器中的擁塞信息，路由計算單元根據(jù)擁塞信息通過GHARA計算當前節(jié)點到全網(wǎng)每個節(jié)點的路由對應輸出端口.將到每個節(jié)點應選擇的輸出端口結(jié)果存儲在輸出端口表中.由目的地址的編碼去選取輸出端口表中的對應值.

4實驗評估

本節(jié)評估GHARA在多種人工片上通信模式以及實際負載測試程序集上的性能.

4.1實驗設置

我們修改了片上網(wǎng)絡模擬器booksim2.0[16]來實現(xiàn)Roof-Mesh擁塞監(jiān)控網(wǎng)絡結(jié)構以及GHARA所需要的路由器微結(jié)構.我們利用GEM5[17]來抓取booksim2.0所需要格式的測試程序trace.本文分別從確定路由算法、本地自適應路由算法、區(qū)域自適應算法和全局自適應算法中選取了DOR，Local，RCA， GCA作為GHARA的對比算法進行評估.

本文采用8×8和16×16的2D Mesh的拓撲結(jié)構，路由器的流水線合并了RC和VC，SA使用2個流水級，每一跳除了流水線中的2個周期，還需要1個周期的鏈接傳輸.每個端口上使用8個VC，每個VC有5個微片緩沖.片上網(wǎng)絡模擬的預熱需要10 000個周期，數(shù)據(jù)采樣來自于接下來的100 000個周期.

在評估人工注入傳輸模式下的片上網(wǎng)絡性能時使用了刷洗(shuffle)、轉(zhuǎn)置(transpose)和位反(bit-reverse)三種通信傳輸模式，在評估真實測試程序下的片上網(wǎng)絡性能時使用了SPLASH-2測試用例集中的fft，raydix，raytrace，ocean，barnes.

4.2實驗結(jié)果與分析

1) 真實測試程序.圖7給出了5種算法在8×8 Mesh網(wǎng)絡下運行實際科學計算測試程序SPLASH-2的平均數(shù)據(jù)包延遲.為了直觀比較各種算法的性能，所有運行結(jié)果進行了對DOR的結(jié)果的歸一化運算.從圖7可以看出，GHARA在5個測試程序中表現(xiàn)最好，其平均數(shù)據(jù)包延遲比DOR減少35.4%，比Local減少16%，比RCA減少18%，比GCA減少14%.其中在raytrace中，GHARA表現(xiàn)了相對最優(yōu)情況，其平均數(shù)據(jù)包延遲比GCA減少40%.我們還可以看到在大部分實際測試程序中，全局自適應算法GCA比區(qū)域自適應算法RCA并沒有太多的性能提升，這是由GCA在其傳播擁塞信息的途徑的局限性以及計算路由的速度決定的，而GHARA在傳播擁塞信息和計算路由方面的設計保證了其在大部分情況下都能表現(xiàn)出良好的性能.

Fig. 7　Performance of SPLASH-2 benchmark traces.圖7　SPLASH-2 測試程序集性能評估

Fig. 8　Performance of synthetic workloads (8×8 Mesh).圖8　人工模式性能評估(8×8 Mesh)

2) 人工合成通信.圖8和圖9分別給出了包括GHARA在內(nèi)的5種路由算法在8×8和16×16的2D Mesh中不同負載下的平均數(shù)據(jù)包延遲，以此來衡量算法的性能.當延遲到達零負載延遲的3倍時，判斷性能到達飽和點.可以看出在3種通信傳輸模式下，GHARA都表現(xiàn)出了最好的性能.在刷洗(shuffle)、轉(zhuǎn)置(transpose)和位反(bit-reverse)模式下，確定路由算法DOR都由于容易造成負載不均衡而嚴重影響了性能.自適應路由算法均在這3個模式中發(fā)揮了很好的作用，但是本地自適應算法Local以及區(qū)域自適應算法RCA均存在不同程度的近視現(xiàn)象，從而限制了算法的性能.而全局自適應路由算法GCA由于計算步驟較多，表現(xiàn)并不突出，8×8 Mesh下平均飽和帶寬僅比RCA提高8.5%，在16×16 Mesh下的平均飽和帶寬比RCA提高不足6%.

Fig. 9　Performance of synthetic workloads (16×16 Mesh).圖9　人工模式性能評估(16×16 Mesh)

GHARA算法在3種模式下都勝過其他4種算法，表1和表2展示了實驗中8×8 和16×16 Mesh下所有算法在3種模式下的飽和帶寬以及GHARA相對這些算法提高的百分比.在transpose模式下，8×8 Mesh下GHARA的飽和帶寬比GCA提高 13.9%，16×16 Mesh下GHARA的飽和帶寬比GCA提高 17.6%.3個模式平均來看，GHARA在8×8 Mesh下平均飽和帶寬比GCA提高10.7%，在16×16 Mesh下平均飽和帶寬比GCA提高14.7%.隨著網(wǎng)絡規(guī)模的增加，本地自適應算法Local和區(qū)域自適應算法RCA由于近視現(xiàn)象產(chǎn)生次優(yōu)路由越發(fā)明顯，計算步驟較多的全局自適應路由算法GCA也越來越慢.由于擁有全局擁塞信息同時計算速度較快，相比于其他算法GHARA在16×16 Mesh中比在8×8 Mesh中表現(xiàn)了更大的飽和帶寬優(yōu)勢.

Table 1Saturation Throughput on 8×8 Mesh and

Improvement of GHARA

表1　8×8 Mesh飽和帶寬及GHARA提高百分比

Table 2Saturation Throughput on 16×16 Mesh and

Improvement of GHARA

表2　16×16 Mesh飽和帶寬及GHARA提高百分比

5總結(jié)與展望

本文針對本地自適應算法和區(qū)域自適應算法很難有效獲得全局負載信息以及目前全局自適應算法計算路由速度慢的問題，提出了一個新型全局自適應路由機制.該機制包含一個全局擁塞信息監(jiān)視網(wǎng)絡Roof-Mesh和一個全局自適應路由算法GHARA.Roof-Mesh將全網(wǎng)Mesh結(jié)構分成多級區(qū)域，針對不同區(qū)域中各個節(jié)點，得到不同精確度的全局節(jié)點擁塞信息.GHARA是一個低開銷、全局性、可擴展的多級自適應路由算法，其主要有2個特點：

1) 具有全局的視角.利用Roof-Mesh全局擁塞信息監(jiān)視網(wǎng)絡，每個節(jié)點獲得不同精確度的全網(wǎng)各個節(jié)點的擁塞信息以指導路由計算，從而避免了本地自適應算法的短視現(xiàn)象.

實驗結(jié)果表明：GHARA表現(xiàn)優(yōu)于其他區(qū)域和全局自適應路由算法如RCA和GCA.在人工注入通信模式下8×8 Mesh平均飽和帶寬比GCA提高10.7%，16×16 Mesh平均飽和帶寬比GCA提高14.7%.而在運行真實測試程序集SPLASH-2模式下，平均數(shù)據(jù)包延遲最多比GCA減少40%，平均減少14%.

GHARA的可擴展性體現(xiàn)在隨著網(wǎng)絡規(guī)模的增加，我們只需要在全局擁塞信息監(jiān)視網(wǎng)絡Roof-Mesh中增加相應的擁塞監(jiān)控單元、增大擁塞寄存器以及增加層次.我們接下來的工作要進一步優(yōu)化全局擁塞信息監(jiān)視網(wǎng)絡Roof-Mesh的結(jié)構，提高處理速度；同時研究在其他拓撲結(jié)構上部署類似的結(jié)構，并在此基礎上應用全局自適應路由算法.

參考文獻

[1]Wang Yongqing, Xie Lunguo, Fu Qingchao. Moveable bublle flow control and adaptive routing mechanism in torus networks[J]. Journal of Computer Research and Development, 2014, 51(8): 1854-1862 (in Chinese)(王永慶, 謝倫國, 付清朝. Torus網(wǎng)絡中移動氣泡流控及其自適應路由實現(xiàn)[J]. 計算機研究與發(fā)展, 2014, 51(8): 1854-1862)

[2]Sankaralingam K, Nagarajan R, Gratz P, et al. The distributed microarchitecture of the TRIPS prototype processor[C] //Proc of the 39th Int Symp on Microarchitecture. Piscataway, NJ: IEEE, 2006: 480-491

[3]Vangal S, Howard J, Ruhl G, et al. An 80-Tile1.28 TFLOPS network-on-chip in 65nm CMOS[C] //Proc of IEEE Int Solid-state Circuits Conf. Piscataway, NJ: IEEE, 2007: 98-99

[4]Rahman M, Shah A, Inoguchi Y. A deadlock-free dimension order routing for hierarchical 3D-mesh network[C] //Proc of Int Conf on Computer & Information Science (ICCIS). Piscataway, NJ: IEEE, 2012: 563-568

[5]Ramakrishna M, Gratz P, Sprintson A. GCA: Global congestion awareness for load balance in networks-on-chip[C] //Proc of the 7th Int Symp on Networks on Chip (NoCS). Piscataway, NJ: IEEE, 2013: 1-8

[6]Woo S, Ohara M, Torrie E, et al. The SPLASH-2 programs: Characterization and methodological considerations[C] //Proc of the 22nd Annual Int Symp on Computer Architecture (ISCA). Piscataway, NJ: IEEE, 1995:24-36

[7]Dally W, Aoki H. Deadlock-free adaptive routing in multicomputer networks using virtual channels[J]. IEEE Trans on Parallel and Distributed Systems, 1993, 4(4): 466-475

[8]Li M, Zeng Q, Jone W. DyXY—A proximity congestion-aware deadlock-free dynamic routing method for network on chip[C] //Proc of the 43rd Design Automation Conf. Piscataway, NJ: IEEE, 2006: 849-852

[9]Gratz P, Grot B, Keckler S. Regional congestion awareness for load balance in networks-on-chip[C] //Proc of the 14th High Performance Computer Architecture(HPCA). Piscataway, NJ: IEEE, 2008: 203-214

[10]Ma Sheng, Jerger N, Wang Zhiying. DBAR: An efficient routing algorithm to support multiple concurrent applications in networks-on-chip[C] //Proc of the 38th Annual Int Symp on Computer Architecture (ISCA). Piscataway, NJ: IEEE, 2011: 413-424

[11]Manevich R, Cidon I, Kolodny A, et al. A cost effective centralized adaptive routing for networks-on-chip[C] //Proc of the 14th Euromicro Conf on Digital System Design (DSD). Piscataway, NJ: IEEE, 2011: 39-46

[12]Kim J, Park D, Theocharides T, et al. A low latency router supporting adaptivity for on-chip interconnects[C] //Proc of the 42nd Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2005: 559-564

[13]Galles M. Spider: A high-speed network interconnect[J]. Micro, 1997, 17(1): 34-39

[14]Gratz P, Sankaralingam K, Hanson H,et al. Implementation and evaluation of a dynamically routed processor operand network[C] //Proc of the 1st Int Symp on Networks-on-Chip. Piscataway, NJ: IEEE, 2007: 7-17

[15]Kumar A, Kundu P, Singh A, et al. A 4.6Tbits/s 3.6GHz single-cycle NoC router with a novel switch allocator in 65nm CMOS[C] //Proc of the 25th Int Conf on Computer Design (ICCD). Piscataway, NJ: IEEE, 2007: 63-70

[16]Dally W, Towles B. Principles and Practices of Interconnection Networks[M]. San Francisco, CA: Morgan Kaufmann, 2003

[17]Binkert N, Beckmann B, Black G, et al. The GEM5 simulator[J]. ACM SIGARCH Computer Architecture News, 2011, 39(2): 1-7

Zhang Yang, born in 1981. PhD candidate. Member of China Computer Federation. His main research interests include network-on-chips design and real-time scheduling.

Wang Da, born in 1981. PhD, associate professor. Member of China Computer Federation. Her main research interests include IC testing and analysis, micro architecture design, many-core processor, and VLSI design and testing.

Ye Xiaochun, born in 1981. PhD, associate professor. Member of China Computer Federation. His main research interests include high-performance computer archi-tecture, software simulation, algorithm paralleling and optimizing.

Zhu Yatao, born in 1978. PhD candidate. Member of China Computer Federation. His main research interests include high throughput computing architecture and software simulation.

Fan Dongrui, born in 1979. PhD, professor and PhD supervisor. Member of China Computer Federation. His main research interests include many-core processor design, high throughput processor design and low power micro-architecture.

Li Hongliang, born in 1975. PhD, associate professor. Member of China Computer Federation. His main research interests include high performance computing and processors architecture design.

Xie Xianghui, born in 1958. PhD, professor. Senior member of China Computer Federation. His main research interests include high performance computer archit-ecture and distributed computing.

A Global Hierarchical Adaptive Routing Mechanism in Many-Core Processor Network-on-Chip

Zhang Yang1,2, Wang Da1, Ye Xiaochun1, Zhu Yatao1,2,3, Fan Dongrui1, Li Hongliang4, and Xie Xianghui4

1(StateKeyLaboratoryofComputerArchitecture(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)2(SchoolofComputerandControlEngineering,UniversityofChineseAcademyofSciences,Beijing100049)3(CollegeofInformationScience&Technology,AgriculturalUniversityofHebei,Baoding,Hebei071001)4(StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Wuxi,Jiangsu214125)

AbstractAccompanied by the arrival of the era of big data, data center has been becoming an infrastructure in human life.Many-core processor provides a highly parallel capability to solve applications in data center such as sorting and searching efficiently. For the purpose to utilize the parallelism of many-core processor, routing algorithm in interconnection network turns into one of the most important issues in many-core system. Mesh and ring are the most employed topological structures in many-core processor for their features of easy implementation and high scalability. Depending on the scope of congestion information, routing algorithms in mesh and ring can be divided into oblivious routing, local adaptive routing, regional adaptive routing and global adaptive routing. The oblivious routing algorithm applied in the mesh architecture affects the load-balance of the network which is reflected in reducing through-put and high packet latency. Current local adaptive routing and regional adaptive routing both suffer from short-sightedness and are not suitable for large scale mesh structure. And prior global adaptive routings are limited by the slow computation of global route. We propose a novel global hierarchical adaptive routing mechanism, which is comprised of a global congestion information propagation network Roof-Mesh and a global hierarchical adaptive routing algorithm GHARA. Roof-Mesh provides a platform to share global congestion information in a hierarchical way among all nodes on the network. Depending on the information supplied by Roof-Mesh, GHARA reduces the procedure of routing by hierarchically computing from large region perspective to neighbor nodes. The result of experiment shows that GHARA performs better than other regional and global adaptive routings.

Key wordsmany-core processor; networks-on-chip; load balance; global congestion information propagation network; global hierarchical adaptive routing algorithm (GHARA); Roof-Mesh

收稿日期：2015-02-15；修回日期：2015-07-14

基金項目：國家“九七三”重點基礎研究發(fā)展計劃基金項目(2011CB302501)；國家自然科學基金項目(61332009,61173007,61221062)；“核高基”國家科技重大專項基金項目(2013ZX0102-8001-001-001)；國家“八六三”高技術研究發(fā)展計劃基金項目(2015AA011204,2012AA010901)

中圖法分類號TP302

This work was supported by the National Basic Research Program of China (973 Program) (2011CB302501), the National Natural Science Foundation of China (61332009,61173007,61221062), the National Science and Technology Major Projects of Hegaoji (2013ZX0102-8001-001-001), and the National High Technology Research and Development Program of China (863 Program) (2015AA011204,2012AA010901).