片上網(wǎng)絡非適應性路由算法研究

李天陽，潘能智，屈凌翔

（中國電子科技集團公司第58研究所，江蘇 無錫 214035）

1 引言

近十年來，由于摩爾定律的發(fā)展遇到了工藝和生產(chǎn)成本的限制[1]，許多片上系統(tǒng)（SoC）為了在單芯片上集成更高的運算能力，同時也為了縮短芯片的面市時間（TTM，Timing To Market），通過集成IP的方法來構建多處理器芯片[2]。當前集成多核芯片的主要方法是通過總線互聯(lián)，這在小規(guī)模如雙核、四核、八核等芯片上具有結構簡單且能達到單周期存取數(shù)據(jù)的要求[1]。但是，總線結構由于其總線帶寬的限制，可擴展性不高，且當數(shù)據(jù)流量過高時，也會產(chǎn)生平均通信效率低下的問題。因此，近年來人們提出了一種類似計算機網(wǎng)絡的方法將處理器進行互聯(lián)的硬件結構，并稱之為片上網(wǎng)絡（NoC，Network on Chip），使多核處理器系統(tǒng)的通信效率、吞吐量和可擴展性有了本質的飛躍。片上網(wǎng)絡結構處理器目前已經(jīng)廣泛用于超級計算機和分布式計算等領域。NoC互聯(lián)結構或可成為下一代超大規(guī)模集成電路的主流[3]。

片上網(wǎng)絡體系結構包括網(wǎng)絡拓撲、協(xié)議設計、路由算法、流量控制、仲裁、服務質量（QoS）和差錯管理等方面。其中路由算法和流量控制是判斷某個NoC網(wǎng)絡好壞的兩個關鍵因素[4]。

路由算法負責在網(wǎng)絡拓撲結構中從源節(jié)點到目的節(jié)點進行路徑選擇。在一個NoC網(wǎng)絡中，路由算法的選擇非常嚴格。一個好的路由算法在網(wǎng)絡信道中可以起到平衡負載的作用，即使是在像隨機序列通信這樣的非標準通信模式下，信道負載越平衡，網(wǎng)絡的吞吐量就越理想。但是當前的路由器并沒有進行很好的負載平衡。通常，節(jié)點之間的通信取決于某條預先設定的路徑。在這種路由算法下，非標的通信模式會在次優(yōu)的吞吐量下發(fā)生巨大的負載失衡。選擇這些路由的原因在于大多數(shù)路由器都是以最短路徑作為設計目標[5]。一個好的路由算法也應該保持路徑長度盡可能地短，并且減少經(jīng)過的節(jié)點數(shù)以減少數(shù)據(jù)的總體延時。通常，路由最小化（通常選擇最短路徑）在平衡負載和吞吐量上會相互沖突[6]。

本文總結了常見的路由算法，介紹了無關性路由算法并對其進行分析比較，其中主要分析了非適應性的路由算法，因為其具有結構簡單、容易實現(xiàn)和能預防死鎖的優(yōu)點，因此被大多數(shù)片上網(wǎng)絡系統(tǒng)所使用。

2 路由方法分類

按照如何選擇從源節(jié)點x到目的節(jié)點y可能的路徑集Rxy的方式來分類不同的路由算法。使用路由關系R和選擇函數(shù)ρ來代替路由算法。R返回一組路徑（或信道），ρ在這些路徑（或信道）之間進行選擇。分割算法，和信道依賴以及死鎖都與R相關，而適應性與ρ相關。

定義R為以下3種方式[8]：

其中ρ(X)指定了冪集，或X的所有子集。這種記法表明，路由關系可能會返回多條路徑(或信道)，且由選擇函數(shù)選擇這些結果中的一個。

當路由關系的輸出是所有路徑，如式（1）所示，路由算法又表示為一次路由（all-at-once routing）。當數(shù)據(jù)包從節(jié)點x到節(jié)點y進入網(wǎng)絡時，路由關系為：U=R(x,y)。由于U有可能是路由的集合，因此只選擇其中一個賦值給數(shù)據(jù)包。U不必包含所有可能的路由集合R’xy，甚至不必包含所有的最小路由集合Rxy。在確定性路由算法的情況下，只返回一個結果（|U|=1）。一旦路由被指定，就被保存在數(shù)據(jù)包中。一次路由可以最小化每個包計算路由關系的時間，但這需要在數(shù)據(jù)包內增加額外的路由開銷。

另一種方案是增長路由[7]，其路由關系返回一組可能的信道。與一次路由不同，增長路由并不是一次性返回全部路徑，而是每到一個中繼節(jié)點才計算一次，如式（2）所示。例如，路由關系的輸入為數(shù)據(jù)包的當前節(jié)點ω和目的節(jié)點y。通過計算得到一組信道：D=R(ω,y)，其中D的每個元素都是一條源于ω的輸出信道或ωOCD?。選擇函數(shù)用來從D來的數(shù)據(jù)包選擇下一條信道，并且這種增長的過程一直重復到數(shù)據(jù)包到達其目的節(jié)點為止。

第三種關系（式（3））也是類似的增長方法，唯一的區(qū)別是函數(shù)的輸入是歷史數(shù)據(jù)包使用的信道和其目的節(jié)點，即使用歷史信道c的信息而不是節(jié)點本身，由于信道c已經(jīng)提供了足夠的歷史信息來去除信道間的依賴和耦合，這可以避免死鎖[11]的發(fā)生。

3 確定性路由算法[8]

確定性路由算法是最簡單的路由算法，它在x和y之間即便可能存在多條路徑（|Rxy|〉1）的情況下也只選擇固定的一條路徑，故而稱為確定性路由算法。

確定性路由算法忽略了當前拓撲結構路徑的多樣化，在負載平衡的優(yōu)化上表現(xiàn)很差。每個確定性路由算法都存在一種通信模式可以產(chǎn)生巨大的負載失衡。但是，這類算法有著非常簡單且容易實現(xiàn)的優(yōu)點，而且不會產(chǎn)生路由死鎖。確定性路由算法在項目中曾被廣泛使用，即使在現(xiàn)在也能在很多片上網(wǎng)絡項目中使用確定性路由算法。尤其是對于不規(guī)則的網(wǎng)絡拓撲而言，設計一個好的隨機化或適應性路由在不規(guī)則網(wǎng)絡拓撲下非常困難。最流行的確定性路由算法是目標標記路由和維度排序路由算法。

3.1 目標標記路由

在一個k路n級（k-ary n-fly，即有n級路由，每級路由有k個輸出通路）的蝶式網(wǎng)絡拓撲[23]結構中，目標地址表示為n位k進制的數(shù)。地址的每一位都用來依次選擇每級路由的輸出通路，就像是轉發(fā)的路由表一樣。圖1表示了2路3級的蝶式拓撲下目標標記路由算法[9]的尋路過程。

從節(jié)點3到節(jié)點5，從左到右傳輸目標地址轉換成二進制，5=1012=下，上，下。算法沒有用到源節(jié)點的信息，因為無論從哪個節(jié)點出發(fā)，用101的模式都能到達節(jié)點5。因此，目標標記的路由方法只依賴于目標的地址，與起始地址無關。

3.2 維度排序路由

維度排序路由又叫e立方路由[10]，是目標標記路由算法在a路b維網(wǎng)絡（tori和meshes）[11]的模擬。和目標標記算法類似，目標地址表示為k進制數(shù)的每一位都用來指示路由尋址。不同點是每一位不是用來選擇輸出通路，而是用來選擇在指定立方體下的路由節(jié)點。與蝶式拓撲網(wǎng)絡不同，立體網(wǎng)絡可能在處理每一位數(shù)字時需要多次跳轉才能到下個數(shù)字。以多維（torus[12]）拓撲網(wǎng)絡為例，其每個維度都可以順時針或者逆時針遍歷，因此e立方路由的第一步就是計算每個維度最短的（或者其他優(yōu)先的）方向。為了找到優(yōu)先的方向，先要計算每一位源和目標數(shù)字i相關的地址Δi：

這可以用來計算優(yōu)先的方向：

其中T表示函數(shù)是環(huán)形（tori）網(wǎng)絡的。一旦優(yōu)先方向向量被計算出來后，數(shù)據(jù)包就被轉發(fā)到下一層，直到其到達目的節(jié)點。

圖1 從節(jié)點3到節(jié)點5的路由過程

一般而言維度排序路由的負載平衡性質很差，但是仍然被廣泛用于高路多維（mesh和torus）的網(wǎng)絡結構[18]。首先維度排序路由很容易實現(xiàn)，而且允許路由以維度進行切分或跨維度分割。其次，這種算法通過預防在不同維度間回環(huán)，從而避免死鎖的問題。不過，在一個維度內還是有可能造成死鎖。

4 無關性路由算法[13]

無關性路由（oblivious routing），是指在傳輸數(shù)據(jù)包的時候不考慮網(wǎng)絡當前狀態(tài)的路由算法。這種算法非常容易實現(xiàn)和分析，加入網(wǎng)絡狀態(tài)信息可以提高路由性能，但同時也加入了相當大的復雜性，如果不小心處理，反而會導致性能下降。無關性路由算法主要有隨機化路由算法、最小無關路由算法和負載平衡路由算法等。

4.1 Valiant隨機化路由算法

Valiant隨機化路由算法[14]是一種部分隨機的算法。當數(shù)據(jù)包從s傳輸?shù)絛時，首先從s傳輸?shù)揭粋€隨機選擇的終端節(jié)點x，然后從x傳輸?shù)絛。這兩步中可以使用任意的路由算法，此算法在標準通信中可得到最好的平衡負載效果。不考慮初始的通信模式，Valiant算法的每一步都是標準隨機通信。因此Valiant算法避免了網(wǎng)絡中不均衡網(wǎng)絡流量和熱點（hot spot）[24]的產(chǎn)生。

Valiant算法具有最好與最壞的性能邊界。以k路n級的網(wǎng)絡為例，在n的每個維度中，隨機的兩步中的每一步的平均距離都是k/4，總的跳數(shù)為nk/2。因此每次鏈接平均的負載為γ=k/4。吞吐量為4b/k，在實踐中幾乎是最優(yōu)的。在旋風通信（tornado traffic）[19]的情況下，每個數(shù)據(jù)包必須經(jīng)過H=n(k/2-1)次跳轉。信道負載在任何路由算法下至少為：

當k增加的時候，Valiant算法引起的信道平衡接近理想情況，因此Valiant算法是漸進最優(yōu)的。在最壞通信的情況下（如tornado 旋風通信[19]），Valiant算法有良好的性能，這是以犧牲本地性為代價的[15]，因為在兩步中加入了隨機化和額外的工作量。在某些模式中，如鄰近通信（nearest neighbor traffic），每個數(shù)據(jù)包一般只要求中繼一次，使用Valiant算法卻仍需兩步，將跳轉數(shù)從H=1提高到了nk/2，且降低了吞吐量。

4.2 最小無關路由算法

最小無關（minimal oblivious）路由算法[16]嘗試通過將路由限制為最?。ㄗ疃搪窂剑?，以在不丟失本地性的情況下來達到隨機化路由算法的負載平衡。非最小無關路由算法可能選擇任何R’xy中的路徑來將數(shù)據(jù)包從x傳輸?shù)統(tǒng)，而最小無關路徑嚴格選擇路徑Rxy。對于層次拓撲而言，最小無關路由算法工作得非常好，在保證本地性的同時也有良好的負載平衡性。

對比而言，在旋風通信的順時針下所有最小化算法都給出了至少γ=k/2-1的信道負載，在逆時針則是0。由于這樣的負載不平衡性，吞吐量最多只能達到因此沒有一種最小無關路由算法能達到Valiant算法最差情況下吞吐量的一半。

4.3 負載平衡無關路由算法

完全隨機化路由（Valiant）算法和最小無關路由算法中有時需要取一個折中的方法，即負載平衡無關路由算法[17]，其在torus中通過隨機選擇象限（quadrant）來進行輸入。通過距離來給象限的選擇賦權，能精確地平衡旋風通信的負載。在每個維度i下，以的概率選擇較短的方向D’i=Di，以Δi/k的概率選擇較長的方向D’i=-Di。一旦選擇了方向向量D’，就可以像最小無關路由一樣輸入到選擇的象限中。在象限中隨機選擇一個中間節(jié)點，并路由經(jīng)過該節(jié)點，然后再傳輸?shù)侥康牡?。對于路由的每一步來說，維度順序都是隨機選擇的。

5 非適應性路由算法比較

非適應性路由算法在進行路由選擇時不關心當前路由網(wǎng)絡的實際流通狀態(tài)，因此其結構簡單，易于在單芯片中實現(xiàn)。在實際中可能通過對已有路由拓撲結構加載已經(jīng)開發(fā)的標準測試通信向量，并對其加載向量后整個網(wǎng)絡的通信歸一化波特率加以分析，可以得到非適應性路由算法之間的一個比較。常用的測試通信模式有“鄰近通信模式”、“單一通信模式”、“位互補通信模式”、“轉置通信模式”[18]、“旋風通信模式”[19]與“最大負載通信模式”[20]。表1通過對一個8路2維立方[21]節(jié)點路由拓撲結構的模擬，比較了維度路由、隨機路由、最小無關路由、與負載平衡無關4種路由算法。因目標標記路由主要針對蝶形拓撲結構，在這里不適合與其他非適應性路由算法進行對比。各種算法測試結果如表1所示[22]。

表1 使用不同負載模式對一個8路2維立方路由拓撲進行測試得到的網(wǎng)絡歸一化吞吐量

從表1的值可以看出，在不同的負載方式下各個路由算法所表現(xiàn)出來的吞吐量有著較大的差異。因此不存在一個絕對優(yōu)良的算法可以在每種通信模式下都表現(xiàn)出較大的吞吐量。例如在鄰近通信模式情況下，負載平衡無關路由算法的表現(xiàn)勝過Valiant算法（這是因為其更頻繁地通過較短路徑傳輸），但是其表現(xiàn)卻不如最小無關路由算法（這是因為有一部分數(shù)據(jù)傳輸不是通過最小象限的）。雖然負載平衡無關路由在旋風通信下表現(xiàn)優(yōu)異，但其最壞情況下的吞吐量卻遠低于Valiant算法。

6 小結

本文主要介紹了幾種非適應性的路由算法。由于適應性路由算法在實踐中往往太過復雜，芯片實施的代價（實現(xiàn)、面積、功耗等因素）很大，對性能的提升效果也不明顯，因此大多數(shù)片上網(wǎng)絡架構都使用非適應性路由算法[22]。Valiant隨機化路由算法完全平衡了任何通信模式下的負載，然而這樣的平衡性卻是以破壞本地性為代價。最小無關路由算法則相反，其保持了本地性，提高了在所有模式平均狀態(tài)下的網(wǎng)絡吞吐量。但是在多維（torus）網(wǎng)絡中，任何最小無關路由算法最多只能提供最壞通信情況下的Valiant算法的一半吞吐量。負載平衡無關路由算法提供了上述兩種算法的一種折中，既考慮了負載平衡也考慮了本地性，但其最壞情況下的吞吐量卻遠低于Valiant算法。因此在選擇非適應路由算法時，需要著重考慮目標NoC芯片的應用場景的通信模式，依照目標應用場景模式才可以選出適合于具體工程要求的路由算法。

[1] Semiconductors Industry Association. International technology road map for semiconductors,World semiconductors[C]. World Semiconductor Council, 1999.

[2] 馬關勝，馮剛. SoC設計與IP核重用技術[M]. 北京：國防工業(yè)出版社，2006.

[3] W J Dally, C L Seitz. The Torus Routing Chip[M].Technical Report 5208: TR: 86, Computer Science Dept,California Inst. Of Technology, 1986. 1-19.

[4] Axel Jantsch, Hannu Tenhunen. Networks on Chip[M].Kluwer Academic Publishers, 2003. 87-88.

[5] J Hu, R Marculescu. Exploiting the routing flexibility for energy/performance aware mapping of regular NoC architectures[M]. In Proc. DATE, March 2003.

[6] S Murali, G De Micheli. SUNMAP: A tool for automatic topology selection and generation for NoCs[M]. In Proc. DAC, June 2004.

[7] K Srinivasan, KS Chatha, G Konjevod. Linear programming based techniques for synthesis of Network-on-Chip architectures[M]. In Proc. ICCD,Oct 2004.

[8] Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks[J]. IEEE Tran.-on -Computers, 1993, 23 (2): 62-76.

[9] Kariniemi H, Nurmi J. Arbitration and routing schemes for onchippacket networks[C]. Interconnect-Centric Design for AdvancedSoC and NoC,2005. 253-282.

[10] R E Kessler, J L Schwarzmeier. Cray T3D: a new dimension for Cray Research[C]. In Proc. Of the IEEE Computer society International Conference (COMPCON),Feb. 1993. 11176-182.

[11] Charles L Setiz. Deadlock free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987, 36(5): 546-553.

[12] Steven L Scott, Greg Thorson. Optimized routing in the Cray T3D[M]. In proc. Of the First International Parallel Computer Routing and Communication Workshop,Seattle, May 1994. 281-294.

[13] Jose Duato. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(6): 841-854.

[14] D H Lawrie. Access and alignment of data in an array processor[J].IEEE Transactions on Computers,1975, 24:1145-1155.

[15] Harold S Stone. Parallel processing with the perfect shuffle[J]. IEEE Transactions on Computers,1971, 20(2):153-161.

[16] Allan Borodin, John E Hopcroft. Routing, merging,and sorting on parallel models of computation[J]. Journal of Computer and System Sciences, 1985, 30: 130-145.

[17] L G Valiant, G J Brebner. Universal schemes for parallel communication[M]. In Proc. Of the ACM Symposium of the Theory of Computing, Milwaukee, Minn, 1981. 263-277.

[18] Ted Nesson, S Lennart Johnsson. ROMM routing on mesh and torus networks[M]. In Proc. of the Symposimu on Parallel Algorithms and Architectures, Santa Barbara, CA, 1995. 275-287.

[19] Arjun Singh, William J Dally, Brian Towles, Amit K Gupta. Locality-preserving randomized oblivious routing on torus networks[M]. In Proc. Of the Symposium on Parallel Algorithms and Architectures, Winnipeg, Manitoba,Canada, Aug. 2002. 9-19.

[20] Brian Towles, William J Dally. Worst-case traffic for oblivious routing functions[M]. In Proc. Of the Symposium on Parallel Algorithms and Architecture, Winnipeg,Manitoba, Canada, Aug. 2002. 1-8.

[21] H Sullivan, T R Bashkow. A large scale, homogeneous,fully distributed parallel machine[M]. In proc Of the International Symposium on Computer Architecture, March 1977. 105-124.[22] W J Dally, B Towles. Principles and Practices of Interconnection Networks[M]. Morgan Kaufmann publishers, 2004. 182.

[23] Charles E Leiserson, Zahi S Abuhamdeh, David C Douglas, Carl R Feynman, Mahesh N Ganmukhi, Jeffrey V Hill, W Daniel Hillis, Bradley C Kuszmaul, Margaret A St Pierre, David S Wells, Monica C Wong-chan, Shaw-Wen Yang, Robert Zak. The network architecture of the Connection Machine CM-5[J]. Journal of Parallel and Distributed Computing, 1996, 33(2): 145-158.

[24] Ni L M, McKinley P K. A survey of wormhole routing techniques in direct networks[J]. IEEE Tran.-on -Computers, 1993, 23 (2): 62-76.