苏 新 陈永平

（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-），男，安徽马鞍山人。讲师，研究方向：片上网络。

责任编辑：陈 侃