片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)研究

胡偉

（黃山學(xué)院 信息工程學(xué)院，安徽 黃山 245021）

片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)研究

胡偉

（黃山學(xué)院 信息工程學(xué)院，安徽 黃山 245021）

隨著SoC體系結(jié)構(gòu)設(shè)計復(fù)雜度的提高，傳統(tǒng)的總線結(jié)構(gòu)已成為IP核之間通信的瓶頸，新的設(shè)計方法片上網(wǎng)絡(luò)(NoC)應(yīng)運(yùn)而生。在對NoC拓?fù)浣Y(jié)構(gòu)進(jìn)行了分類的基礎(chǔ)上，分析了各種網(wǎng)絡(luò)拓?fù)涞南嚓P(guān)特性，結(jié)果表明這些拓?fù)浣Y(jié)構(gòu)都具有良好的可擴(kuò)展性，文章還探討了NoC拓?fù)浣Y(jié)構(gòu)的發(fā)展方向。

片上網(wǎng)絡(luò)（NoC）；片上系統(tǒng)（SoC）；拓?fù)浣Y(jié)構(gòu)

1 引 言

隨著半導(dǎo)體工藝技術(shù)步入納米階段，在單一芯片中集成上億晶體管已經(jīng)成為現(xiàn)實(shí)，片上系統(tǒng)（SoC）的發(fā)展已經(jīng)進(jìn)入極其迅速的時代。按照不同的片上互連方式，多核SoC可分為兩大類，即傳統(tǒng)的基于總線的互連和基于網(wǎng)絡(luò)的互連。前者是現(xiàn)有SoC的擴(kuò)展，通過多總線及層次化總線等技術(shù)使得片上集成更多的處理器核，從而實(shí)現(xiàn)高復(fù)雜度和高性能，而后者是近些年提出的嶄新概念，即多處理器核之間采用分組路由的方式進(jìn)行片內(nèi)通信，從而克服了由總線互連所帶來的各種瓶頸問題，這種片內(nèi)通信方式稱為片上網(wǎng)絡(luò) (Network on a Chip，NoC)。自從NoC概念在2000年第一次被提出，已經(jīng)過10年的發(fā)展，已經(jīng)進(jìn)入技術(shù)逐步成熟的階段。

2 片上網(wǎng)絡(luò)體系結(jié)構(gòu)

NoC中允許存在任意類型的資源節(jié)點(diǎn)，典型的資源節(jié)點(diǎn)可以是帶緩沖的嵌入式微處理器和DSP核、專用硬件資源、可重構(gòu)硬件資源，或者是上述各種硬件的組合。圖1顯示了資源節(jié)點(diǎn)中可能包含的硬件資源。計算類的資源節(jié)點(diǎn)以微處理器核、DSP核等形式存在，而存儲類的資源節(jié)點(diǎn)則要求盡可能地分散，以避免訪問數(shù)據(jù)時要跨越整個芯片。各種尺寸的SRAMS、DRAMS、FLASH滿足了不同的需求。

圖1 資源節(jié)點(diǎn)中包含各種類型的硬件資源

通訊節(jié)點(diǎn)是互連網(wǎng)絡(luò)中的主要部分，其核心就是交換開關(guān)。如網(wǎng)絡(luò)中的路由器，其主要作用是尋找出信息從起點(diǎn)到終點(diǎn)的最短最有效的路徑。在數(shù)據(jù)傳輸中，有兩種路由方式可供設(shè)計者選擇：確定性路由（deterministic routing）和自適應(yīng)路由（adaptive routing）但是對于NoC設(shè)計，自適應(yīng)路由規(guī)則并不適合。這并不是考慮自適應(yīng)路由中路由表的存在，而是由計算升級和維持信息的復(fù)雜度決定的。

3 片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

為了滿足不同的性能和成本等需求，人們設(shè)計了很多不同的專用多處理器網(wǎng)絡(luò)拓?fù)?。MPSoC (Multi-Processor System-on-Chip)網(wǎng)絡(luò)可以被分成直接網(wǎng)絡(luò)和間接網(wǎng)絡(luò)兩類。在直接網(wǎng)絡(luò)MPSoC中，節(jié)點(diǎn)處理器通過網(wǎng)絡(luò)直接相互連接，每個節(jié)點(diǎn)執(zhí)行數(shù)據(jù)流路由和仲裁。在間接網(wǎng)絡(luò)MPSoC中，節(jié)點(diǎn)處理器通過一個或多個中間節(jié)點(diǎn)開關(guān)相連，開關(guān)節(jié)點(diǎn)執(zhí)行路由和仲裁功能。間接網(wǎng)絡(luò)也稱為多階段互連網(wǎng)絡(luò)（Multistage Interconnect Networks,MIN）。

NOC的拓?fù)浣Y(jié)構(gòu)有直接網(wǎng)絡(luò)Orthogonal拓?fù)?，立體連接循環(huán)（Cube-Connected-Cycle）拓?fù)洹ctagon拓?fù)涞龋婚g接網(wǎng)絡(luò)拓?fù)銫rossbar Switch結(jié)構(gòu)、Fully-Connected網(wǎng)絡(luò)、Butterfly拓?fù)涞取?/p>

3.1 直接網(wǎng)絡(luò)拓?fù)?/h3>

3.1.1 Orthogonal拓?fù)?/p>

Orthogonal拓?fù)渚W(wǎng)絡(luò)中節(jié)點(diǎn)以K-陣列N-維Mesh[1]或者K-陣列N-維Torus[2]形式互連。如圖2所示的就是一個2-D Mesh網(wǎng)格結(jié)構(gòu)，從圖中可以看到，每個資源節(jié)點(diǎn)和一個交換節(jié)點(diǎn)相連，而一個交換節(jié)點(diǎn)和4個相鄰的交換節(jié)點(diǎn)相連，二維網(wǎng)格結(jié)構(gòu)在帶寬、時延等通信性能上并不是最優(yōu)，但其結(jié)構(gòu)簡單、可重用性好、可擴(kuò)展性強(qiáng)，因此成為研究最多的拓?fù)浣Y(jié)構(gòu)。Torus網(wǎng)絡(luò)結(jié)構(gòu)在Mesh網(wǎng)格結(jié)構(gòu)的基礎(chǔ)上,將位于邊緣的兩個節(jié)點(diǎn)也連接了起來，如圖3所示，環(huán)面網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)點(diǎn)在于增強(qiáng)了位于邊緣的節(jié)點(diǎn)之間的通訊，其缺點(diǎn)在于增加的邊緣的節(jié)點(diǎn)之間的連線與其它連線有交叉,增加了布線的困難。Mesh和Torus網(wǎng)絡(luò)在并行計算平臺中被廣泛使用。

圖2 Mesh網(wǎng)絡(luò)

圖3 Torus網(wǎng)絡(luò)

3.1.2 立方體連接循環(huán)拓?fù)?/p>

立方體連接循環(huán)拓?fù)涫菫榱藴p少Orthogonal拓?fù)渲忻總€節(jié)點(diǎn)的度而設(shè)計的。如圖4所示，3-立方結(jié)構(gòu)的每個節(jié)點(diǎn)有3個度，而在Mesh和Torus網(wǎng)絡(luò)中每個節(jié)點(diǎn)有2n個度，立方體互連周期拓?fù)溆幸粋€層次化結(jié)構(gòu)，在立方體的每個角上3個節(jié)點(diǎn)形成一個局部環(huán)。

圖4 Octagon網(wǎng)絡(luò)

3.1.3 Octagon拓?fù)?/p>

Octagon網(wǎng)絡(luò)是為網(wǎng)絡(luò)處理器提出的一個片上通信結(jié)構(gòu)。F.Kariml[3]等人在設(shè)計網(wǎng)絡(luò)處理器時提出了一個如圖5所示的八角形網(wǎng)絡(luò)。這種結(jié)構(gòu)中，8個處理器通過一個Octagon環(huán)和3個直徑相連。任意兩個處理器之間的延遲在局部環(huán)中不超過兩個階段，即通過一個中間節(jié)點(diǎn)，這個Octagon網(wǎng)絡(luò)是可伸縮的。如果一個處理器作為橋節(jié)點(diǎn)，可以把更多的Octagon連在一起。

圖5 立方連接循環(huán)

3.2 間接網(wǎng)絡(luò)拓?fù)?/h3>

3.2.1 Crossbar Switch結(jié)構(gòu)

一個N×N Crossbar網(wǎng)絡(luò)連接N個輸入端口和N個輸出端口。N個輸入端口的任意一個都可以和任意一個輸出端口通過對應(yīng)的交叉點(diǎn)上的節(jié)點(diǎn)開關(guān)相連。

圖6 CrossbarSwitch結(jié)構(gòu)

3.2.2 Fully-Connected網(wǎng)絡(luò)

一個N×N完全互連網(wǎng)絡(luò)使用MUXes把每個輸入聚合到輸出，如圖7所示。仲裁器控制著每個MUX，決定哪個輸入指向哪個輸出。

圖7 全連接Switch結(jié)構(gòu)

與交叉網(wǎng)絡(luò)相似，完全互連開關(guān)網(wǎng)絡(luò)也常稱為Crossbar，在完全互連開關(guān)網(wǎng)絡(luò)中，每個源-目的連接有專門的數(shù)據(jù)路徑。

3.2.3 Butterfly拓?fù)?/p>

Butterfly網(wǎng)絡(luò)（如圖8）是一個間接網(wǎng)絡(luò)結(jié)構(gòu)。在Butterfly結(jié)構(gòu)中，每個源到目的路由是用一個專門的數(shù)據(jù)路徑。任意兩個處理器節(jié)點(diǎn)之間的延遲是一樣的，延遲時間由開關(guān)結(jié)構(gòu)上的中間階段數(shù)目決定。

圖8 Butterfly結(jié)構(gòu)

Butterfly拓?fù)溆泻芏嗖煌耐瑯?gòu)變體，如Banyan Network，Batcher-Banyan Networks等。

3.2.4 Fat-tree拓?fù)?/p>

樹中的內(nèi)節(jié)點(diǎn)是開關(guān)，葉子是處理器。除了根節(jié)點(diǎn)，每個內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和若干個子節(jié)點(diǎn)相連。傳統(tǒng)K叉樹的主要問題是單個父節(jié)點(diǎn)尤其是根節(jié)點(diǎn),容易成為通信瓶頸。Leiserson[4]于1985年提出的胖樹，一個節(jié)點(diǎn)可擁有多個父節(jié)點(diǎn),可以緩解此問題。因此，和Butterfly網(wǎng)絡(luò)不同，胖樹網(wǎng)絡(luò)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)提供了多個數(shù)據(jù)路徑。胖樹網(wǎng)絡(luò)可被看作一個擴(kuò)展的有多個根節(jié)點(diǎn)的n-列樹網(wǎng)絡(luò)，網(wǎng)絡(luò)延遲依賴于樹的深度。

如圖9所示，SPIN[5]網(wǎng)絡(luò)是一個4-列胖樹拓?fù)涞脑O(shè)計例子，每個處理器位于這個胖樹的葉子節(jié)點(diǎn)上。被分割為分組的消息通過向上或向下遍歷胖樹網(wǎng)絡(luò)在處理元件之間進(jìn)行分組交換。一個分組被定義為一個36位的字。分組的頭占用第一個字，頭的一個字節(jié)代表目的地址，其他位用于作分組標(biāo)志和路由信息。分組的有效負(fù)載時可變的，每個分組由一個尾部來終止，尾部不含數(shù)據(jù)，而是用來檢錯的。

圖9 SPIN網(wǎng)絡(luò)

4 各種拓?fù)浣Y(jié)構(gòu)的對比

用來刻劃一個拓?fù)浣Y(jié)構(gòu)的特征，并影響其性能的而又彼此關(guān)聯(lián)的參數(shù)有：節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)度，網(wǎng)絡(luò)直徑和鏈路數(shù)等。表1總結(jié)了一些典型規(guī)則拓?fù)涞奶匦詤?shù)，這些參數(shù)常用來估計網(wǎng)絡(luò)的復(fù)雜性、通信效率、成本等，是選擇網(wǎng)絡(luò)拓?fù)涞闹匾罁?jù)。

表1 典型規(guī)則拓?fù)涞奶匦?/p>

5 結(jié) 論

NoC解決了在SoC設(shè)計中存在的問題，是一種新的設(shè)計方法，它在信息吞吐量、延遲、能耗和芯片面積等方面做出了很大的改進(jìn)。本文分析了NoC中常見的拓?fù)浣Y(jié)構(gòu)，指出了每種拓?fù)浣Y(jié)構(gòu)的主要特點(diǎn)，并綜合地對幾種典型拓?fù)鋸墓?jié)點(diǎn)數(shù)，網(wǎng)絡(luò)直徑，節(jié)點(diǎn)度，鏈路數(shù)等方面進(jìn)行了對比分析，這些拓?fù)浣Y(jié)構(gòu)都具有良好的可擴(kuò)展性。

未來NoC拓?fù)浣Y(jié)構(gòu)的主要發(fā)展方向是：

1.增強(qiáng)系統(tǒng)的可測試性和可靠性，降低設(shè)計的風(fēng)險；

2.研究Noc模擬工具，降低設(shè)計成本，提高設(shè)計效率；

3.設(shè)計低復(fù)雜度的拓?fù)浣Y(jié)構(gòu)，減小芯片面積；

4.研究NoC降低功耗，提高系統(tǒng)性能。

同時，NoC涉及了從物理實(shí)現(xiàn)到體系結(jié)構(gòu)，到操作系統(tǒng)，到應(yīng)用的各個層次，也就需要對其各個層面進(jìn)行研究。

[1]M.Forsell,A scalable high-performance computing solution for networks on chips[J].IEEE Micro,2002,22(5):46-55.

[2]WJDally,B Towles,RoutePackets,NotWires:On-Chip Interconnection Networks[J].DAC 2001,IEEE,2001,18 (6):684-689.

[3]F.Karim,A.Nguyen,S.Dey,R.Rao.On -chip communication architecture for OC -768 network processors [J]. Proceedings of 38th Design Automation Conference,June 2001,25(6):.678-683.

[4]LEISERSON C E.Fat-trees:Universalnetworks for hardware-effi-cient supercomputing[J].IEEE Transactions on Computers,1985,34(10):892-901.

[5]ADRIAHANTENAINA A,CHARLERY H,GREINER A,et al.SPIN:A scalable,packetswitched,on-chipmicronetwork[C]//Proceedings of Design,Automation and Test in Europe Conferenceand Exhibition.Washington, DC, USA:IEEE ComputerSociety,2003:70-73.

Research on the Topology Structure of Network-on-Chip

Hu Wei
(School of Information Engineering,Huangshan University,Huangshan 245021,China)

With the increasing complexity of SoC structure design,the traditional bus structure has become the bottleneck of communication among IP blocks,thus a new design method for network-on-chip (NoC)came into being.On the basis of a classification for NoC topology structures,each specific topology was discussed in details.The results showed that the topology structures have good scalability.At the end of the paper,the future research direction of NoC topology structure was presented.

Network-on-Chip(NoC);System-on-Chip(SoC);topology structure

TP302

A

1672-447X(2010)04-0083-04

2010-05-10

胡 偉(1978-),安徽績溪人,黃山學(xué)院信息工程學(xué)院講師，碩士,主要研究方向?yàn)榍度胧较到y(tǒng)綜合與測試、計算機(jī)控制。

胡德明