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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

1相關工作

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

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

2Roof-Mesh片上網絡

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

2.1Roof-Mesh的基本組成

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

2.2多級擁塞傳播附加網絡

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

Fig. 1　Roof-Mesh network.圖1　Roof-Mesh網絡

Fig. 2　CMU-L1 micro-architecture.圖2　CMU-L1 微結構

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

Fig. 3　CMU-L2 micro-architecture.圖3　CMU-L2微結構

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

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

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

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

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

3.1GHARA算法

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

GHARA算法步驟如下：

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

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

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

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

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

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

算法1. GHARA算法.

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

②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)的路由，每一步計算路由的目標均用黑色標注.節點(0,0)所在G16組為G16-0，節點(6,6)所在G16組為G16-3.從擁塞信息寄存器中獲得G16-1和G16-2的擁塞值分別為1和0，因此路由選擇從G16-2區域經過.在G16-0中，每一跳都將計算到區域G16-0和G16-2的邊境點(3,0), (3,1), (3,2), (3,3)之一的最小擁塞距離.在計算G16內的最小擁塞路徑時，我們繼續將G16內的G4組看作是4個節點進行計算，從擁塞信息寄存器中我們獲得G4-1，G4-2，G4-3的擁塞值分別為0，1，0.因此選擇從G4-1，G4-3抵達G16-0的邊境點(3,2)，(3,3).接下來在G4-0中要計算節點(0，0)到G4邊境節點(0，1)和(1，1)的最小擁塞.從擁塞信息寄存器中獲得節點(0，1)，(1，0)的擁塞信息分別0和1, 同時得到節點(1，1) 2個方向的擁塞信息為1和1.因此將選擇(0，1)為下一個節點，輸出端口為E.(0，1)為邊境目的節點則選擇過境，進入G4-1，之后重復在G4-0內的計算過程，數據包進入G4-3，選擇邊境目的節點，到達G16邊境，然后進入G16-2開始下一輪路由計算.

3.2支持GHARA的路由器微結構

Fig. 6　GHARA router micro-architecture.圖6　GHARA 路由器微結構

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

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

4實驗評估

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

4.1實驗設置

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

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

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

4.2實驗結果與分析

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

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在內的5種路由算法在8×8和16×16的2D Mesh中不同負載下的平均數據包延遲，以此來衡量算法的性能.當延遲到達零負載延遲的3倍時，判斷性能到達飽和點.可以看出在3種通信傳輸模式下，GHARA都表現出了最好的性能.在刷洗(shuffle)、轉置(transpose)和位反(bit-reverse)模式下，確定路由算法DOR都由于容易造成負載不均衡而嚴重影響了性能.自適應路由算法均在這3個模式中發揮了很好的作用，但是本地自適應算法Local以及區域自適應算法RCA均存在不同程度的近視現象，從而限制了算法的性能.而全局自適應路由算法GCA由于計算步驟較多，表現并不突出，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%.隨著網絡規模的增加，本地自適應算法Local和區域自適應算法RCA由于近視現象產生次優路由越發明顯，計算步驟較多的全局自適應路由算法GCA也越來越慢.由于擁有全局擁塞信息同時計算速度較快，相比于其他算法GHARA在16×16 Mesh中比在8×8 Mesh中表現了更大的飽和帶寬優勢.

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總結與展望

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

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

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

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

參考文獻

[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網絡中移動氣泡流控及其自適應路由實現[J]. 計算機研究與發展, 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

基金項目：國家“九七三”重點基礎研究發展計劃基金項目(2011CB302501)；國家自然科學基金項目(61332009,61173007,61221062)；“核高基”國家科技重大專項基金項目(2013ZX0102-8001-001-001)；國家“八六三”高技術研究發展計劃基金項目(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).