陳中勝

摘要：隨著多核系統(tǒng)中核芯數(shù)量的增加，基于總線(xiàn)的系統(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)的研究課題之一。本文首先簡(jiǎn)單介紹了片上網(wǎng)絡(luò)，然后從幾個(gè)方面介紹片上網(wǎng)絡(luò)路由算法以及容錯(cuò)路由算法，最后指明容錯(cuò)路由算法一個(gè)值得研究的方向。

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）12-0012-03

1 引言

片上系統(tǒng)指的是集成在一個(gè)芯片上完整的多核系統(tǒng)以及通信系統(tǒng)，隨著技術(shù)的完善和半導(dǎo)體工藝的發(fā)展，片上系統(tǒng)能夠包含多個(gè)處理器、存儲(chǔ)器模擬電路等眾多元器件和子系統(tǒng)[1]。但是隨著集成的核心數(shù)量的不斷增加，傳統(tǒng)的總線(xiàn)式通信架構(gòu)會(huì)遭遇到嚴(yán)重的面積開(kāi)銷(xiāo)和性能問(wèn)題，這就亟須一種適用于超大規(guī)模片上系統(tǒng)的通信架構(gòu)來(lái)替代傳統(tǒng)的總線(xiàn)式結(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)直接相連。其中路由器與路由器之間、路由器與處理器之間通過(guò)雙向鏈路連接。

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è)重要問(wèn)題，拓?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ò)的通信效率與性能。

最為常見(jiàn)的拓?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)之間通過(guò)雙向鏈路連接，每個(gè)路由器節(jié)點(diǎn)連接一個(gè)本地處理器。

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

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

如圖4所示，胖樹(shù)拓?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)上可能會(huì)造成嚴(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路由算法分類(lèi)

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

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

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

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

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

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

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

2.2.2容錯(cuò)路由算法

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

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

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

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

3.1 動(dòng)機(jī)

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

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

3.2 展望

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

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

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

以上種種觀(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)，通過(guò)路由算法與網(wǎng)絡(luò)狀態(tài)的關(guān)系，本文對(duì)片上網(wǎng)絡(luò)的路由算法進(jìn)行一個(gè)大致的分類(lèi)，并詳細(xì)介紹不同路由算法的路由特點(diǎn)以及各自的局限性的優(yōu)越性。然后介紹了容錯(cuò)路由算法以及其局限性，并介紹了需要在超大規(guī)模片上網(wǎng)絡(luò)中容忍眾多故障的動(dòng)機(jī)，最后提出了一個(gè)使用圖論來(lái)進(jìn)行超大規(guī)模片上網(wǎng)絡(luò)中容錯(cuò)眾多故障的路由算法的研究方向，并通過(guò)理論論證了其可行性與優(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)編輯：梁書(shū)】