片上網(wǎng)絡(luò)容錯路由算法的綜述與展望

陳中勝

摘要：隨著多核系統(tǒng)中核芯數(shù)量的增加，基于總線的系統(tǒng)在可擴展性、平均傳輸延遲、功耗、性能等方面都受到嚴(yán)峻的挑戰(zhàn)。片上網(wǎng)絡(luò)（Network-on-Chip NoC）在這樣的背景下應(yīng)運而生，它充分借鑒了計算機網(wǎng)絡(luò)中的通信思想，并且很好的考慮了片上系統(tǒng)（System On Chip，SoC）的特性，是一種適用于片上系統(tǒng)的通信架構(gòu)。隨著片上網(wǎng)絡(luò)的提出，相關(guān)的研究也日益發(fā)展，比如片上網(wǎng)絡(luò)拓?fù)?，通信服?wù)質(zhì)量、片上網(wǎng)絡(luò)路由算法、片上網(wǎng)絡(luò)容錯等等。其中片上網(wǎng)絡(luò)容錯路算法是其中比較重要也是比較有挑戰(zhàn)的研究課題之一。本文首先簡單介紹了片上網(wǎng)絡(luò)，然后從幾個方面介紹片上網(wǎng)絡(luò)路由算法以及容錯路由算法，最后指明容錯路由算法一個值得研究的方向。

關(guān)鍵詞：片上網(wǎng)絡(luò)；容錯路由算法；圖論

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）12-0012-03

1 引言

片上系統(tǒng)指的是集成在一個芯片上完整的多核系統(tǒng)以及通信系統(tǒng)，隨著技術(shù)的完善和半導(dǎo)體工藝的發(fā)展，片上系統(tǒng)能夠包含多個處理器、存儲器模擬電路等眾多元器件和子系統(tǒng)[1]。但是隨著集成的核心數(shù)量的不斷增加，傳統(tǒng)的總線式通信架構(gòu)會遭遇到嚴(yán)重的面積開銷和性能問題，這就亟須一種適用于超大規(guī)模片上系統(tǒng)的通信架構(gòu)來替代傳統(tǒng)的總線式結(jié)構(gòu)。

在這種背景下，2001年，片上網(wǎng)絡(luò)被研究機構(gòu)提出。片上網(wǎng)絡(luò)主要目標(biāo)就是追求高質(zhì)量的片內(nèi)通信，它的設(shè)計借鑒了計算機網(wǎng)絡(luò)中的成熟的通信思想，結(jié)合片上系統(tǒng)的電氣特性，一經(jīng)提出，就受到眾多研究機構(gòu)的關(guān)注與進(jìn)一步研究。

一個典型的片上網(wǎng)絡(luò)如圖1所示，每個路由節(jié)點連接一個本地處理器，且直接與兩個到四個鄰居路由器節(jié)點直接相連。其中路由器與路由器之間、路由器與處理器之間通過雙向鏈路連接。

2片上網(wǎng)絡(luò)拓?fù)渑c路由算法

2.1片上網(wǎng)絡(luò)拓?fù)?/p>

片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是片上網(wǎng)絡(luò)需要研究的一個重要問題，拓?fù)浣Y(jié)構(gòu)指的片上系統(tǒng)內(nèi)部各個節(jié)點之間以何種方式進(jìn)行排列和連接。拓?fù)浣Y(jié)構(gòu)直接決定了片內(nèi)各節(jié)點以何種方式進(jìn)行通信，也就能夠在很大程度上決定了片上網(wǎng)絡(luò)的通信效率與性能。

最為常見的拓?fù)浣Y(jié)構(gòu)是2D Mesh[2]，如圖2所示，這種結(jié)構(gòu)最容易被理解，也是最容易在硬件上實現(xiàn)的一種拓?fù)浣Y(jié)構(gòu)。在這種拓?fù)浣Y(jié)構(gòu)中，路由器節(jié)點呈矩形排列，相鄰節(jié)點之間通過雙向鏈路連接，每個路由器節(jié)點連接一個本地處理器。

這種結(jié)構(gòu)的優(yōu)點是簡單且易于實現(xiàn)，缺點是邊界的節(jié)點沒有形成一個閉環(huán)，這會導(dǎo)致某些路由需要較長的路由路徑。

為了解決這種局限性，二維花托拓?fù)浣Y(jié)構(gòu)（Torus）[3]被提出。如圖3所示這種結(jié)構(gòu)是一種對2D Mesh的改進(jìn)，通過在邊界增加一個長的環(huán)路來連接邊界節(jié)點，這樣就可以保證每個節(jié)點都是對稱的，可以盡量減少傳輸路徑，緩解路由擁塞。這種結(jié)構(gòu)的缺點也顯而易見，它增加了布線的復(fù)雜度，大大提高的實現(xiàn)的難度。

如圖4所示，胖樹拓?fù)洌╢at tree）[4]是一種能夠?qū)崿F(xiàn)極少通信延遲的拓?fù)浣Y(jié)構(gòu)，在這種結(jié)構(gòu)中，每個處理器節(jié)點與其他節(jié)點之間的路由路徑都相等，這種結(jié)構(gòu)的缺點就是，在根路由器節(jié)點上可能會造成嚴(yán)重的路由擁塞。

2.2路由算法

路由算法是片上網(wǎng)絡(luò)設(shè)計中的另一個重要研究課題。路由算法的作用是負(fù)責(zé)將數(shù)據(jù)包準(zhǔn)確地發(fā)送到目的地節(jié)點，除了達(dá)到這一目標(biāo)之外，一個優(yōu)秀的路由算法還需要考慮到服務(wù)質(zhì)量，也就是要盡可能選擇最短的路由路徑，盡可能地減少通信延遲，還需要很好的緩解可能出現(xiàn)的路由擁塞，實現(xiàn)負(fù)載均衡。

2.2.1路由算法分類

路由算法的種類繁多，根據(jù)不同的分類標(biāo)準(zhǔn)也可以對其進(jìn)行多種分類，本文中根據(jù)路由決策與網(wǎng)絡(luò)狀態(tài)的關(guān)系將路由算法分為靜態(tài)路由算法與動態(tài)路由算法。

2.2.1.1靜態(tài)路由算法

靜態(tài)路由算法也可以叫作確定性路由算法或無關(guān)路由算法，因為它的路由決策是可以確定或是預(yù)先計算得到的，并且它與在線運行時的網(wǎng)絡(luò)狀態(tài)無關(guān)，也就是說這種路由算法不能很好地兼顧到路由時的網(wǎng)絡(luò)狀態(tài)，比如路由擁塞等問題。但是這種路由算法的路由路徑也不一定是確定的，因為可以根據(jù)其他一些與網(wǎng)絡(luò)無關(guān)的變量來選擇不同的備選路徑，比如循環(huán)選擇、隨機選擇等，這些方式的引入都是為了更好的緩解路由擁塞。雖然選擇的路徑可能不同，但是這些備選路徑都是靜態(tài)的，都是可以在離線就進(jìn)行計算好的，所以這種路由算法也還是可以稱為靜態(tài)路由算法。

這種路由算法一般計算較為簡單，可以在線進(jìn)行路由計算，也可以在離線時就把所有路由決策計算好，然后在線通過離線計算得到的路由表進(jìn)行路由決策?；诼酚杀淼穆酚伤惴ㄔ诰€路由計算一般會比不急于路由表的路由算法的在線路由計算要簡單高效，但是由于需要在硬件中存儲一張路由表，雖有他的缺點也顯而易見，就是會造成更大的面積開銷。

2.2.1.2動態(tài)路由算法

動態(tài)路由算法與靜態(tài)路由算法不同，這種路由算法的路由決策會在片上網(wǎng)絡(luò)在線運行時，除了根據(jù)數(shù)據(jù)包的源點和目的地，還會綜合考慮片上網(wǎng)絡(luò)的擁塞程度、溫度、功耗等狀態(tài)來進(jìn)行路由決策。這種路由算法相較于靜態(tài)路由算法能夠更好地提升片上網(wǎng)絡(luò)的路由性能，緩解路由擁塞，實現(xiàn)負(fù)載均衡。但是缺點也是顯而易見的，要實現(xiàn)這些狀態(tài)的綜合考量，就必須要實現(xiàn)對應(yīng)的狀態(tài)檢測機制，這就往片上系統(tǒng)中加入需要額外的硬件。在本來就對面積開銷的要求苛刻的片上系統(tǒng)中，這無疑會造成嚴(yán)重的挑戰(zhàn)。

除此之外，綜合考慮狀態(tài)來進(jìn)行路由決策就會對增加路由算法的復(fù)雜度與實現(xiàn)難度，這也可會導(dǎo)致增加片上網(wǎng)絡(luò)的開銷和功耗。

2.2.2容錯路由算法

片上網(wǎng)絡(luò)系統(tǒng)由于自身電器特性以及元器件的老化，可能會導(dǎo)致節(jié)點、鏈路或其他元器件發(fā)生。在某些情況下，直接修復(fù)或替換這些故障元器件難度和成本過高，因此，片上網(wǎng)絡(luò)需要有容錯能力，以保證即使存在故障，片上網(wǎng)絡(luò)也可以以盡可能小的影響正常工作。

容錯相關(guān)技術(shù)是片上網(wǎng)絡(luò)的重要支撐技術(shù)之一[5]，在路由算法層面，路由由于可以選擇不同的路由路徑來繞過故障的鏈路或節(jié)點，因此，只要對路由算法加以改進(jìn)，就可以實現(xiàn)有很好效果的容錯路由算法。

通過容錯路由算法容忍故障的優(yōu)點是可以無須或盡可能小的增加片上系統(tǒng)的面積開銷，就可以實現(xiàn)對故障的容忍。缺點是由于需要加入對于故障的判斷和容忍故障的路由計算，會導(dǎo)致算法的設(shè)計和實現(xiàn)較為復(fù)雜，路由路徑不一定能選擇最短路徑，這就會導(dǎo)致更高的路由延遲，也就會影響片上網(wǎng)絡(luò)的通信效率。

3容錯路由算法展望

3.1 動機

傳統(tǒng)的片上網(wǎng)絡(luò)規(guī)模較小，故障鏈路的數(shù)量也較小。而業(yè)界也普遍在片上網(wǎng)絡(luò)中認(rèn)為發(fā)生單個故障的可能性就已經(jīng)很低了，所以目前的大多數(shù)關(guān)于片上網(wǎng)絡(luò)路由算法的研究工作都是針對單故障展開的，但是隨著制造和繼承工藝的不斷發(fā)展和新的架構(gòu)的提出，超大規(guī)模片上網(wǎng)絡(luò)的實現(xiàn)已經(jīng)越來越成為可能甚至已經(jīng)被設(shè)計和實現(xiàn)。

Sunway TianHuLight超級計算機[6]，繼承了260個核芯，采用的是晶圓級的片上網(wǎng)絡(luò)架構(gòu)設(shè)計，整個芯片面積僅為25平方厘米。由于它本身的電器特性和硬件老化會導(dǎo)致發(fā)生故障的可能性增加，而且這種設(shè)計要求極高的硬件集成和制造成本，一旦發(fā)生故障，無法對故障元器件進(jìn)行替換和修復(fù)，也不能直接棄用整塊芯片，這就需要有針對可能發(fā)生眾多故障的超大規(guī)模片上系統(tǒng)的容錯路由算法，來保證片上系統(tǒng)在存在多個故障時也能正常運行，并且對不可用的節(jié)點和鏈路進(jìn)行棄用，從而可以降級使用片上系統(tǒng)。

3.2 展望

片上網(wǎng)絡(luò)的結(jié)構(gòu)可以抽象為節(jié)點與雙向鏈路的組合，這可以很好的用數(shù)學(xué)中的圖來進(jìn)行抽象，于是可以將片上網(wǎng)絡(luò)抽象成一張有向圖，圖中的節(jié)點對應(yīng)的就是片上網(wǎng)絡(luò)中的路由器節(jié)點，圖中的有向邊對應(yīng)的就是片上網(wǎng)絡(luò)中的鏈路，針對故障，我們可以刪除圖中對應(yīng)的節(jié)點或是鏈路。于是我們可以將片上網(wǎng)絡(luò)的路由算法和容錯算法轉(zhuǎn)化為圖論中的問題來處理，比如尋找路由路徑就可以看作是對圖進(jìn)行搜索，找到兩個節(jié)點之間的最短路徑，由于已經(jīng)刪除了故障節(jié)點和故障鏈路，那么容錯算法也就自然而然地被實現(xiàn)了，且可以容忍數(shù)量眾多故障。

對于眾多故障導(dǎo)致的節(jié)點可能不連通的情況，我們可以使用最大強連通分量的概念來對片上網(wǎng)絡(luò)中的不連通節(jié)點進(jìn)行棄用，從而降級使用片上網(wǎng)絡(luò)，保證在眾多故障發(fā)生的情況下片上網(wǎng)絡(luò)還可正常工作。

使用圖論來解決片上網(wǎng)絡(luò)容錯容錯路由算法還有一個優(yōu)點就是無須考慮片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，無論是2D、3D、Torus、異構(gòu)等等拓?fù)浣Y(jié)構(gòu)。因為在圖中，只需要考慮節(jié)點與邊的關(guān)系，而無須考慮它們是如何排列的。

以上種種觀點都能充分表明圖論是解決超大規(guī)模片上網(wǎng)絡(luò)中容忍眾多故障的一個有前景的研究方案。

4總結(jié)

本文介紹了片上網(wǎng)絡(luò)的相關(guān)概念，并總結(jié)了片上網(wǎng)絡(luò)的幾種典型的拓?fù)浣Y(jié)構(gòu)以其其各自的優(yōu)缺點，通過路由算法與網(wǎng)絡(luò)狀態(tài)的關(guān)系，本文對片上網(wǎng)絡(luò)的路由算法進(jìn)行一個大致的分類，并詳細(xì)介紹不同路由算法的路由特點以及各自的局限性的優(yōu)越性。然后介紹了容錯路由算法以及其局限性，并介紹了需要在超大規(guī)模片上網(wǎng)絡(luò)中容忍眾多故障的動機，最后提出了一個使用圖論來進(jìn)行超大規(guī)模片上網(wǎng)絡(luò)中容錯眾多故障的路由算法的研究方向，并通過理論論證了其可行性與優(yōu)點。

參考文獻(xiàn)：

[1] W.J. Dally and B. Towles， "Route packets， not wires： On-chip interconnection networks[J]，" in Proc. DAC， 2001， pp. 684-689.

[2] S.Kumar， A.Jantschl，J.P.Soininen，etc.A Network on Chip Architecture and Design Methodology[A].Proceeding of the IEEE Computer Society Annual Symposium on VLSI[C]，April 2002：105-112.

[3] M.Mirza-Aghatabar，S.Koohi，S.Hessabi，M.Pedram.An Empirical Investigation of Mesh and Torus NoC Topologies Under Different Routing Algorithms and Traffic Models.10th Euromicro Conference on Digital System Design Architectures，Methods and Tools.Aug.2007：19-26.

[4] Zhang Shengbing，Wang Jing，Pan Yongfeng.Analysis of Network on Chip Based on Longtium SoC.International Conference on Embedded Software and Systems Symposia[C].July.2008：243-247.

[5] L.enini G. De Micheli. Networks on chips： a new SoC paradigm IEEE Computer Vol. 35 No.1 Jan.2002，pp.70-80.

[6] J. Dongarra， "Report on Sunway TaihuLight System"， Oak Ridge National Laboratory， Jun. 2016.

【通聯(lián)編輯：梁書】