基于OPNET的片上網(wǎng)絡(luò)路由算法的建模與仿真

陳良昌，劉召軍，張彥軍

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

1 引言

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

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

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

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

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

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

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

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

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

圖2 路由算法流程圖

3 OPNET模型建立

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

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

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

3.2 節(jié)點層

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

圖4 節(jié)點層模型圖

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

3.3 進程層

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

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

圖5 dest_select模塊進程層模型

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

圖6 queue模塊進程層模型

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

圖7 proc模塊進程層模型

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

圖8 arbiter模塊進程層模型

4 仿真研究

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

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

圖9 時間間隔為3s的各鏈路吞吐量

圖10 時間間隔為10s的各鏈路吞吐量

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

圖11 時間間隔為10s的路徑圖

圖12 時間間隔為3s的路徑圖

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

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

圖13 端到端平均延時

5 結(jié)語

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