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

蘇 新 陳永平

（1 合肥工業大學，安徽 合肥 230009）

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

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

蘇 新1,2陳永平2

（1 合肥工業大學，安徽 合肥 230009）

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

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

片上網絡；拓撲；路由；3Dmesh

1 引言

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

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

2 NoC中的拓撲結構

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

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

2.1 網格/環繞網絡（Mesh/Torus）

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

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

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

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

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

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

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

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

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

3 NOC中的路由算法

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

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

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

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

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

4 3Dmesh結構上的路由算法

4．1 改進的XY路由

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

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

4．2 3 Dmesh 節點編碼

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

4．3 基于3Dmesh路由算法

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

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

4．4 示例說明

假設在一個4×4×4的3D結構中，源節點的位置為（0，0，2），目標節點的位置為（2，3，0），根據上述 3D 路由算法，途經的節點為（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中的路由算法，應該具有可達性，健壯性和無死鎖性三個特點。可達性是指在網絡中，從某個節點出發，都能找出一條正確的路由傳送至目標節點。健壯性是指當所選路徑中某一節點出現擁塞時，可以從另外一條路徑將數據包路由到目標節點。死鎖是指在網絡2個或2個以上的節點在擁有對方申請資源的同時又去申請對方已經擁有的資源，比如緩存。對于上述路由算法，實驗證明是具有可達性的，同時，在同一平面傳送時采用的維序路由，是不會出現死鎖的，在文獻[6]中已得到證明，垂直方向上顯然是不會出現死鎖的，而在平面之間傳輸數據包時，由于選擇的節點單一，健壯性會差一點，當垂直連接上的某個節點擁塞時，會帶來比較大的延遲。

5 結束語

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

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

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

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

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

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

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

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

[8]沈皓，韓國棟，黃萬偉.片上網絡路由技術研究[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-），男，安徽馬鞍山人。講師，研究方向：片上網絡。

責任編輯：陳 侃