劉怡俊，劉俊輝

(廣東工業(yè)大學計算機學院，廣東廣州510006)

由于片上系統(tǒng)不能滿足大規(guī)模集成電路發(fā)展需要，新的設計方法片上網(wǎng)絡(NoC)應運而生.它是把傳統(tǒng)的計算機網(wǎng)絡技術(shù)移植到芯片內(nèi)部，以成本低廉的點對點分組交換架構(gòu)取代傳統(tǒng)的總線架構(gòu).文獻［1］詳細介紹了片上網(wǎng)絡各組成部分，包括常見的Mesh拓撲網(wǎng)絡跟Torus拓撲網(wǎng)絡以及交換技術(shù)等基本概念.文獻［2］提出一種基于片上網(wǎng)絡的互連拓撲結(jié)構(gòu)－層次化路由結(jié)構(gòu)MLR(Multi-Layer Router).該結(jié)構(gòu)通過層次化設計減小網(wǎng)絡直徑，具有良好的對稱性和擴展性.文獻［3］具體提出了MECS拓撲網(wǎng)絡結(jié)構(gòu)(見圖1)，但由于IP核數(shù)量的增加，輸入緩沖區(qū)容易堵塞增加時延，而且對重要數(shù)據(jù)包傳輸也沒有進行優(yōu)先處理.文獻［4］提出了虛擬通道控制器的設計.文獻［5］提出利用交叉開關(guān)進行并行輸入.文獻［6］提出了一種拓撲結(jié)構(gòu)，每個資源節(jié)點與兩個路由節(jié)點連接，內(nèi)部的路由節(jié)點與3個相鄰的路由節(jié)點相連，雖然容錯性能很好但它的面積和功耗都比較大.文獻［7］對不同數(shù)目的緩沖區(qū)進行分析，優(yōu)化性能.文獻［8］采用模擬退火算法減少虛擬通道數(shù)目并優(yōu)化分配方式，達到功耗優(yōu)化的目標.文獻［9］采用了緩沖區(qū)被多個端口共享FIFO方式提高網(wǎng)絡性能和硬件開銷.文獻［10］提出了QoS服務質(zhì)量保證，針對不同數(shù)據(jù)采用不同優(yōu)先級方式確保了高優(yōu)先級數(shù)據(jù)包低延時的傳輸.本文針對當前決定NoC網(wǎng)絡復雜程度的關(guān)鍵性因素拓撲網(wǎng)絡，采用了文獻［3］的拓撲網(wǎng)絡結(jié)構(gòu)MECS，該結(jié)構(gòu)的優(yōu)點是多個IP核集成在一個路由節(jié)點上，然后采用一對多通信方式，提高了連通性，它們之間的傳輸不需要經(jīng)過多個路由節(jié)點，避免了經(jīng)過中間路由器的延遲和能量損耗，節(jié)點間平均距離(hop)最大為2，不僅節(jié)約了硬件資源，減少了通信延遲時間和提高了吞吐量，而且相對于3維拓撲網(wǎng)絡［11］結(jié)構(gòu)物理布局布線難度較小，而且在此基礎上對輸入輸出模塊進行改進和對特殊需要的數(shù)據(jù)包進行優(yōu)先傳輸.本文分4部分，第1部分是MECS工作原理，第2部分是路由器結(jié)構(gòu)，第3部分是路由算法，最后是實驗驗證結(jié)果.

圖1 MECS拓撲網(wǎng)絡結(jié)構(gòu)Fig.1 MECS topology network architecture

1 MECS工作原理

MECS是一種新型拓撲網(wǎng)絡，使用一對多高程度的互連的通信模式，擁有較小網(wǎng)絡直徑.MECS是采用多個IP核集成在一個路由節(jié)點內(nèi)，數(shù)據(jù)來自節(jié)點內(nèi)IP核發(fā)出的和接收來自其他路由節(jié)點存儲到Cache的.轉(zhuǎn)發(fā)數(shù)據(jù)采用交換開關(guān)方式，輸出到本地、水平方向路由節(jié)點和豎直方向路由節(jié)點，XY方向是采用廣播方式直接輸入到輸入緩沖中，然后再比較是否要進行第二次廣播［12］，因此從源IP核到目的IP核之間最多只需要2次跳躍，路由算法是采用XY無死鎖算法，采用虛直通交換，避免了數(shù)據(jù)丟失，保證了較高的服務質(zhì)量

2 路由器基本結(jié)構(gòu)

如圖1所示，MECS拓撲網(wǎng)絡結(jié)構(gòu)有64個IP核，按照編號把IP核每4個集成在一個路由節(jié)點上.因此64個IP核總共需要6位二進制數(shù)表示.0000_00表示第一個路由節(jié)點的第一個IP核，以此類推，1111_00表示16個路由節(jié)點第64個IP核.總共有32條鏈路，網(wǎng)絡直徑為2，相比較Torus和Mesh拓撲網(wǎng)絡結(jié)構(gòu)，MECS能大程度地減少路由節(jié)點的個數(shù)和傳輸時轉(zhuǎn)發(fā)的跳數(shù)，縮短了網(wǎng)絡直接平均距離和延時.圖2為本文提出的MECS路由節(jié)點結(jié)構(gòu)，擁有輸入模塊、IP核模塊、VC控制器和交叉開關(guān)、路由算法模塊.其中仲裁器采用的是輪詢仲裁方式，路由算法是采用XY確定性算法，交換開關(guān)采用交叉陣列式.

圖2 路由單元結(jié)構(gòu)Fig.2 Routing unit structure

2.1 輸入模塊

2.1.1 數(shù)據(jù)結(jié)構(gòu)

如圖3所示，把微片大小定義為32位，其中頭兩位00表示頭微片，頭微片攜帶路由信息，01表示數(shù)據(jù)微片，10表示尾微片.首先數(shù)據(jù)從IP核出來，根據(jù)目的資源節(jié)點可以推算出目的節(jié)點在哪個路由節(jié)點上，然后把路由節(jié)點信息放在頭微片上，數(shù)據(jù)分割成多個數(shù)據(jù)微片，最后在尾微片處結(jié)束.由于本文只有64位IP核，那么就只需6bit，高4位為節(jié)點數(shù)低2位是IP核數(shù)目例如0000_01則為第一個節(jié)點第2個IP核，其中節(jié)點數(shù)前兩位為豎直方向，后兩位為水平方向.P位為數(shù)據(jù)流優(yōu)先級位，在網(wǎng)絡接口注入數(shù)據(jù)時為某些重要業(yè)務或突發(fā)性業(yè)務設置優(yōu)先級，在鏈路堵塞時，具有高優(yōu)先級的數(shù)據(jù)流對鏈路擁有優(yōu)先權(quán)，使系統(tǒng)得到及時實現(xiàn)功能.

圖3 微片結(jié)構(gòu)Fig.3 Filt structure

2.1.2 輸入緩沖區(qū)

因為NoC受面積影響大，F(xiàn)IFO移位寄存器設計更適合，因為SRAM的地址譯碼器邏輯部分要求有額外的面積開銷，并且在數(shù)據(jù)存儲接入期間信號會有更頻繁的翻轉(zhuǎn)變換.本文輸入的數(shù)據(jù)采用FIFO對數(shù)據(jù)包各微片并行存儲.緩存器空間的大小由兩個指標來定義，深度和寬度.寬度定義了包中并行字節(jié)的數(shù)量(FIFO內(nèi)部字節(jié)的寬度)，深度給出了路由緩存能夠存儲的給定大小的微片的最大數(shù)量.本文采用深度為12、位寬為32位的輸入緩沖區(qū)，如圖4所示(a)為緩沖區(qū)空，(b)為滿.用2個狀態(tài)位表示，讀和寫循環(huán)單次用1表示，循環(huán)雙次用0表示，當讀寫位置一樣時，兩個狀態(tài)位相等則是空，不等則為滿.每個輸入端都擁有2個虛擬通道，其空滿狀態(tài)由標志位表示，由VC控制器控制.

圖4 FIFO空滿標志Fig.4 Empty or full flag of FIFO

2.1.3 虛直通交換

本文數(shù)據(jù)傳輸采用虛直通交換機制［13］.它把數(shù)據(jù)包分割成很小的微片，如圖3所介紹的結(jié)構(gòu).所有的微片按數(shù)據(jù)包中的順序排列好，以“流水線”的形式頭微片先于數(shù)據(jù)微片和尾微片依次在網(wǎng)絡中傳輸.在輸入到Cache時，首先檢查flit類型，如果是頭微片且Cache為空則在仲裁器中標記，然后從緩沖區(qū)中輸出數(shù)據(jù)flit，遇到尾flit時把標記取消，最后詢問下一個Cache，這樣保證了同一個包所有的微片按序傳輸，而且不會讓其他數(shù)據(jù)包的微片插入進來，導致數(shù)據(jù)包出錯.當沒遇到堵塞時相當于直通，并且只占用緩沖區(qū)很少的資源就立馬把微片轉(zhuǎn)發(fā)出去，縮短了存儲轉(zhuǎn)發(fā)的時延.當遇到堵塞時，把數(shù)據(jù)全存儲在最后一個堵塞的Cache中.因此每個Cache的深度應該等于或者大于數(shù)據(jù)微片的大小，等待下次輸出.

2.2 VC控制器和交叉開關(guān)仲裁器

本文通過設置統(tǒng)一個數(shù)虛擬通道，并采用不同數(shù)目測試各自虛擬通道利用率和整個網(wǎng)絡延時、吞吐量等性能.當網(wǎng)絡出現(xiàn)多個業(yè)務競爭同時競爭同一資源傳輸數(shù)據(jù)導致堵塞時，仲裁器［14］根據(jù)一定的法則將資源優(yōu)先分配給某個資源請求者.在輸入緩沖區(qū)采用的是輪詢方式仲裁存儲數(shù)據(jù).當要進入交叉開關(guān)后，存在多個輸入端口傳輸?shù)臄?shù)據(jù)競爭同一個輸出端口情況，這就存在如何分配和競爭的問題，本文輸出數(shù)據(jù)時首先仲裁優(yōu)先級高的業(yè)務進行傳輸，同一優(yōu)先級的業(yè)務則按照計數(shù)器仲裁方式進行傳輸，來自水平方向和豎直方向的數(shù)據(jù)跟本路由節(jié)點4個IP核產(chǎn)生的數(shù)據(jù)共同競爭統(tǒng)一資源或者并發(fā)使用不同資源縮短時延，從而可以提高吞吐量.其中同等優(yōu)先級下的交叉開關(guān)陣列如圖5所示.行為輸入端口，列為輸出端口，即從行端口中的Cache取出數(shù)據(jù)輸出到列的端口去.

圖5 交叉開關(guān)Fig.5 Crossbar

圖5中每列最多只有一個1(1表示為列與行端口建立了通路，它是由仲裁器和路由算法決定)，其余為0，當整個包微片輸出完，然后恢復為0.此交換開關(guān)允許并行輸出，如圖5所示是Xport1_1(水平輸入端口1虛擬通道1)經(jīng)過仲裁獲得輸入到IP核的優(yōu)先權(quán)，建立了通路，直到數(shù)據(jù)包傳輸完畢，恢復為0，然后在其他端口繼續(xù)競爭仲裁，其他類似都是并行工作.

2.3 路由算法

路由算法［15］是在NoC網(wǎng)絡中決定數(shù)據(jù)微片從一個路由器轉(zhuǎn)發(fā)給下一個是哪個路由器的策略.是根據(jù)數(shù)據(jù)包頭微片包含的路由節(jié)點信息、IP核信息、數(shù)據(jù)微片類型信息、業(yè)務類型優(yōu)先權(quán)信息和本地路由信息相結(jié)合，通過一定的仲裁方式來決定下一跳路由節(jié)點的算法.

本文路由節(jié)點的數(shù)據(jù)來自兩個方面，分別是從其他路由節(jié)點輸入到緩存和本地路由節(jié)點輸出的，首先從緩沖區(qū)中取出數(shù)據(jù)先判斷該數(shù)據(jù)的優(yōu)先級，如果是優(yōu)先級高則優(yōu)先取得輸出權(quán)，(1)假如是從豎直緩沖區(qū)取出數(shù)據(jù)則直接傳輸?shù)奖竟?jié)點目的IP核;(2)如果是水平緩沖區(qū)先直接判斷是否本路由節(jié)點就是目的節(jié)點，如果不是則把輸入進行豎直方向廣播，如果是就直接判斷是本路由節(jié)點的哪一個IP核;(3)如果是從IP核直接輸出的數(shù)據(jù)，那么就先判斷目的IP核是否為本路由節(jié)點，如果是就直接輸入IP核，如果不是則先判斷水平方向是否一致，如果不一致則在水平方向進行廣播，如果是就直接進入豎直方向廣播.當發(fā)現(xiàn)不是高優(yōu)先級時，那么就將進入計數(shù)器仲裁方式，通過自身計數(shù)器數(shù)值大小最高的取得輸出權(quán)按照同樣的方式進行傳輸，如果沒有獲取到優(yōu)先權(quán)，那么就將進入下一輪回的等待，計數(shù)器要加1.其中當取得輸出權(quán)時，必須在交叉開關(guān)陣列中標識為1，說明已經(jīng)被占用，其他輸入端口想競爭時，直到數(shù)據(jù)微片輸出完(標志位為0)時才能再次競爭資源，

3 實驗結(jié)果

本文詳細介紹了MECS路由器結(jié)構(gòu)，并用模擬仿真軟件Modelsim10.0版本實現(xiàn)，采用verilog語言編寫而成的，實例化64個IP核16個路由器節(jié)點，每個路由器節(jié)點集成有4個內(nèi)部IP核，連接成4×4MECS網(wǎng)絡，

如圖6所示，目的是從第1個路由節(jié)點(編號00)第1個IP核發(fā)出數(shù)據(jù)(00_0111_11_1_0000000，其中最高兩位是00，說明是頭微片，)傳輸?shù)降?個節(jié)點的第4個IP核位置，由于此數(shù)據(jù)包擁有高優(yōu)先級1，則比其他普通數(shù)據(jù)擁有競爭資源優(yōu)先傳輸數(shù)據(jù).IP核在路由節(jié)點(編號0000)發(fā)出數(shù)據(jù)判斷出要X廣播，由于設置了其他IP核也發(fā)出數(shù)據(jù)進行Y廣播，存在競爭資源，如圖所示得到了權(quán)限，進行廣播，不用存儲.數(shù)據(jù)在水平方向其他的路由節(jié)點進行判斷接收，第三個路由節(jié)點(編碼0011)判斷數(shù)據(jù)符合自己，則把數(shù)據(jù)存入Xport1緩沖區(qū)中，通過FIFO得到數(shù)據(jù)進行判斷，發(fā)現(xiàn)是要進行Y廣播，則要跟路由其他水平緩沖區(qū)和IP核其他發(fā)出Y廣播的進行競爭端口權(quán)限，圖中競爭失敗，原因是此通道已經(jīng)被使用了，等待一組微片時間，然后得到權(quán)限，輸出到第7個路由節(jié)點(0111)Yport1緩沖區(qū)，由于同樣的原因，競爭失敗，之后因為高優(yōu)先級得到輸入權(quán)限，第4個IP核成功接收數(shù)據(jù).

圖6 實驗結(jié)果Fig.6 The experimental results

往每個IP核注入32 Bit*5*20數(shù)據(jù)量，初始化數(shù)據(jù)向指定IP核傳輸數(shù)據(jù)，每個路由節(jié)點最多共有6路并行工作，實際整個傳輸過程有16個路由節(jié)點共有63路并行工作，原因是數(shù)據(jù)先后注入并傳輸?shù)街付康膫鬏敚凑章酚伤惴ㄒ来蝹鬟f存在時間差以及數(shù)據(jù)沒覆蓋所有鏈路導致，當更多數(shù)據(jù)在網(wǎng)絡傳輸時，該拓撲結(jié)構(gòu)的傳輸路徑短和多路并發(fā)優(yōu)勢就發(fā)揮出來.在功能仿真下［16］，以1 ns為時間單位，完成時間為306 ns，理想時間是200 ns，而MESH需要時間是438 ns.其中MECS位寬是一個flit單位32 Bit，平均帶寬是6.69*105Bit/s，其與理想狀況相比，同一路由節(jié)點各Cache內(nèi)共同競爭水平或豎直方向時要發(fā)生資源競爭，按照高優(yōu)先級后按計時器優(yōu)先級規(guī)則占用資源，從而導致時間延遲，比理想狀況直接有鏈路到達時間慢，但節(jié)省更多硬件資源.

實驗證明，本文所設計的拓撲網(wǎng)絡能成功發(fā)送和接收數(shù)據(jù)，實現(xiàn)無差錯、無丟失，通過與2DMesh相比較，在注入通信量很大的情況下評估整體網(wǎng)絡性能，通過波形圖體現(xiàn)本拓撲網(wǎng)絡比后者在時間延遲方面有較大的縮短，通過設置不同數(shù)目虛擬通道以及注入不同的數(shù)據(jù)包總量時，發(fā)現(xiàn)當虛擬通道為4時，延時最少，虛擬通道利用率較高.結(jié)果表明，該結(jié)構(gòu)適用于片上網(wǎng)絡的應用.

4 結(jié)束語

近年來，眾多學者對NoC的拓撲網(wǎng)絡研究主要集中在MESH和Torus上，并在此基礎上不斷完善，但由于各自缺陷，發(fā)展已受到限制.本文提及的架構(gòu)思想原理新穎，物理實現(xiàn)發(fā)展正在加速成熟，擁有網(wǎng)絡直徑小、實現(xiàn)技術(shù)容易和節(jié)省硬件開銷等優(yōu)點.從仿真結(jié)果看，相比傳統(tǒng)的拓撲網(wǎng)絡，MECS確實擁有傳輸延遲小、吞吐量大、所消耗功能低和硬件資源節(jié)省等眾多優(yōu)勢，而且在物理布局布線方面也不會存在技術(shù)問題，因此這結(jié)構(gòu)將會是NoC發(fā)展的一個重要研究方向，給CMP芯片廠商巨大的推力.本研究內(nèi)容交換機制為虛擬直通技術(shù)可能存在一定的限制性，采用沖孔交換技術(shù)跟虛擬通道技術(shù)優(yōu)化結(jié)合和解決傳輸熱點問題是筆者以后著重研究的課題.

［1］William J D，Brian T.Principles and P Practices of Interconnection Networks［M］.San Francisco:Morgan Kaufmann，2004.

［2］陳芳露，陸雯青，虞志益，等.一種新型片上網(wǎng)絡互連結(jié)構(gòu)的仿真和實現(xiàn)［J］.小型微型計算機系統(tǒng)，2010，31(5):883-887.Chen F L，Lu W Q，Yu Z Y，et al.Simulation and implementation of a new NoC-based interconnection network［J］.Joumal of Chinese Computer Systems，2010，31(5):883-887

［3］Grot B，Hestness J，Keckler S W，et al.Express cube topologies for on-chip interconnects［J］.IEEE 15th International Symposium，2009，6(5)，163-174.

［4］張旺，汪金輝，侯立剛，等.基于FPGA的片上網(wǎng)絡虛擬通道控制器的設計［J］.微電子學與計算機，2012，29(5):10-14.Zhang W，Wang J H，Hou L G，et al.The design of networdon-chip virtual channel controller based on FPGA［J］.Microelectronics＆Computer，2012，29(5):10-14.

［5］萬玉鵬，吳寧.NoC路由單元的系統(tǒng)級設計［J］.蘇州科技學院學報:工程技術(shù)版，2009，22(2):61-64+68.Wan Y P，Wu N.NoC system’s design of router［J］.Suzhou of University of Science and Technology:Engineering and Technology，2009，22(2):61-64+68.

［6］Lehtonen T，Liljeberg P，Plosila J.Fault tolerance analysis of NoC architectures circuits and systems［J］.IEEE International Symposium on Circuits and Systems 2007，2(2):27-30.

［7］王榮陽，王科.基于NIRGAM的片上網(wǎng)絡性能仿真［J］.航空電子技術(shù)，2014，45(1):30-34.Wang R Y，Wang K.Performance simulation of network-onchip based on NIRGAM［J］.Avionics Technology，2014，45(1):30-34.

［8］周芳，吳寧，周磊，等.面向低功耗的片上網(wǎng)絡虛通道分配算法［J］.東南大學學報:自然科學版，2013，43(2):263-267.Zhou F，Wu N，Zhou L，et al.Low-power-aware virtual channel allocation algorithm for network on chip［J］.Journal of Southeast University:Natural Science Edition，2013，43(2):263-267.

［9］劉炎華，孫玲，賴宗聲.一種用于片上網(wǎng)絡的異步共享FIFO設計［J］.微電子學與計算機，2013，30(7):159-162.Liu Y H，Sun L，Lai Z S.Design of a asynchronous shared-FIFO for NoC［J］.Microelectronics＆Computer，2013，30(7):159-162.

［10］衡霞，支亞軍，韓俊剛.基于片上網(wǎng)絡多處理器QoS研究與設計［J］.計算機科學，2013，40(6A):220-222.Heng X，Zhi Y J，Han J G.Based on network on chip of multiprocessor QoS mechanism research and design［J］.Computer Science，2013，40(6A):220-222.

［11］相滬平.網(wǎng)絡廣播及其實現(xiàn)原理［J］.甘肅科技，2009，25(1):66-67.Xiang H P.Broadcast network and Implementation［J］.Gansu Science and Technology，2009，25(01):66-67.

［12］虞瀟，李麗，張宇昂，等.一種面向功耗免死鎖三維全動態(tài)3D NoC路由算法［J］.電子學報，2013，41(2):329-334.Yu X，Li L，Zhang Y A，et al.A power-aware dead lock avoid three-dimensional full-adaptive routing algorithm for 3D NoC［J］.Acta Electronica Sinica，2013，41(02):329-334.

［13］王崢，顧華璽，楊燁，等.片上網(wǎng)絡交換機制的研究［J］.中國集成電路，2007，16(12):22-27.Wang Z，Gu H X，Yang Y，et al.A study of switching mechanisms in network-on-chip［J］.China Integrated Circuit，2007，16(12):22-27.

［14］趙國鴻，吳虎城.分布式總線仲裁器的設計［J］.計算機工程與科學，1998，20(02):11-14+70.Zhao G H，Wu H C.Design of the distributed bus arbiter［J］.Computer Engineering＆Science，1998，20(02):11-14+70.

［15］王丹丹，郭大昌，王靜.星圖應用米哈爾頓拉丁方的并行路由算法［J］.廣東工業(yè)大學學報，2011，28(1):62-67.Wang D D，Guo D C，Wang J.A parallel routing algorithmon star graph network employing the hamiltonian circuit latin square［J］.Journal of Guangdong University of Technology，2011，28(1):62-67.

［16］張宇華.基于可編程邏輯器件技術(shù)的基本模型機實驗的設計與實現(xiàn)［J］.廣東工業(yè)大學學報:社會科學版，2010，S1:49-51.Zhang Y H.The design and implementation of the basic model machine based on complex programmable logic device(CPLD)technology［J］.Journal of Guangdong University of Technology:Social Sciences Edition，2010，S1:49-51.