片上網(wǎng)絡(luò)：新一代的片上系統(tǒng)結(jié)構(gòu)*

劉炎華，劉 靜，賴宗聲

（華東師范大學(xué) 微電子電路與系統(tǒng)研究所，上海 200062）

片上網(wǎng)絡(luò)：新一代的片上系統(tǒng)結(jié)構(gòu)*

劉炎華，劉 靜，賴宗聲

（華東師范大學(xué) 微電子電路與系統(tǒng)研究所，上海 200062）

片上系統(tǒng)是使用共享或?qū)Ｓ每偩€作為芯片的通信資源。由于這些總線具有一定的限制，因此擴(kuò)展性較差，不能滿足發(fā)展需求。在這種情況下，目前的片內(nèi)互連結(jié)構(gòu)將成為多核芯片的發(fā)展瓶頸。文章介紹了一種新型的片上體系結(jié)構(gòu)（片上網(wǎng)絡(luò)）來解決未來片上系統(tǒng)中總線所帶來的不足。片上網(wǎng)絡(luò)作為一種新的片上體系結(jié)構(gòu)，可以解決片上系統(tǒng)設(shè)計中所帶來的各種挑戰(zhàn)，受到了學(xué)術(shù)界和工業(yè)界的廣泛重視。片上網(wǎng)絡(luò)的研究涉及體系結(jié)構(gòu)、設(shè)計方法以及設(shè)計工具等諸多方面，文章從體系結(jié)構(gòu)的角度對片上網(wǎng)絡(luò)研究中的關(guān)鍵問題作了簡單介紹。

片上系統(tǒng)；片上網(wǎng)絡(luò)；體系結(jié)構(gòu)

1 引言

微電子技術(shù)發(fā)展的理論基礎(chǔ)是19世紀(jì)末到20世紀(jì)30年代期間建立起來的現(xiàn)代物理學(xué)。從1947第一支半導(dǎo)體晶體管的發(fā)明，到1958年采用硅平面工藝的集成電路誕生，直到目前正在發(fā)展中的SoC，半導(dǎo)體集成電路一直遵循摩爾定律的預(yù)言高速發(fā)展著。半導(dǎo)體發(fā)展速度為人類歷史上所罕見，僅近40年來，單個芯片上集成的晶體管數(shù)目就增加了數(shù)百萬倍。正是源于這種高速發(fā)展，使得移動電話、彩色電視機(jī)、數(shù)碼相機(jī)、個人電腦、互連網(wǎng)絡(luò)等高科技全面進(jìn)入了尋常百姓家，迅速改變了人類的生產(chǎn)模式、文化娛樂和生活方式。

從設(shè)計的角度來看，一個SoC可以被認(rèn)為是“一個將多個獨立的超大規(guī)模集成電路拼接在一起從而提供一個完整應(yīng)用功能的電路。”當(dāng)設(shè)計SoC時，SOC供應(yīng)商除了可以調(diào)用來自內(nèi)部設(shè)計的內(nèi)核庫以外，還可以使用由外部設(shè)計者所提供內(nèi)核庫。內(nèi)核基本上是預(yù)先設(shè)計好的具有復(fù)雜功能的模塊，這些模塊稱為知識產(chǎn)權(quán)模塊（IP Model），虛擬元件（VC）或簡單的一些宏。由于SoC中的核來自不同來提供商，因此SoC內(nèi)部是多樣的，這是使得設(shè)計過程變得復(fù)雜的一個關(guān)鍵因素。

總線結(jié)構(gòu)是SoC的主要特征?？偩€由于結(jié)構(gòu)簡單而被廣泛運(yùn)用。然而隨著工藝技術(shù)的持續(xù)發(fā)展，總線漸漸無法滿足芯片對性能的新要求，其主要表現(xiàn)在以下幾個方面：

（1）擴(kuò)展性差；

（2）線通信效率低；

（3）單一時鐘同步問題。

因而，2000年左右?guī)讉€研究小組提出了一種全新的集成電路體系結(jié)構(gòu)—片上網(wǎng)絡(luò)（Network on Chip），其核心思想是將計算機(jī)網(wǎng)絡(luò)技術(shù)移植到芯片設(shè)計中來，從體系結(jié)構(gòu)上徹底解決總線架構(gòu)帶來的問題。

2 NOC結(jié)構(gòu)

2.1 NOC基本體系結(jié)構(gòu)

片上網(wǎng)絡(luò)（NoC）第一次將計算機(jī)網(wǎng)絡(luò)的技術(shù)引入到芯片設(shè)計中，從體系結(jié)構(gòu)上徹底地解決這些瓶頸問題[1,2]。NoC從本質(zhì)上來說就是一個基于網(wǎng)絡(luò)通信的多處理器片上系統(tǒng)，它主要由計算節(jié)點和通信節(jié)點兩部分組成。通信節(jié)點主要由路由器組成，計算節(jié)點通過路由器加以網(wǎng)絡(luò)協(xié)議從而規(guī)范實現(xiàn)片上資源的互連和通信，這些互連資源包括CPU、DPS、視頻流處理器以及I/O接口等。NoC經(jīng)過幾年的發(fā)展，已經(jīng)出現(xiàn)了多種架構(gòu)方案，其中kumar提出的二維規(guī)則型網(wǎng)絡(luò)（2D Mesh），因其結(jié)構(gòu)簡單、容易分析和布局等優(yōu)點，已經(jīng)成為了研究的熱點[3]。圖1是一個典型的2D Mesh結(jié)構(gòu)的NoC示意圖。

從圖1我們可以看出，計算節(jié)點rn通過網(wǎng)絡(luò)適配單元NI和負(fù)責(zé)計算節(jié)點之間信息交換的通信節(jié)點Sn來實現(xiàn)數(shù)據(jù)交換。圖1給出的4×4的2D Mesh 結(jié)構(gòu)包含了一個NoC 基本組成，該結(jié)構(gòu)沒有采用總線和專用點對點的鏈路，而采用了一般網(wǎng)格拓?fù)浣Y(jié)構(gòu)，通過一定的路由算法可以實現(xiàn)任意兩個計算節(jié)點之間的通信，可采用包交換、電路交換或其他的路由方式，可使用同步、異步或其他邏輯實現(xiàn)。

對于一個NoC來說，常見的片上路由器結(jié)構(gòu)如圖2所示。由于片上路由器的緩存（buffer）限制以及NoC對信息延遲的要求，因此蟲孔交換[4]是一種比較適合NoC信息交換的方式。

2.2 NoC層次結(jié)構(gòu)

NoC借鑒OSI網(wǎng)絡(luò)模型中的分層思想，每一層和相鄰層之間都有數(shù)據(jù)接口，較低層通過接口向上一層提供服務(wù)，服務(wù)的實現(xiàn)細(xì)節(jié)是對上層屏蔽的。較高層又是在較低層提供的低級服務(wù)的基礎(chǔ)上實現(xiàn)更高級的服務(wù)。一般來說，各層的主要功能都是由NoC中的網(wǎng)絡(luò)適配單元來實現(xiàn)。關(guān)于NoC 層次結(jié)構(gòu)在不同的NoC 實現(xiàn)中有不同的描述，各層的功能略有差異，各層的名稱和數(shù)目也不盡相同。圖3給出的NoC中各層次的結(jié)構(gòu)，每個層次都對應(yīng)著NoC 的不同研究問題[5,6～9]。

3 NOC關(guān)鍵問題

3.1 NoC拓?fù)浣Y(jié)構(gòu)

NoC的拓?fù)浣Y(jié)構(gòu)反映了NoC中各節(jié)點在芯片中如何分布和連接。由于通信需求約束、各計算節(jié)點的面積、芯片封裝形式等因素的不同，采用NoC體系結(jié)構(gòu)時，設(shè)計者需要根據(jù)實際情況采用不同類型的拓?fù)浣Y(jié)構(gòu)。在選擇拓?fù)浣Y(jié)構(gòu)的時候，設(shè)計者主要應(yīng)該考慮兩個因素：通信負(fù)載較重的計算節(jié)點之間應(yīng)該盡可能靠近；NoC使用片內(nèi)布線資源作為通信信道，因此節(jié)點之間的連接不能太復(fù)雜，且要具有可擴(kuò)展性。

目前來說，常見的二維片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)主要有以下幾種：

（1）蜂窩結(jié)構(gòu)（Honeyeomb）

蜂窩結(jié)構(gòu)如圖4所示，計算節(jié)點和通信節(jié)點的比例為3∶1，每個計算節(jié)點與三個計算節(jié)點以及一個通信節(jié)點相連接，每個通信節(jié)點與六個計算節(jié)點以及六個通信節(jié)點相連。相對于其他拓?fù)浣Y(jié)構(gòu)，其連線資源比較緊張。圖4中白色模塊代表計算節(jié)點，黑色模塊代表路由節(jié)點。

（2）規(guī)則的二維網(wǎng)狀網(wǎng)絡(luò)（Regular 2D Mesh）

規(guī)則的二維網(wǎng)狀網(wǎng)絡(luò)是目前設(shè)計者最常用的拓?fù)浣Y(jié)構(gòu)，如圖5所示。每一個計算節(jié)點與一個通信節(jié)點相連，而一個通信節(jié)點與四個相鄰的通信節(jié)點相連；通信節(jié)點實現(xiàn)路由的功能，并作為每個相鄰的計算節(jié)點的網(wǎng)絡(luò)接口。

（3）二維折疊環(huán)（2D Folded Torus）

2001年6月，斯坦福大學(xué)的W.J.Daly提出使用片上互連網(wǎng)絡(luò)通過數(shù)據(jù)包通信的方式替代各式各樣的連線結(jié)構(gòu)的構(gòu)想，并提出了二維折疊環(huán)的拓?fù)浣Y(jié)構(gòu)，如圖6所示。與二維網(wǎng)狀網(wǎng)絡(luò)相比，它將處于邊界的通信節(jié)點也連接起來，使所有的通信節(jié)點成為一個環(huán)路，這樣可提供更多的路由選擇。但是從圖6中也可以看到，由于環(huán)路與環(huán)路之間有交叉的地方，這樣不可避免地在物理實現(xiàn)時需要更多的版圖布線資源[10]。

由于三維片上結(jié)構(gòu)的技術(shù)發(fā)展，已經(jīng)有學(xué)者提出了三維的片上結(jié)構(gòu)，三維的片上網(wǎng)絡(luò)可提供更高效的數(shù)據(jù)通信。

3.2 路由策略

路由是確定一個數(shù)據(jù)從源節(jié)點到目的節(jié)點的發(fā)送機(jī)制。NoC中的路由算法確定如何為每個數(shù)據(jù)包建立下一條要執(zhí)行的路徑，即路由算法決定數(shù)據(jù)包從源節(jié)點開始選擇哪一條路徑到達(dá)目的節(jié)點。所以，路由算法對NoC網(wǎng)絡(luò)性能的好壞是至關(guān)重要的。路由算法可以分為：確定性路由（Deterministic Routing）和自適應(yīng)路由（Adaptive Routing）。

NoC主要的確定性路由算法有源路由算法和XY路由算法。源路由算法是由源節(jié)點指定包到目的節(jié)點的路由；XY路由算法將數(shù)據(jù)包首先在X方向進(jìn)行傳輸，然后在Y方向進(jìn)行傳輸?shù)竭_(dá)目的地。它是一種無死鎖、確定性和基于源地址的路由算法。XY路由算法能在負(fù)載較輕和負(fù)載均勻的條件下，比較穩(wěn)定地工作，但在負(fù)載加重時，NoC的性能會變得很差。文獻(xiàn)[11]針對XY路由在負(fù)載加重時，性能變差這一缺點提出改用一種自適應(yīng)路由模式。在負(fù)載較輕和負(fù)載均勻的條件下采用XY路由模式，在負(fù)載加重時采用自適應(yīng)路由模式，這路由算法稱為DyAD Routing。自適應(yīng)路由涉及動態(tài)分布機(jī)制，它能根據(jù)局部鏈路擁塞的情況，很好地適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化，是具有一定容錯功能的網(wǎng)絡(luò)路由算法。例如，網(wǎng)絡(luò)中某節(jié)點不可用（故障）時，包就繞開該節(jié)點，沿著其他的路徑傳輸，但自適應(yīng)路由算法實現(xiàn)復(fù)雜、開銷大，不適合在芯片上實現(xiàn)。

NoC中的路由算法應(yīng)該能有效地解決活鎖、饑餓以及死鎖的問題?；铈i：當(dāng)一個包在它的目的地環(huán)繞但無法到達(dá)目的節(jié)點時就發(fā)生了活鎖，該問題存在于非最短路由算法中。饑餓：使用不同優(yōu)先級可能出現(xiàn)高優(yōu)先級的包始終占用資源，而一些低優(yōu)先級的包永遠(yuǎn)不能到達(dá)其目的地，發(fā)生饑餓現(xiàn)象，使用公平路由算法或為低優(yōu)先級的包預(yù)留一些資源可避免饑餓現(xiàn)象。死鎖：當(dāng)兩個包彼此等待路由轉(zhuǎn)發(fā)時，由于保留了部分資源并等待對方釋放資源，因此產(chǎn)生死鎖，死鎖是由資源的獨占性引起的。

3.3 交換技術(shù)

交換技術(shù)是按照某種方式動態(tài)地分配傳輸線路和接口資源的規(guī)則。NoC中的基本交換技術(shù)，包括：存儲轉(zhuǎn)發(fā)交換、虛擬直通交換技術(shù)（Virtual Cut-Through）和蟲孔交換技術(shù) （Wormhole Routing）[12]。

（1）存儲轉(zhuǎn)發(fā)交換：在計算機(jī)網(wǎng)絡(luò)中，這是最流行的分組交換技術(shù)。采用存儲轉(zhuǎn)發(fā)交換，整個數(shù)據(jù)包的一部分將存放在接收路由器中，直到接收路由器接收到整個數(shù)據(jù)包后，它才將數(shù)據(jù)包提交給下一個在路由路徑上的路由器。在這路由機(jī)制下，每個路由器都需要有充足的緩沖空間，以存放整個數(shù)據(jù)包。對于大的數(shù)據(jù)包而言，這種方法將會引入額外的數(shù)據(jù)包傳輸延遲。由于緩沖資源相當(dāng)昂貴，除此以外，存儲轉(zhuǎn)發(fā)交換需要消耗更多的功耗和面積，因此不適合作為NoC的路由交換技術(shù)。

（2）虛擬直通交換：這種技術(shù)可以減少由于存儲轉(zhuǎn)發(fā)交換所引起的數(shù)據(jù)包延遲。在這種路由機(jī)制下，路由器不存儲整個數(shù)據(jù)包，數(shù)據(jù)包被當(dāng)前路由器接收后可以馬上轉(zhuǎn)向下一個路由器。但是，如果下一個路由器無法使用，那么，當(dāng)前路由器，將以完整的形式存儲待發(fā)數(shù)據(jù)包。在吞吐量相同的情況下，虛擬直通交換機(jī)制的能耗低于存儲轉(zhuǎn)發(fā)交換。

（3）蟲孔交換：這種交換機(jī)制是為并行處理器而開發(fā)的。蟲洞流程控制能夠?qū)崿F(xiàn)較小的Buffer和較短時間的路由延遲。在蟲孔交換中，信息包被劃分成更小的流控單元（flit）。flit以流水線的方式進(jìn)行路由，可明顯減少通信延遲。第一個flit通常被稱為頭flit，頭flit中包含了路由信息，當(dāng)頭flit由于網(wǎng)絡(luò)競爭產(chǎn)生堵塞后，后續(xù)的flit將停止在各自所在的路由節(jié)點，因此各路由節(jié)點只需要很小的緩存就可以滿足存儲的需要。從而減少了路由器中緩存空間的需求。

通過比較了三個流行的交換技術(shù)后，可以很容易的看出，蟲孔交換是片上網(wǎng)絡(luò)的最佳選擇：蟲孔交換使網(wǎng)絡(luò)延遲對路徑長度不那么敏感。通常延遲由兩部分組成：一部分是發(fā)送數(shù)據(jù)包的時間，另一部分是各個節(jié)點尋徑時間的總和。在實際應(yīng)用中，一般數(shù)據(jù)包的長度比較大，且遠(yuǎn)遠(yuǎn)大于各個節(jié)點尋徑時間的總和，蟲孔交換的網(wǎng)絡(luò)延遲主要由數(shù)據(jù)包發(fā)送時間來決定，因此采用蟲孔路由的片上網(wǎng)絡(luò)更易升級。同時蟲孔路由只需要很少的路由器緩存，這一點也很好的迎合了NoC的特點。因此目前的大部分片上網(wǎng)絡(luò)交換技術(shù)都是采用了蟲孔路由技術(shù)。

片上網(wǎng)絡(luò)成為了解決日益復(fù)雜的SoC設(shè)計問題最有前景的方法之一，目前NoC的研究除了集中在上述幾個方面外，還包括了NoC的服務(wù)質(zhì)量（QoS）以及它的軟件模型（software model）等。

4 小結(jié)

本文所討論的問題只是 NoC設(shè)計中的一部分，具體實現(xiàn)一個 NoC的時候，從物理層到系統(tǒng)層，從軟件到硬件，NoC涉及的方方面面遠(yuǎn)遠(yuǎn)多于本文所討論的問題。雖然NoC的潛力是巨大的，但在實現(xiàn)一些關(guān)鍵技術(shù)之前：如可靠的NoC結(jié)構(gòu)、高質(zhì)量的服務(wù)保證和可行的軟件模型，它將還無法應(yīng)用到實際設(shè)計中去。因此NoC這個領(lǐng)域，還有很多值得研究的地方。

［1］L.Benini, G.De Micheli.Networks on chips: A new SoC Paradigm [J].IEEE Computer Magazine, 2002, 35（1）:70-78.

［2］W.J.Dally, B.Towles.Route packets,not wires:on-chip interconnection networks[A].Proc.Design Auto- mation Conf[C],2001,684-689.

［3］Kumar S,J ant sch A,Soininen J,et al.A Network on Chip Architecture and Design Methodology [A].Proc- eedings of IEEE Computer Society Annual Symposium on VLSI[C], 2002,105-112.

［4］L.M.Ni and P.K.McKinley.A survey of wormhole routing techniques in direct networks [J].Computer, 1993, 26（2）:62-76.

［5］http:// www.st.com/[EB/OL].

［6］Dally W J, Towles B.Principles and Practices of Interconnection Networks [M]. Morgan Kaufmann, 2004.

［7］Bjerregaard T,Mahadevan S.A survey of research and practices of network-on-chip[C].ACM Computing Surveys,2006 , 38（1） :1-54

［8］Dehyadgari M,Nickray M, Afzali2kusha A, et al. A New Protocol Stack Model for Network on Chip[C]. In: Proceedings of the 2006 Emerging VLSI Technologies and Architectures （ISVLSI’ 06）, IEEE, 2006, p2

［9］Kumar S, J ant sch A, Soininen J-P, et al. A network on chip architecture and design met hodology. In: Proc. Int’s Symp.VLSI （ISVLSI）, 2002. 117-124

［10］W.J.Dally and C.L.Seitz, The Torus Routing ChiP[J].Technieal RePort 5208:TR:86,ComPuter Seienee De Pt,California Inst.Of Technology,1986:1-19.

［11］Dehyadgari M,Nickray M,Afzali - kusha A,et al. Evaluation of pseudo adaptive XY routing using an object oriented model for NoC [C]//The 17th International Conference on Microelectronics. Iran:Tehran University,2005:204-208

［12］Ye T, Benini L, De Micheli G.Packetization and routing analysis of on chip multiprocessor networks[J]. Journal of Systems Architecture,2004,50（223）:81-104.

NoC: A New Architecture for System on Chip

LIU Yan-hua, LIU Jing, LAI Zong-sheng
（Institute of Microelectronics Circuit & System, East China Normal University,Shanghai200062,China）

The shared or dedicated buses are used in System on Chip（SoC）to interconnect the communicating on-chip resources. But, these buses can not be scalable beyond a certain limit. In this case, the current interconnect infrastructure will become a bottleneck for the development of multi IP chip. In this paper, we will introduce a new design paradigm （Networks on Chip） that has been proposed to counter the inefficiency of buses in future SoC. NoC as a new architecture on chip, can be a solution for the challenges of SoC design and has been

recognition by academe and industry. The research for NoC involves many problems such as system architecture, design methodology, design tools and so on.In this paper, we simply discuss the key problems for NoC from the view of system architecture.

System on Chip（SoC）; Network on Chip（NoC）; system architecture

TN701

A

1681-1070（2011）05-0023-05

2011-04-02

江蘇省專用集成電路設(shè)計重點實驗室開放課題基金資助項目（JSICK0801）

劉炎華（1980—），男，江蘇南通人，博士研究生，主研方向為高性能SoC/NoC體系結(jié)構(gòu)設(shè)計及測試。

微電子制造與可靠性