蘇 新 陳永平

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

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

一種基于3Dmesh的NOC路由算法設(shè)計(jì)與分析

蘇 新1,2陳永平2

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

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

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

片上網(wǎng)絡(luò)；拓?fù)洌宦酚桑?Dmesh

1 引言

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

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

2 NoC中的拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

圖 1 （a）2Dmesh結(jié)構(gòu) （b）2DTorus結(jié)構(gòu) （c）3DMesh結(jié)構(gòu)

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

2.2 超立方體結(jié)構(gòu)（Hypercube）和胖樹結(jié)構(gòu)

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

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

圖 2 （a）3 立方體結(jié)構(gòu) （b）胖樹結(jié)構(gòu)

另外還有一些其他的拓?fù)浣Y(jié)構(gòu)，比如蝶網(wǎng)結(jié)構(gòu)、八角形結(jié)構(gòu)等，在此不一一介紹。

3 NOC中的路由算法

NoC的拓?fù)浣Y(jié)構(gòu)保證了每個(gè)節(jié)點(diǎn)都可以發(fā)送數(shù)據(jù)到其他節(jié)點(diǎn)，路由算法決定數(shù)據(jù)包從源節(jié)點(diǎn)開始選擇一條路徑將數(shù)據(jù)包傳送到目標(biāo)節(jié)點(diǎn)。因此，路由算法對(duì)NoC的性能也是至關(guān)重要的。路由算法根據(jù)不同的分類方法可以分為不同的類別，其中一種分類方法是將路由算法分為確定性路由和自適應(yīng)路由。

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

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

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

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

4 3Dmesh結(jié)構(gòu)上的路由算法

4．1 改進(jìn)的XY路由

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

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

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

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

4．3 基于3Dmesh路由算法

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

圖3 （a）3×4×4的3DMesh結(jié)構(gòu)的坐標(biāo)體系 （b）0平面上節(jié)點(diǎn)的節(jié)點(diǎn)編碼

4．4 示例說明

假設(shè)在一個(gè)4×4×4的3D結(jié)構(gòu)中，源節(jié)點(diǎn)的位置為（0，0，2），目標(biāo)節(jié)點(diǎn)的位置為（2，3，0），根據(jù)上述 3D 路由算法，途經(jīng)的節(jié)點(diǎn)為（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 算法特性分析

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

[6]歐陽(yáng)一鳴，董少周，梁華國(guó).基于2DMesh的NoC的路由算法設(shè)計(jì)與仿真[J].計(jì)算機(jī)工程，2009，35（22）：227-229.

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

[8]沈皓，韓國(guó)棟，黃萬(wàn)偉.片上網(wǎng)絡(luò)路由技術(shù)研究[J].通信技術(shù)，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

安徽省自然科學(xué)研究項(xiàng)目（項(xiàng)目編號(hào)：KJ2010B223）

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

責(zé)任編輯：陳 侃