陳中勝

摘要：隨著多核系統(tǒng)中核芯數(shù)量的增加，基于總線的系統(tǒng)在可擴(kuò)展性、平均傳輸延遲、功耗、性能等方面都受到嚴(yán)峻的挑戰(zhàn)。片上網(wǎng)絡(luò)（Network-on-Chip NoC）在這樣的背景下應(yīng)運(yùn)而生，它充分借鑒了計(jì)算機(jī)網(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ò)容錯(cuò)等等。其中片上網(wǎng)絡(luò)容錯(cuò)路算法是其中比較重要也是比較有挑戰(zhàn)的研究課題之一。本文首先簡單介紹了片上網(wǎng)絡(luò)，然后從幾個(gè)方面介紹片上網(wǎng)絡(luò)路由算法以及容錯(cuò)路由算法，最后指明容錯(cuò)路由算法一個(gè)值得研究的方向。

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.2路由算法

路由算法是片上網(wǎng)絡(luò)設(shè)計(jì)中的另一個(gè)重要研究課題。路由算法的作用是負(fù)責(zé)將數(shù)據(jù)包準(zhǔn)確地發(fā)送到目的地節(jié)點(diǎn)，除了達(dá)到這一目標(biāo)之外，一個(gè)優(yōu)秀的路由算法還需要考慮到服務(wù)質(zhì)量，也就是要盡可能選擇最短的路由路徑，盡可能地減少通信延遲，還需要很好的緩解可能出現(xiàn)的路由擁塞，實(shí)現(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àn)樗穆酚蓻Q策是可以確定或是預(yù)先計(jì)算得到的，并且它與在線運(yùn)行時(shí)的網(wǎng)絡(luò)狀態(tài)無關(guān)，也就是說這種路由算法不能很好地兼顧到路由時(shí)的網(wǎng)絡(luò)狀態(tài)，比如路由擁塞等問題。但是這種路由算法的路由路徑也不一定是確定的，因?yàn)榭梢愿鶕?jù)其他一些與網(wǎng)絡(luò)無關(guān)的變量來選擇不同的備選路徑，比如循環(huán)選擇、隨機(jī)選擇等，這些方式的引入都是為了更好的緩解路由擁塞。雖然選擇的路徑可能不同，但是這些備選路徑都是靜態(tài)的，都是可以在離線就進(jìn)行計(jì)算好的，所以這種路由算法也還是可以稱為靜態(tài)路由算法。

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

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

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

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

2.2.2容錯(cuò)路由算法

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

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

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

3容錯(cuò)路由算法展望

3.1 動機(jī)

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

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

3.2 展望

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

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

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

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

4總結(jié)

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

參考文獻(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)編輯：梁書】