陳良昌，劉召軍，張彥軍

(1.中北大學(xué)儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030051；2.中北大學(xué)電子測(cè)試技術(shù)重點(diǎn)實(shí)驗(yàn)室，山西 太原 030051)

1 引言

隨著大規(guī)模集成電路和半導(dǎo)體技術(shù)的快速發(fā)展，在有限的空間中，可以放置越來(lái)越多的電子器件。這就使得越來(lái)越多的功能模塊可以集成在一塊芯片上，片上系統(tǒng)(System-on-Chip，SoC)的概念應(yīng)運(yùn)而生[1]。片上系統(tǒng)包含多個(gè)可以實(shí)現(xiàn)某一功能的知識(shí)產(chǎn)權(quán)核(Intellectual Property，IP)，這些知識(shí)產(chǎn)權(quán)核通過總線的方式與處理器保持通信[2]。但由于總線帶寬的限制，IP核與處理器之間的通信會(huì)受到制約，產(chǎn)生一定的延時(shí)。片上系統(tǒng)所集成的IP核越多延時(shí)越高，集成電路芯片的工作效率就會(huì)受到很大的影響[3]。

為了解決總線通信中存在的這些問題，研究人員從計(jì)算機(jī)網(wǎng)絡(luò)受到啟發(fā)，提出了片上網(wǎng)絡(luò)(Network on Chip，NoC)這樣全新的通信架構(gòu)[4]。文獻(xiàn)[5]介紹了片上網(wǎng)絡(luò)應(yīng)用在集成電路上的依據(jù)與原理。與片上系統(tǒng)不同的是，IP核連接在路由節(jié)點(diǎn)上，路由節(jié)點(diǎn)間相互連接，形成一個(gè)網(wǎng)絡(luò)[6]。在片上網(wǎng)絡(luò)中，每個(gè)IP核在與處理器進(jìn)行通信的時(shí)候，有很多條鏈路可以選擇。這樣就避免了數(shù)據(jù)傳輸過程中因帶寬不夠而造成的不必要等待，很好的解決了IP核與處理器之間通信的時(shí)延問題[7]。但是，在片上網(wǎng)絡(luò)的熱點(diǎn)區(qū)域很容易發(fā)生堵塞，所以片上網(wǎng)絡(luò)路由的研究成為當(dāng)前片上網(wǎng)絡(luò)研究的一個(gè)重要方向[8]。

片上網(wǎng)絡(luò)路由算法的研究過程中，國(guó)外主要把算法分為兩種類型：確定性路由算法和自適應(yīng)路由算法[9]。其中確定性路由算法是最簡(jiǎn)單和最容易實(shí)現(xiàn)的路由算法。但是確定性路由算法由于其本身的局限性，在大量數(shù)據(jù)包進(jìn)入網(wǎng)絡(luò)時(shí)，由于不能自主選擇路徑，存在平均延時(shí)較大，鏈路利用率不高等缺點(diǎn)。在自適應(yīng)路由算法中，目前研究最簡(jiǎn)單的是維序XY路由算法，MIT的RAW、Tile64以及Intel公司的Tera-Scale都采用這種算法進(jìn)行NoC上的數(shù)據(jù)通信[10]。國(guó)內(nèi)對(duì)片上網(wǎng)絡(luò)的研究較國(guó)外起步晚，主要研究是對(duì)原有的通用路由算法進(jìn)行改進(jìn)。本文路由算法采用兩種約束條件，提高了節(jié)點(diǎn)間數(shù)據(jù)路由的自適應(yīng)性，大大提高了數(shù)據(jù)傳輸?shù)亩藢?duì)端延時(shí)和鏈路利用率。

2 片上網(wǎng)絡(luò)路由算法

路由算法在很大程度上決定著片上網(wǎng)絡(luò)的各項(xiàng)性能。目前，片上網(wǎng)絡(luò)硬件搭建最普遍的是在二維拓?fù)浣Y(jié)構(gòu)下展開的。所以本文基于最典型的4×4 2D-Mesh結(jié)構(gòu)對(duì)片上網(wǎng)絡(luò)的一種路由算法進(jìn)行仿真。該路由算法通過兩個(gè)步驟的約束條件對(duì)數(shù)據(jù)包進(jìn)行路徑的選擇。第一步，比較中間地址與目的地址的坐標(biāo)；第二步，比較各個(gè)通道間鏈路利用率的大小。

各個(gè)節(jié)點(diǎn)的地址由(x，y)兩個(gè)參數(shù)表示，傳輸方向由E、S、W、N、L表示，分別代表東、南、西、北、本地五個(gè)傳輸方向，如圖1所示。節(jié)點(diǎn)源地址用(xs，ys)表示，目的地址用(xd，yd)表示，在數(shù)據(jù)包傳輸?shù)倪^程中，地址是實(shí)時(shí)變化的，稱為中間地址，用(xm，ym)表示。

圖1 片上網(wǎng)絡(luò)各節(jié)點(diǎn)坐標(biāo)

中間地址與目的地址的比較關(guān)系有以下8種情況。①當(dāng)xm=xd且ymyd時(shí)，數(shù)據(jù)包向N方向傳輸；③當(dāng)ym=yd且xmxd時(shí)，數(shù)據(jù)包向W方向傳輸；⑤當(dāng)xmxd且ymyd時(shí)，數(shù)據(jù)包在N和E兩個(gè)方向中進(jìn)行選擇；⑧當(dāng)xm>xd且ym>yd時(shí)，數(shù)據(jù)包在N和W兩個(gè)方向中進(jìn)行選擇。

之后，比較各個(gè)通道間的鏈路利用率，主要是對(duì)上一約束條件中有兩種路徑選擇的情況進(jìn)行再次判斷，以確定數(shù)據(jù)傳輸?shù)穆窂?。它通過比較兩條路徑上的鏈路利用率大小，選擇鏈路利用率小的路徑進(jìn)行傳輸。路由算法具體流程圖如圖2所示。

圖2 路由算法流程圖

3 OPNET模型建立

3.1 網(wǎng)絡(luò)層

OPNET[11]-[13]的網(wǎng)絡(luò)層建模主要描述了模型的拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)傳輸?shù)姆绞?，本次建模是基?×4 2D-Mesh結(jié)構(gòu)建立的片上網(wǎng)絡(luò)數(shù)據(jù)傳輸模型。如圖3所示，由16個(gè)節(jié)點(diǎn)和24條鏈路構(gòu)成。根據(jù)數(shù)據(jù)在網(wǎng)絡(luò)模型中傳輸?shù)囊螅溌凡捎萌p工鏈路。

圖3 網(wǎng)絡(luò)層模型圖

3.2 節(jié)點(diǎn)層

根據(jù)所連接的鏈路的個(gè)數(shù)的不同，建立三種類型的節(jié)點(diǎn)。主要區(qū)別在于發(fā)信機(jī)和接信機(jī)的數(shù)量不同和仲裁模塊接收來(lái)自各個(gè)方向的統(tǒng)計(jì)量的數(shù)量不同。其中node0、3、13、16節(jié)點(diǎn)模型如圖4(a)所示，node1、2、4、7、8、11、13、14節(jié)點(diǎn)的模型如圖4(b)所示，node5、6、9、10節(jié)點(diǎn)模型如圖4(c)所示。節(jié)點(diǎn)層的建模主要包括rcv模塊、xmt模塊、src模塊、queue模塊、dest_select模塊、arbiter模塊、proc模塊、fifo模塊和sink模塊。

圖4 節(jié)點(diǎn)層模型圖

從各個(gè)方向傳輸?shù)奖竟?jié)點(diǎn)的數(shù)據(jù)包，通過rcv模塊接收后傳輸?shù)絨ueue模塊進(jìn)行存儲(chǔ)，數(shù)據(jù)包想要傳輸?shù)絧roc模塊，需要經(jīng)過arbiter模塊的仲裁。arbiter模塊收集來(lái)自queue模塊和proc模塊的統(tǒng)計(jì)量并進(jìn)行分析，反饋給queue模塊一個(gè)統(tǒng)計(jì)量來(lái)控制queue模塊中的數(shù)據(jù)包傳輸?shù)絧roc模塊中。proc模塊首先對(duì)數(shù)據(jù)包的中間地址進(jìn)行更新，然后確定數(shù)據(jù)包的傳輸方向。之后將數(shù)據(jù)包傳輸?shù)较鄳?yīng)方向的fifo模塊中，fifo模塊再將數(shù)據(jù)包傳輸?shù)絰mt模塊發(fā)送出去。src模塊用來(lái)產(chǎn)生數(shù)據(jù)包，然后由dest_select模塊標(biāo)定數(shù)據(jù)包的源地址和目的地址。sink模塊用來(lái)銷毀目的地址為本節(jié)點(diǎn)的數(shù)據(jù)包。

3.3 進(jìn)程層

OPNET進(jìn)程層通過構(gòu)建狀態(tài)轉(zhuǎn)移圖和Proto-C語(yǔ)言編程，來(lái)模擬節(jié)點(diǎn)層各個(gè)模塊內(nèi)部的工作狀態(tài)[14]。其中xmt模塊與rcv模塊分別為發(fā)信機(jī)模塊、接收機(jī)模塊，用來(lái)發(fā)送和接收數(shù)據(jù)包，無(wú)進(jìn)程模型。src模塊使用OPNET提供的simple_source進(jìn)程模型，fifo模塊使用acb_fifo進(jìn)程模型，sink模塊使用sink進(jìn)程模型。其余進(jìn)程模型根據(jù)片上網(wǎng)絡(luò)路由方法的具體內(nèi)容進(jìn)行設(shè)計(jì)。

dest_select模塊的進(jìn)程層模型如圖5所示。首先執(zhí)行idle狀態(tài)的進(jìn)入執(zhí)行(Enter Executives)對(duì)本節(jié)點(diǎn)的地址進(jìn)行設(shè)定，然后當(dāng)有數(shù)據(jù)流到來(lái)時(shí)，觸發(fā)PK_ARRVL中斷，執(zhí)行rout_pk()函數(shù)。將本節(jié)點(diǎn)的地址賦值給數(shù)據(jù)包源地址，并設(shè)置數(shù)據(jù)包的目的地址。

圖5 dest_select模塊進(jìn)程層模型

queue模塊的進(jìn)程層模型如圖6所示。queue模塊與fifo模塊都為隊(duì)列模塊，不同的是進(jìn)入queue模塊的數(shù)據(jù)包必須接受到來(lái)自arbiter模塊的傳輸命令后，才能移出隊(duì)列。首先執(zhí)行init狀態(tài)進(jìn)行一系列的初始化設(shè)定和統(tǒng)計(jì)量的定義，然后跳轉(zhuǎn)到wait狀態(tài)進(jìn)行等待。當(dāng)有數(shù)據(jù)流到來(lái)時(shí)觸發(fā)ARRIVAL中斷，跳轉(zhuǎn)到insert狀態(tài)，將傳輸來(lái)的數(shù)據(jù)包插入到隊(duì)列中去。當(dāng)來(lái)自arbiter模塊的統(tǒng)計(jì)流到來(lái)時(shí)觸發(fā)FLOW_CONTROL中斷，跳轉(zhuǎn)到svc_start狀態(tài)。當(dāng)統(tǒng)計(jì)流中有arbiter模塊反饋來(lái)的傳輸命令時(shí)，產(chǎn)生一個(gè)自中斷。此時(shí)觸發(fā)SVC_COMPLETION中斷，跳轉(zhuǎn)到svc_compl狀態(tài)，使數(shù)據(jù)包強(qiáng)制移出隊(duì)列，傳輸?shù)絧roc模塊。當(dāng)模塊處于wait狀態(tài)時(shí)，會(huì)產(chǎn)生統(tǒng)計(jì)流給arbiter模塊。表示模塊空閑，可以傳送數(shù)據(jù)包。

圖6 queue模塊進(jìn)程層模型

proc模塊的進(jìn)程層模型如圖7所示。首先執(zhí)行init狀態(tài)的Enter Executives對(duì)本節(jié)點(diǎn)的地址進(jìn)行設(shè)定，跳轉(zhuǎn)到idle狀態(tài)。當(dāng)有數(shù)據(jù)流到來(lái)時(shí)，觸發(fā)PK_ARRVL中斷，執(zhí)行rout_pk()函數(shù)。更新數(shù)據(jù)包的地址，并根據(jù)上述約束條件進(jìn)行路徑選擇，確定數(shù)據(jù)包的傳輸方向。之后將數(shù)據(jù)包傳輸?shù)较鄳?yīng)方向的fifo模塊中，準(zhǔn)備發(fā)送出去。當(dāng)模型中無(wú)數(shù)據(jù)流的時(shí)候，會(huì)產(chǎn)生統(tǒng)計(jì)流給arbiter模塊。表示模塊空閑，可以接收數(shù)據(jù)包。

圖7 proc模塊進(jìn)程層模型

arbiter模塊的進(jìn)程層模型如圖8所示。Init狀態(tài)中對(duì)控制各個(gè)queue模塊的統(tǒng)計(jì)量進(jìn)行設(shè)定，然后跳轉(zhuǎn)到idel狀態(tài)。當(dāng)同時(shí)接收到某個(gè)queue模塊的空閑統(tǒng)計(jì)流和proc模塊的空閑統(tǒng)計(jì)流后，便會(huì)產(chǎn)生一個(gè)統(tǒng)計(jì)流傳送到相應(yīng)的queue模塊中。若有多個(gè)queue模塊滿足條件，則隨機(jī)選擇一個(gè)queue模塊發(fā)送統(tǒng)計(jì)流。

圖8 arbiter模塊進(jìn)程層模型

4 仿真研究

經(jīng)過以上三個(gè)層次的建模后，片上網(wǎng)絡(luò)模型已經(jīng)搭建完成?；谠撃Ｐ瓦M(jìn)行仿真，測(cè)試本模型數(shù)據(jù)傳輸?shù)耐掏铝亢蜁r(shí)延性能。比較網(wǎng)絡(luò)在正常狀態(tài)和繁忙狀態(tài)下的吞吐量，觀察在數(shù)據(jù)量較大的情況下，數(shù)據(jù)包選擇路徑的情況；將該路由算法與確定性路由算法的平均延時(shí)進(jìn)行比較。在模型中設(shè)置7個(gè)節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包，相應(yīng)的設(shè)置7個(gè)節(jié)點(diǎn)接收數(shù)據(jù)包。數(shù)據(jù)包具體的傳輸為node0到node10，node3到node9，node6到node12，node8到node1，node10到node4，node11到node2，node15到node7。

在節(jié)點(diǎn)層添加source interarrival time的參數(shù)值3和10，代表數(shù)據(jù)包產(chǎn)生的間隔分別為3s和10s。這樣來(lái)區(qū)分大量數(shù)據(jù)傳輸情況與正常數(shù)據(jù)傳輸情況。設(shè)置仿真時(shí)間長(zhǎng)度為2000秒。實(shí)驗(yàn)一的source interarrival time設(shè)置為3，實(shí)驗(yàn)二的source interarrival time設(shè)置為10，其它條件都一樣。分別得出在數(shù)據(jù)包產(chǎn)生時(shí)間間隔為3s和10s時(shí)的各個(gè)鏈路的吞吐量如圖9和圖10所示。

圖9 時(shí)間間隔為3s的各鏈路吞吐量

圖10 時(shí)間間隔為10s的各鏈路吞吐量

根據(jù)兩個(gè)實(shí)驗(yàn)的吞吐量可以得出兩個(gè)實(shí)驗(yàn)中數(shù)據(jù)包的傳輸路徑，如圖11和圖12所示。

圖11 時(shí)間間隔為10s的路徑圖

圖12 時(shí)間間隔為3s的路徑圖

可以看出，在包產(chǎn)生時(shí)間間隔為10秒的時(shí)候，節(jié)點(diǎn)node5，node6為熱點(diǎn)節(jié)點(diǎn)。當(dāng)時(shí)間間隔變小，產(chǎn)生的數(shù)據(jù)量變多的時(shí)候，仿真模型會(huì)適當(dāng)?shù)谋荛_熱點(diǎn)節(jié)點(diǎn)node5和node6，尋找新的路徑進(jìn)行傳輸。表明該模型在遇到大量數(shù)據(jù)傳輸?shù)臅r(shí)候，可以根據(jù)各節(jié)點(diǎn)的利用率，有效的選擇合適的路徑，避免了大量數(shù)據(jù)因選擇同一路徑而造成的擁堵。

對(duì)傳統(tǒng)的確定性路由算法進(jìn)行建模，與本文所訴路由算法相比。在數(shù)據(jù)包傳輸?shù)脑吹刂放c目的地址相同，產(chǎn)生數(shù)據(jù)包時(shí)間間隔為3s的條件下，查看仿真的端到端的平均延時(shí)，如圖13所示。起初的時(shí)候由于鏈路暢通延時(shí)很小，隨著數(shù)據(jù)包產(chǎn)生數(shù)量的增多，延時(shí)會(huì)迅速增加，之后產(chǎn)生包和銷毀包的數(shù)量達(dá)到動(dòng)態(tài)平衡，故在曲線上顯示為一條直線?？梢钥闯觯c傳統(tǒng)的確定性路由相比，該路由算法平均延時(shí)小，傳輸速度快。

圖13 端到端平均延時(shí)

5 結(jié)語(yǔ)

本文提出了一種片上網(wǎng)絡(luò)路由算法，建立了一個(gè)基于4×4 2D-Mesh拓?fù)浣Y(jié)構(gòu)的片上網(wǎng)絡(luò)模型，并對(duì)該模型進(jìn)行了網(wǎng)絡(luò)層、節(jié)點(diǎn)層、進(jìn)程層的建模。對(duì)該模型在正常狀態(tài)和繁忙狀態(tài)下進(jìn)行仿真，分別得出各個(gè)鏈路的吞吐量，在此基礎(chǔ)分析后得出數(shù)據(jù)包的傳輸路徑，進(jìn)行比較?？梢钥闯鲈诖罅繑?shù)據(jù)包涌入網(wǎng)絡(luò)的時(shí)候，會(huì)根據(jù)各個(gè)節(jié)點(diǎn)的具體情況，選擇傳輸路徑。減少某些熱點(diǎn)節(jié)點(diǎn)的壓力，有效的避免了因數(shù)據(jù)量大而造成的延時(shí)增大或堵塞現(xiàn)象。與傳統(tǒng)的確定性路由相比，延時(shí)更小，效率更高。