蘇 新 陳永平

（1 合肥工業(yè)大學，安徽 合肥 230009）

（2 馬鞍山職業(yè)技術學院，安徽 馬鞍山 243031）

一種基于3Dmesh的NOC路由算法設計與分析

蘇 新1,2陳永平2

（1 合肥工業(yè)大學，安徽 合肥 230009）

（2 馬鞍山職業(yè)技術學院，安徽 馬鞍山 243031）

隨著半導體技術的高速發(fā)展，集成度越來越高，片上系統(tǒng)由于其總線式結構，存在的許多問題，使其無法滿足功能復雜的應用需求，于是，片上網(wǎng)絡越來越受人們的關注。文中在介紹了片上網(wǎng)絡的拓撲結構和路由算法的基礎之上，重點研究了基于3Dmesh結構上的片上網(wǎng)絡路由技術，并提出了一種適用于小規(guī)模的、3Dmesh結構上的路由算法，并對算法的相關特性作了簡單的分析。

片上網(wǎng)絡；拓撲；路由；3Dmesh

1 引言

隨著半導體技術的發(fā)展，未來集成系統(tǒng)將包含億萬個晶體管，由數(shù)百個IP核組成。這些IP核，面對涌現(xiàn)出的各種功能復雜的多媒體和網(wǎng)絡應用，應該能提供豐富的多媒體服務和網(wǎng)絡服務。這些IP核的有效合作 (例如，高效的數(shù)據(jù)傳輸），可以通過在芯片級上改變通信策略來達到。能容納這么多IP核，且能滿足對通信和數(shù)據(jù)傳輸?shù)男枰慕Y構，即是片上網(wǎng)絡（Network-on-Chip，NoC）結構。

NoC技術的核心思想是計算機網(wǎng)絡技術移植到集成電路芯片中來，從體系結構上解決片上系統(tǒng)（System-on-a-Chip，SoC）總線式結構帶來的一系列問題：可擴展性差、總線通訊效率低、單一時鐘同步等。NoC具有良好的空間擴展性，提供了高效的并行通訊能力，以分組交換作為通訊技術，采用全局異步—局部同步的通訊機制，受到業(yè)界的廣泛關注。從網(wǎng)絡的角度來看，片上網(wǎng)絡研究的重點在于拓撲結構、協(xié)議設計、流量控制、服務質量等。本文基于3Dmesh這種拓撲結構，介紹和分析其上的路由技術，與研究人員共同探討。

2 NoC中的拓撲結構

拓撲結構是NoC中各路由節(jié)點間、路由節(jié)點和處理節(jié)點間通信的物理連接，它確定了路由節(jié)點和路由節(jié)點，以及處理節(jié)點和路由節(jié)點之間的數(shù)據(jù)通路，制約著整個信息傳輸?shù)乃俣?、容錯能力。同時也決定著路由算法的設計以及整個系統(tǒng)的工作效率，從而對整個系統(tǒng)的性能，起著重要的影響。

由于片上網(wǎng)絡不同于傳統(tǒng)意義上的計算機網(wǎng)絡，其拓撲結構在設計時要求應具有對稱、簡單等特征的規(guī)則結構。目前，在對NoC拓撲結構的研究中，常見的規(guī)則的拓撲結構主要有以下幾種：網(wǎng)格/帶環(huán)網(wǎng)絡（Mesh/Torus）、Hypercube（超立方體結構）、胖樹（Fat Tree）結構等。

2.1 網(wǎng)格/環(huán)繞網(wǎng)絡（Mesh/Torus）

在2DMesh/2DTorus結構（如圖1）中，節(jié)點相互連接成一個M行N列的陣列，或是M行N列的2D環(huán)型陣列。這種結構連接簡單，易于部署在芯片上，可擴展性好，鏈路利用率高，因此被廣泛應用在并行處理系統(tǒng)中。但是其網(wǎng)絡直徑和平均距離較大，對于大規(guī)模網(wǎng)絡功耗較大。

另外還有一種3DMesh結構，這種結構是在2DMesh結構上的一種延伸，它將所有節(jié)點部署在多個層次，每個層稱為一個平面（plane），利用三維坐標X、Y、Z來定位每個節(jié)點。通過將節(jié)點分層，當節(jié)點比較多時，會使結構更加清晰，相對于2DMesh，大大縮短了網(wǎng)絡直徑。如圖1所示。

圖 1 （a）2Dmesh結構 （b）2DTorus結構 （c）3DMesh結構

Mesh和Torus結構具有高度的規(guī)則性，每兩個節(jié)點之間的連線長度都相一致，從而在任意兩個鄰接節(jié)點間進行數(shù)據(jù)傳輸時，所消耗的能量基本一致，保證片上網(wǎng)絡整體性能的均衡性。

2.2 超立方體結構（Hypercube）和胖樹結構

相比較于Mesh/Torus結構，超立方體結構有效的減少了每個節(jié)點的度數(shù)，即每個節(jié)點所連接的邊的數(shù)目。例如，在3立方體結構中，任何節(jié)點的度數(shù)都是3，而在2DMesh或Torus結構中，每個節(jié)點的度數(shù)為2n（n為維數(shù)）。如圖2（a）所示。

有人也提出了一種可擴展的胖樹結構，如圖2（b）所示，但該結構的布線復雜度大。隨著胖樹節(jié)點的增加，其節(jié)點的復雜性也隨著增大，對引腳的需求也增加，這在芯片設計中，顯然這是不實際的。

圖 2 （a）3 立方體結構 （b）胖樹結構

另外還有一些其他的拓撲結構，比如蝶網(wǎng)結構、八角形結構等，在此不一一介紹。

3 NOC中的路由算法

NoC的拓撲結構保證了每個節(jié)點都可以發(fā)送數(shù)據(jù)到其他節(jié)點，路由算法決定數(shù)據(jù)包從源節(jié)點開始選擇一條路徑將數(shù)據(jù)包傳送到目標節(jié)點。因此，路由算法對NoC的性能也是至關重要的。路由算法根據(jù)不同的分類方法可以分為不同的類別，其中一種分類方法是將路由算法分為確定性路由和自適應路由。

3．1 確定性路由（Deterministic Routing）

確定性路由在作路徑選擇時，只取決于源節(jié)點和目標節(jié)點的位置，而與網(wǎng)絡當前各節(jié)點的狀態(tài)無關。因為確定性路由是一種比較簡單的路由算法，而且在網(wǎng)絡低擁塞的前提下可以獲得較低的延遲，因此被廣泛使用在NoC中，其中常見的是2Dmesh結構中使用的XY維序路由。本文后面中提到的適用于3Dmesh結構的路由算法就是一種確定性路由算法，其在某一個平面上尋址時采用改進的XY－YX路由算法。

3．2 自適應路由(Adaptive Routing)

自適應路由是指數(shù)據(jù)包傳送的路徑選擇不僅局限于源節(jié)點和目標節(jié)點的位置，而且跟網(wǎng)絡當前的狀態(tài)有關。也就是說，在網(wǎng)絡不同時，即使源節(jié)點和目標節(jié)點位置相同，選擇的路徑可能是不相同的。自適應路由從一定程度上避免了擁塞，提高了網(wǎng)絡的吞吐量，但同時也會帶來死鎖的危險，因此，在設計自適應路由算法時，通常會對某些出口方向作出一些限制。

4 3Dmesh結構上的路由算法

4．1 改進的XY路由

在2Dmesh結構模型中，通常把與每個路由節(jié)點相連接的 4個通道分別用 N（北）、S（南）、W（西）、E（東）進行標識(邊緣節(jié)點按照實際存在情況進行標識)。并規(guī)定2Dmesh結構的默認轉向指的是90o的轉向。在一個2D的陣列中，有8種可能的轉折，構成兩個簡單的回路，XY維序路由不允許使用8種轉折中的4個，當沿－X或+X前進時，做－Y或+Y的折轉是合法的，但是一旦數(shù)據(jù)包沿－Y或+Y前進，它就不能做進一步的轉彎了。

在文獻[6]中提出的XY－YX維序路由算法，其思想是根據(jù)當前節(jié)點和目標節(jié)點的相對位置來選擇X或Y方向。當目的節(jié)點X方向的值小于當前節(jié)點X方向的值時，即目的節(jié)點在當前節(jié)點的西邊，選擇先X后Y；當目的節(jié)點X方向的值大于當前節(jié)點對應的值時，即目的節(jié)點在當前節(jié)點的東邊，選擇先Y后X，從而減輕XY路由算法在X方向產(chǎn)生的阻塞。對應的算法C偽代碼如下：

4．2 3 Dmesh 節(jié)點編碼

在3Dmesh結構模型中，將一個平面，即水平方向上，看成是一個2DMesh結構，分別用X、Y軸來表示，而在垂直方向上，用Z坐標軸表示，這樣，每個節(jié)點的坐標可以用一個三維坐標來唯一確定，圖 3（a）所示是一個 3×4×4 的 3DMesh 結構的坐標體系，圖3（b）所示是0平面上節(jié)點的節(jié)點編碼，第一維表示Z坐標，即節(jié)點所在的平面，第二維表示X坐標，第三維表示Y坐標。

4．3 基于3Dmesh路由算法

數(shù)據(jù)包在傳送過程中，我們假設當前節(jié)點的坐標為(tx，ty，tz)，目標節(jié)點的坐標為（dx，dy，dz）。由于3D結構中的某一個平面，我們可以看成是一個2DMesh結構，因此，當dz=tz相同時，即當前節(jié)點和目標節(jié)點在同一個平面，則可以直接使用上述改進的路由算法，在水平方向上，同一平面中進行路由。若當前節(jié)點和目標節(jié)點不在同一個平面上，即dz≠tz時，則利用垂直連接，向上或向下路由到上一平面或下一平面，直到當前節(jié)點和目標節(jié)點在同一平面為止。算法C偽代碼如下標示：

圖3 （a）3×4×4的3DMesh結構的坐標體系 （b）0平面上節(jié)點的節(jié)點編碼

4．4 示例說明

假設在一個4×4×4的3D結構中，源節(jié)點的位置為（0，0，2），目標節(jié)點的位置為（2，3，0），根據(jù)上述 3D 路由算法，途經(jīng)的節(jié)點為（0，0，2），（1，0，2），（2，0，2），（2，0，1），（2，0，0），（2，1，0），（2，2，0），（2，3，0），如圖 4 所示。

圖4 3D路由算法示例

4．5 算法特性分析

對于NoC中的路由算法，應該具有可達性，健壯性和無死鎖性三個特點?？蛇_性是指在網(wǎng)絡中，從某個節(jié)點出發(fā)，都能找出一條正確的路由傳送至目標節(jié)點。健壯性是指當所選路徑中某一節(jié)點出現(xiàn)擁塞時，可以從另外一條路徑將數(shù)據(jù)包路由到目標節(jié)點。死鎖是指在網(wǎng)絡2個或2個以上的節(jié)點在擁有對方申請資源的同時又去申請對方已經(jīng)擁有的資源，比如緩存。對于上述路由算法，實驗證明是具有可達性的，同時，在同一平面?zhèn)魉蜁r采用的維序路由，是不會出現(xiàn)死鎖的，在文獻[6]中已得到證明，垂直方向上顯然是不會出現(xiàn)死鎖的，而在平面之間傳輸數(shù)據(jù)包時，由于選擇的節(jié)點單一，健壯性會差一點，當垂直連接上的某個節(jié)點擁塞時，會帶來比較大的延遲。

5 結束語

在目前剛興起的NoC的研究中，拓撲結構和路由算法是影響NoC整體性能重要的兩個因素，本文在分析了NoC常見的拓撲結構的基礎上，提出了一種基于3DMesh結構，適用于小規(guī)模片上網(wǎng)絡的路由算法，并對其作出了簡單的分析。

[1]王曉袁.片上網(wǎng)絡系統(tǒng)模型[D].陜西：西安電子科技大學，2008.

[2]馮偉.NoC測試端口選擇方法與Dmesh結構研究[D].安徽：合肥工業(yè)大學，2008.

[3]蔣勇男.片上網(wǎng)絡路由算法及應用研究[D].四川：電子科技大學，2008.

[4]段宜賓，王曉冬，唐磊.片上網(wǎng)絡關鍵技術及仿真方法研究[J].通信技術，2009,42（12）：182-184.

[5]李蕾.應用于NoC的小規(guī)模PRDT（2，1）布線及路由問題的研究[D].河北：河北工業(yè)大學，2006.

[6]歐陽一鳴，董少周，梁華國.基于2DMesh的NoC的路由算法設計與仿真[J].計算機工程，2009，35（22）：227-229.

[7]謝佩博,顧華璽,賈林.片上網(wǎng)絡路由算法的研究[J].計算機工程與設計，2009，30（13）：3078-3081.

[8]沈皓，韓國棟，黃萬偉.片上網(wǎng)絡路由技術研究[J].通信技術，2009，42（5）：125-127.

[9]Fayez Gebali，Haytham Elmiligi.Networks-on-Chips_Theory_and_Practice[M].CRC Press.

DESIGN AND ANALYSIS OF NOC ROUTING ALGORITHM BASED ON 3D MESH

SU Xin1，2CHEN Yong-ping2
（1 Hefei University of Technology,HefeiAnhui230009）（2 Maanshan Technical College,Maanshan Anhui 243031）

With the rapid development of semiconductor technology,the number of transistors on a chip become more and more,because of the bus structure used on the chip,having many flaws in the kind of structure,makes it can not meet the functional needs of complex applications.Therefore,people pay more attention to NoC.In this paper we first introduce the chip in the network topology and routing algorithm,then make more focus on the routing technology based on 3Dmesh structure,and propose a routing algorithm,that can be applied for small-scale,3Dmesh structure,and make the analysis to algorithmic characteristic.

Network-on-Chip（NoC）； Topology； routing； 3Dmesh

TP301.6

A

1672－2868（2010）06－0043－05

2010－08-11

安徽省自然科學研究項目（項目編號：KJ2010B223）

蘇新（1981-），男，安徽馬鞍山人。講師，研究方向：片上網(wǎng)絡。

責任編輯：陳 侃