胡明 張俊

摘 要 路由算法的作用是在片上網(wǎng)絡(luò)中結(jié)點間相互通信時選擇一條最優(yōu)的通信路徑。文章針對片上網(wǎng)絡(luò)的傳輸規(guī)律與特性，歸類各類型的片上網(wǎng)絡(luò)路由算法。

關(guān)鍵詞 片上網(wǎng)絡(luò)；路由算法；通信

中圖分類號 G2 文獻(xiàn)標(biāo)識碼 A 文章編號 1674-6708（2019）230-0118-02

1 無關(guān)路由算法

無關(guān)路由不考慮自適應(yīng)性、容錯性等，直接發(fā)送數(shù)據(jù)包，包括維序路由算法、維序路由算法、泛洪算法。

1）維序路由算法。對一個多維網(wǎng)格來說，維序路由是指在路由路徑選擇的過程中按照維度的順序路由且維度順序不能交叉。以2D Mesh為例，維序路由要求數(shù)據(jù)必須先沿X軸方向傳輸，再沿Y方向傳輸。該路由算法實現(xiàn)簡單，且避免死鎖，但導(dǎo)致了大量的數(shù)據(jù)傳輸包含重復(fù)路徑，浪費了大量的傳輸資源。歐陽一鳴等提出了XY-YX算法，當(dāng)目的結(jié)點Y方向的值小于當(dāng)前結(jié)點Y方向的值時，選擇先Y方向后X方向傳輸；當(dāng)目的結(jié)點Y方向的值大于當(dāng)前結(jié)點對應(yīng)的值時，選擇X方向后Y方向傳輸，從而減輕XY路由算法在X方向產(chǎn)生的阻塞。該算法也是免死鎖的。2）禁止轉(zhuǎn)向算法。禁止轉(zhuǎn)向算法是對維序路由算法的一種改進(jìn)。根據(jù)Glass CJ，Ni LM.提出的轉(zhuǎn)向模型，在不使用虛通道的情況下，為了使路由算法免死鎖需要破壞逆時針和順時針的環(huán)行傳輸依賴。而維序路由算法即是破壞了順時針和逆時針各兩種轉(zhuǎn)向方式。但其限制的轉(zhuǎn)向個數(shù)并不是最少的，禁止轉(zhuǎn)向算法在正反方向僅各禁止一種轉(zhuǎn)向來達(dá)到免死鎖的目的。并不是限制任意順時針和逆時針各一種轉(zhuǎn)向就能避免死鎖，例如限制西北和北西轉(zhuǎn)向仍然會存在環(huán)形依賴導(dǎo)致死鎖。在所有禁止兩種轉(zhuǎn)向的方法中，只有4種方法可以保證死鎖，考慮對稱性有West-First（WF），NorthLast（NL）及Negative-First（NF）三種算法。禁止轉(zhuǎn)向的三種算法在某些情況下的路由路徑不是唯一的，因此其在選擇路徑中可以通過一定的選擇策略加入選擇函數(shù)來防止擁塞。3）泛洪算法。泛洪算法將數(shù)據(jù)包沿不同的方向發(fā)送相同的數(shù)據(jù)包多份，最終使得至少有一份數(shù)據(jù)包發(fā)送至目的結(jié)點。該算法由于發(fā)送數(shù)據(jù)包的路徑有多條，當(dāng)片上網(wǎng)絡(luò)的結(jié)點出現(xiàn)故障時，具有較強(qiáng)的容錯能力。但由于同時發(fā)送多份數(shù)據(jù)包，將對網(wǎng)絡(luò)的通信資源造成浪費，易引起信道的擁塞。另外為了避免數(shù)據(jù)包在片上網(wǎng)絡(luò)內(nèi)無限制游走，需要給每個數(shù)據(jù)包設(shè)置生存閾值時間，若數(shù)據(jù)包的生存時間超過該時間將自動銷毀。

2 自適應(yīng)路由算法

自適應(yīng)路由考慮網(wǎng)絡(luò)擁塞程度，選擇空閑路徑到達(dá)目的結(jié)點。自適應(yīng)路由按其對擁塞的感知程度分可分為本地?fù)砣兄蛥^(qū)域擁塞感知，按適應(yīng)程度分為完全自適應(yīng)路由和部分自適應(yīng)路由。

1）Odd-Even算法。禁止轉(zhuǎn)向中的三種算法都限制了一定的路由選擇，易引起數(shù)據(jù)包在某些方向的阻塞。另外平均一半的數(shù)據(jù)包的傳輸只有一種最短的路由策略（例如West-First算法中目的結(jié)點在發(fā)送結(jié)點西邊的情形）。而Odd-Even算法不完全限制任何一種轉(zhuǎn)向，將數(shù)據(jù)包發(fā)生擁塞的可能性降到最低，另外每一個發(fā)送-目的結(jié)點對幾乎都有多種路由策略，實現(xiàn)了高適應(yīng)性。其基本規(guī)則是在偶數(shù)列禁止由東向南和由東向北的轉(zhuǎn)向；在奇數(shù)列禁止由南向西和由北向西的轉(zhuǎn)向。Odd-Even算法相對于禁止轉(zhuǎn)向算法有更多的路由策略可供選擇，PoonaBahrebar，DirkStrooband將其運用到NoC上的多播路由，實現(xiàn)了路由策略適應(yīng)性的最大化。

2）double-x算法。維序、禁止轉(zhuǎn)向、Odd-Even等算法均通過限制一部分的路由策略實現(xiàn)了路由的免死鎖，而在某些無法限制路由策略的情況下，此時設(shè)置虛通道是另一種免死鎖的方式。Double-x算法是指在x方向的通道設(shè)置兩條虛擬通道x0及x1，而在y方向的通道不設(shè)置虛擬通道，將整個網(wǎng)絡(luò)分成上升子網(wǎng)和下降子網(wǎng)。上升子網(wǎng)包含x0和y+（y軸正向傳輸通道），下降子網(wǎng)包含x1和y-（y軸負(fù)向傳輸通道）。當(dāng)目的結(jié)點在發(fā)送結(jié)點的上方時，使用上升子網(wǎng)路由；當(dāng)目的結(jié)點在發(fā)送結(jié)點的下方時，使用下降子網(wǎng)路由。因此任意數(shù)據(jù)包的傳輸過程將只使用其中的一個子網(wǎng)，因而消除了環(huán)形依賴。

3）mad-y算法。double-x算法在上升子網(wǎng)和下降子網(wǎng)各只能有兩個方向的轉(zhuǎn)彎。例如當(dāng)數(shù)據(jù)包使用y+通道時，只能在下一步使用x0通道。可能仍會導(dǎo)致數(shù)據(jù)包占用虛通道資源的不平衡。mad-y算法仍然在一個維度使用兩條虛通道，但其通過限制最少的轉(zhuǎn)向策略達(dá)到免死鎖的目的，又可以根據(jù)虛通道的擁塞情況發(fā)送數(shù)據(jù)包使資源的使用較為平衡。對于double-x算法，我們可以相應(yīng)擴(kuò)展出mad-x算法：在double-x的規(guī)則上允許y-→x0方向和y+→x1方向的轉(zhuǎn)彎。此時由于在同一子網(wǎng)中仍不能形成環(huán)形依賴，因而是免死鎖的。此時算法具有更大的自適應(yīng)度。例如當(dāng)數(shù)據(jù)包將從y+轉(zhuǎn)到x方向時，可以根據(jù)擁塞情況選擇x0和x1之間的任意一個虛通道。而mad-y是mad-x算法在維度上交換的對稱算法。

4）NoP算法。LOCAL算法是一種僅考察當(dāng)前結(jié)點相鄰結(jié)點的擁塞情況的算法，在可行的發(fā)送策略中選擇最為空閑的結(jié)點發(fā)送數(shù)據(jù)包。其實現(xiàn)較簡單，但路由策略缺少全局性。NoP（Neighbors-on-Path）算法是LOCAL的一種改進(jìn)，其進(jìn)一步考慮鄰居結(jié)點的相鄰結(jié)點的擁塞情況來達(dá)到避免擁塞的目的。該算法考慮的范圍比LOCAL算法要大，其考察半徑擴(kuò)大了一倍，但未能從本質(zhì)上克服局部擁塞感知的缺點，缺乏全局性。

5）RCA算法。RCA（RegionCongestionAwareness）算法是一類算法的統(tǒng)稱：包括RCA-1D，RCA-Fanin，RCA-Quadrant等算法，都是考慮一定區(qū)域內(nèi)結(jié)點的擁塞情況而做出路由決策，通過獨立的邏輯單元收集片上網(wǎng)絡(luò)其他結(jié)點的擁塞信息。RCA-1D算法考慮當(dāng)前結(jié)點4個方向沿直線的所有結(jié)點的擁塞信息。RCA-Fanin算法用最簡單的數(shù)字邏輯按不同權(quán)重考慮整個網(wǎng)絡(luò)所有結(jié)點的擁塞情況，但其考慮的結(jié)點有冗余。RCA-Quadrant將整個網(wǎng)絡(luò)按象限劃分為獨立的單元來考慮片上網(wǎng)絡(luò)所有結(jié)點的擁塞情況，避免了冗余擁塞信息，但硬件實現(xiàn)較RCA-Fanin復(fù)雜。

6）DBAR算法。NoP算法和RCA算法在考慮結(jié)點擁塞情況時都與目的結(jié)點無關(guān)，因此會將許多無用的阻塞信息考慮其中。馬勝提出的DBAR（Destination-BasedAdaptiveRouting）算法在每個結(jié)點接收并存儲所有的與其同行及同列結(jié)點的擁塞信息。當(dāng)數(shù)據(jù)包進(jìn)行路由決策時，僅考慮位于目的結(jié)點與當(dāng)前結(jié)點之間的結(jié)點的擁塞信息，從而選擇最優(yōu)的路由路徑。

3 容錯路由算法

容錯路由算法是在存在故障的片上網(wǎng)絡(luò)實現(xiàn)正常通信的路由算法。對于可能出現(xiàn)故障的片上網(wǎng)絡(luò)，可以通過沿不同路徑重復(fù)發(fā)送相同的數(shù)據(jù)包來解決，也可以在故障結(jié)點處通過繞路發(fā)送數(shù)據(jù)包來解決。對于發(fā)送單一數(shù)據(jù)包的路由，又可以跟據(jù)對待故障的粒度分成不同的路由種類：故障塊路由。將集中的故障結(jié)點和周圍結(jié)點一起看作整個故障塊，數(shù)據(jù)包在傳送過程中沿著故障塊周圍繞行。單故障路由。將故障結(jié)點視作單個的結(jié)點看待，不考慮故障結(jié)點相連的情況。在維序路由算法的基礎(chǔ)上，遇到單個故障結(jié)點時采用在其自然輪廓上繞路的方式，為了使路由免死鎖，需修改部分繞路方式。粒度故障路由。其將片上網(wǎng)絡(luò)故障分為結(jié)點故障和鏈路故障等多種情況，因而對于路由算法的實現(xiàn)更加復(fù)雜，但可以減少片上網(wǎng)絡(luò)資源的浪費。

4 源路由算法

源路由算法主要是用于宏觀網(wǎng)絡(luò)中，通過網(wǎng)絡(luò)中結(jié)點存儲網(wǎng)絡(luò)的狀態(tài)信息，包括擁塞情況、故障情況等。當(dāng)網(wǎng)絡(luò)出現(xiàn)問題，結(jié)點向相鄰結(jié)點發(fā)送數(shù)據(jù)包，相鄰結(jié)點收到數(shù)據(jù)包后回傳一個鏈路數(shù)據(jù)包，來判斷網(wǎng)絡(luò)是否出現(xiàn)故障。如網(wǎng)絡(luò)出現(xiàn)故障，則廣播給片上網(wǎng)絡(luò)中所有結(jié)點該數(shù)據(jù)包，并更新整個網(wǎng)絡(luò)信息表。如需路由決策，則根據(jù)源節(jié)點存儲的結(jié)點信息（故障信息、延時、擁塞等）找出到目的結(jié)點間最優(yōu)路徑。源路由算法是路由決策全部完成于發(fā)送數(shù)據(jù)包的源結(jié)點。源結(jié)點將路由路徑加入數(shù)據(jù)包的頭部，網(wǎng)絡(luò)結(jié)點根據(jù)頭部的路由信息對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，不再參與路由決策。源路由算法的優(yōu)點是其在尋找路由決策的時候具有全局的鏈路信息，因此路由策略可以綜合各種信息找出最佳路徑。但其由于算法的實現(xiàn)和網(wǎng)絡(luò)信息的存儲較復(fù)雜，不適用于結(jié)點結(jié)構(gòu)簡單的片上網(wǎng)絡(luò)中。

5 結(jié)論

本文在研究片上系統(tǒng)網(wǎng)絡(luò)路由算法的發(fā)展現(xiàn)狀，對目前各類型應(yīng)用于片上網(wǎng)絡(luò)的路由算法做一個歸納和綜述。目前的片上網(wǎng)絡(luò)系統(tǒng)進(jìn)行核間通信都需要通過路由算法實現(xiàn)一條可行的路徑，由于目前片上網(wǎng)絡(luò)核心數(shù)不斷增加，優(yōu)化路由策略是提高片上網(wǎng)絡(luò)速度的重要途徑。后面將研究對源路由算法進(jìn)行研究，來提高網(wǎng)絡(luò)效率。

參考文獻(xiàn)

[1]來耀，荊明娥.基于A*算法優(yōu)化的片上網(wǎng)絡(luò)源路由算法[J].復(fù)旦學(xué)報（自然科學(xué)版），2018，57（5）：605-610.

[2]歐陽一鳴，董少周，梁華國.基于 2DMesh的NoC路由算法設(shè)計與仿真[J].計算機(jī)工程，2009（22）：227-229，235.

[3]馬勝.Cache一致性片上網(wǎng)絡(luò)路由算法和流控機(jī)制優(yōu)化關(guān)鍵技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2012.