- 1 -
蜂窝网格的虫孔路由算法1
张伟文，杨小帆
重庆大学 计算机学院, 重庆市 （400044）
摘 要:六角形蜂窝网格是一种新近提出的并行多处理机互连网络。蜂窝网格在某些特性上优
于二维网格。不过，这种网络不存在单信道最短路径无死锁路由算法。文中针对该网络设计
了两个部分自适应无死锁虫孔路由算法。一个是基于转弯模型单信道非最短路径路由算法，
另一个则是采用了虚拟双信道的最短路径路由算法。对第二个算法，还进一步使用转弯模型
对其改进。通过仿真实验，结果显示这两个路由算法都具有较好的性能。
关键词: 互连网络; 虚信道; 转弯模型; 无死锁路由; 虫孔
中图法分类号: TP338；TP393
1. 引言
并行多处理器互连网络（简称互连网络），是指处理器已一定方式相互连接而构成的网
络。在互连网络中，为了实现某些功能，处理器之间经常需要交换信息，例如，处理器之间
的任务分配、负载平衡和同步等。大部分这些直接网络是通过交互消息或者报文来实现节点
之间的通信。路由算法则是建立消息或报文在网络中将要执行的传递路径。所以，路由算法
性能的效率会直接影响到并行机的性能。对规则网络来说，利用好网络的拓扑性质才能实现
高效的路由算法。另外，互连网络中路由算法的设计往往也跟采用交换方式相关。在早期的
并行计算机中采用的交换技术主要是电路交换和报文交换技术。这些技术的时延较大，已经
很少应用在并行计算机中了。虫孔交换技术由于时延短，已被广泛应用于当今的并行计算机
中。例如，Cray T3E，Intel Paragon 和曙光系列并行机等。虫孔路由有一个很大的优点是对
数据传输距离不敏感。不过，它相对一般交换技术更加容易引起死锁。解决死锁问题是虫孔
路由设计的难点。
根据图论的知识，已经有许多网络拓扑结构被提出来。一些经典结构（超立方体、网格
等）已被广泛的研究和应用。而一些新的网络结构，研究还比较欠缺。最近，Stojmenovic
提出一种新的网络[1]，六角形蜂窝网格。该网络是一种平面拓扑的互连网络，它类似于二
维网格，不过节点连接度只有 3，比网格少 1，而同时具有类似网格的拓扑性质( 对称性、
低连接度、可递归构造性等 )， 有些特性还优于网格[1，2，3，4]。针对该网络的路由设计
的研究还比较欠缺。文献[1]中提出了一个简单的单播路由算法，不过该算法是死锁的。广
播算法的研究主要有 J. Carle 提出的一种 all-to-all 全广播算法[10]和 Song 针对单口传播方式
提出的一个点广播算法[9]。本文的研究主要是设计了六角形蜂窝网格的两个单播路由算法，
一个是基于转弯模型技术[6]，另一个则是使用了虚信道技术[8]。
1本课题得到教育部博士点基金（2005061101）和教育部新世纪优秀人才资助计划（NCET-05-0759）的资助。
- 2 -
2. 概述
六角形蜂窝网格
六角形蜂窝网格是基于网格连接结构的网络结构。该网络可以递归构造。二维蜂窝网格
可以由一维蜂窝网格外围的每一条边添加一个六角形而构成。同理，H t 可由 H t – 1 外围增
加一层六边形构造而成。t 维蜂窝网格的节点数是 6t2 ，边数是 9t2－3t。
图 1 六角形蜂窝网格 H3
我们可以使用 XYZ 三坐标的坐标系来对蜂窝网格的节点进行编码[1]。以蜂窝网格的中
心为坐标原点，XYZ 三个坐标轴分别平行于六角形的边。经过编码，如果蜂窝网格中两个
节点相邻，那么它们的一个坐标值相差 1，其他两个坐标是相等的。蜂窝网格也是个二部图，
该网络中所有的节点可以分为两组，一组节点（XYZ 坐标之和绝对值为 1）的某个坐标值总
是大于邻接的节点，另一组（XYZ 坐标之和绝对值为 2）则恰恰相反。在下文的讨论中，我
们把第一组标记它为黑节点（该类节点坐标值大于或等于邻接节点的坐标），第二组节点我
们标记它为白节点（该类节点的坐标值小于或等于邻接节点的坐标）。具体实例见图 1 H3 示
意图。
虚信道以及转弯模型
分割物理缓冲增加管理模块可以把一个物理通道虚拟为几个虚信道。利用虚信道技术可
以在一定程度上增加网络的吞吐量和防止死锁发生[8]。通过使用虚信道，可以使得一些本
来死锁的路由算法改进成为无死锁路由算法。
转弯模型是由 Glass 和 Ni 提出的[6]，它提供一种在给定网络条件下开发自适应路由算
法的系统方法。J. Duato 指出如果通道间没有相关环的话，就不会发生死锁。转弯模型是通
过禁止路由中某些转弯来避免路由中的圈的形成，从而避免死锁。基于转弯模型的路由算法
突出优点是对硬件逻辑要求比较简单，成本较低，无需增加虚信道就可以达到无死锁和部分
自适应。
3. 蜂窝网格路由算法设计
基于转弯模型虫孔路由算法
对蜂窝网格的单播算法，Stojmenovic 提出一个最短路径单播路由算法。该路由算法类
似网格的维序路由算法。它依次以节点间编码偏移量递减顺序 XYZ 方向优先路由报文。不
- 3 -
过由于蜂窝网格路由时不可能严格按顺序走完 X 向，再 Y 向，最后 Z 向路由。它必须一正
一负交叉路由，例如 S (1, 2, -1）节点到节点 D (1, 0, 0)的路由路径是 Y－，Z+，Y－。显而
易见，该算法是死锁的。针对蜂窝网格，我们设计了一种非最短路径单播路由算法。该算法
基于转弯模型。
图 2 蜂窝网格转弯（虚线转弯是禁止转弯）
蜂窝网格中的形成抽象圈共有两种，参见图 2。我们可以禁止其中的某些转弯来防止环
的形成。这当中可以有很多选择，图 2 中显示了一种禁止方法，虚线转弯是需要禁止的转弯。
这两个转弯分别是由 Z 向转向 X－和 Y+方向。禁止了这两个转弯就可以防止环的形成，从
而避免的死锁的发生。不过，禁止这两个转弯要实现任意两个节点的路由，必须先得路由完
所有的 X－、Y+两个方向，那么路由的路径就不是最短路径了。但由于前面所言，蜂窝网
格不存在有单通道的最短路径算法的。对于禁止图 2 中的转弯组合，我们设计出一个 X－
Y+优先路由算法。算法描述如下：对节点 A（x1，y1，z1）的报文（被分割为数个微片，来
实现虫孔路由）路由到节点 B（x2，y2，z2）的路径首先顺着 X－，Y+的“之”字形走法，走
完所有的 X－向和 Y+向，然后再选任一最短路径路由至目的结点。当没有路由完 X－向和
Y+向就走到底边时，报文就沿着底边往 Z 向路由然后再路由 X－向或 Y+向。算法的伪代码
参见算法 1。伪代码中，当有几条输出通道可供选择时算法中的选路函数默认以 XYZ 优先
顺序选择输出通道的。算法中节点依前面所言分为黑和白两类，分别标识为 black 和 white。
路由示例可参见图 1 中 A 与 B 点之间的路由。同理，我们还可以构造出其他几种转弯组合，
这里不再详细阐述。
x, y
8n-4-2y, x-1 8n-4-2y, 2n-2-x
8n-5-2y, 0
8n-4+y, 0
x, y
8n-4+y, x-1
8n-5-2y, 0
x, y
8n-4+y, 2n-2-x
8n-5-2y, 0
图 3 节点通道编码
证明算法的无死锁特性，我们使用 Dally 和 SeitZ 提出的方法[5]。该方法是通过对网络
中的通道进行特定编号，如果能使得路由算法所经过的路径通道编号是严格递减或者递增的
话，那么该路由算法是无死锁的。
定理 1：X－Y+优先路由是连接且无死锁的。
证明：在走完所有 X－和 Y+路径之后，报文使用的路由是[1]中提出的最短路径路由，该路
由是连接的，所以，X－Y+优先路由也是连接的。把 N 维蜂窝网格置于二维普通网格之中，
蜂窝网格节点的编号与二维网格一致，节点编号也只使用两坐标( x, y )标识。这样，N 维的
- 4 -
蜂窝网格就嵌入到一个 2N × (4N－1)的网格之中。如图 3 所示，我们把节点分为两类，第一
类是底边节点，第二类是非底边节点的普通节点。对节点边使用两对数来编号。越往南边的
通道编号数值越小，而其他方向则是越远离节点边编号数值就越小。经过编码之后的网格，
我们发现，使用上述的路由算法中，报文所经过的路径总是沿着比原来编码要小的边路由。
根据 Dally 和 SeitZ 的理论，可得出该算法是无死锁的。
算法 1（X－Y+向优先算法）：
输入：当前节点坐标（Xcurrent，Ycurrent，Zcurrent）和目的节点坐标（Xdest，Ydest，Zdest），节点类型
NodeFlag（可由节点坐标值之和的绝对值计算）
输出：选择的输出通道 Channel。
过程：
Xoffset :＝ Xdest － Xcurrent;
Yoffset :＝ Ydest － Ycurrent;
Zoffset :＝ Zdest － Zcurrent;
if (Xoffset < 0 or Yoffset > 0) then
if (Xoffset < 0 and NodeFlag = White) then
/*到达网格底边，X－路径不可用的情况*/
if (X－ is unusable) then
Channel := Z－;
Channel :＝X－;
if (Yoffset > 0 and NodeFlag = Black) then
/*到达网格底边，Y+路径不可用的情况*/
if (Y+ is unusable) then
Channel := Z+;
Channel := Y+;
if (NodeFlag = Black) then
if (Xoffset > 0) then
Channel := X+;
if (Yoffset > 0) then
Channel := Y+;
if (Zoffset > 0) then
Channel := Z+;
if (NodeFlag = White) then
if (Xoffset < 0) then
Channel := X－;
if (Yoffset < 0) then
Channel := Y－;
if (Zoffset < 0) then
Channel := Z－;
/*到达终点,直接传到处理器*/
if (Xoffset = 0 and Yoffset = 0 and Zoffet = 0) then
Channel := internal;
- 5 -
基于虚信道路由算法
为了在六角形蜂窝网络设计最短路径的算法，我们使用虚信道技术来避免死锁。我们对
X 向和 Y 向通道使用两个虚信道 X0，Y0 通道和 X1，Y1 通道，Z 向通道保持单信道不变。
设计路由算法的思想是构造两个虚拟网络，报文根据不同的情况选择不同网络来路由，从而
避免死锁。设计的路由算法（简称为 Double XY 算法）描述如下：当目标节点与源节点的 Z
坐标差大于零时使用 Z 指向其正方向通道和 X0、Y0 通道进行最短路径路由；当目的节点与
源节点的 Z 向坐标差小于零时使用指向 Z 负方向的通道和 X1、Y1 通道进行最短路径路由；
当目的节点与源节点的 Z 向坐标差等于 0 时，则选择可随意 0，1 虚信道之中的一个来进行
路由。路由过程中禁止不同类型通道的切换。该算法是无死锁的，因为 Z 正向和 X，Y 向 0
信道组成的网络可视为一个虚拟网络，它与 Z 负向和 X，Y 向 1 通道构成的虚拟网络不相互
影响，而且每个虚拟网络中路由的路径是单向的，不会形成环路。所以该算法是无死锁的。
伪代码见算法 2，伪代码选路函数为 XYZ 顺序优先以便简化程序。
图 4 双 XY 虚信道转弯模型禁止的转弯
利用转弯模型，我们可以进一步对上述算法进行改进。当增加了 XY 虚信道之后，形成
的抽象圈的种类就达到了 32 种，我们只需禁止其中的六个转弯（图 4 所示）就可以来避免
圈的形成。由于使用了虚信道，存在有 0o 转弯。改进之后的算法主要是多允许了某些 0o转
弯。路由的情况按照目的结点和源节点的坐标偏移量分为六类。每一类之间没有相互重叠，
并覆盖了所有情况的，分类如下：
○1 Zoffset ＜ 0, Xoffset ＞ 0, Yoffset ≤ 0;
○2 Zoffset ＜ 0, Xoffset ≥ 0, Yoffset ＞ 0;
○3 Zoffset ≤ 0, Xoffset ＜ 0, Yoffset ＞ 0;
○4 Zoffset ＞ 0, Xoffset ＜ 0, Yoffset ≥ 0;
○5 Zoffset ＞ 0, Xoffset ≤ 0, Yoffset ＞ 0;
○6 Zoffset ≥ 0, Xoffset ＞ 0, Yoffset ＜ 0;
改进路由算法描述如下：路由过程中只使用最短路径。具体则根据上面的分类情况分别
采用不用策略路由。○2 和○5 类按Double XY算法路由。○1 类路由则先使用虚信道0向X0+、
Y0－通道路由，然后可以转入使用虚信道1和Z通道路由，以后再也不能转用虚信道0。○3 类
路由则先使用虚信道0向X0－、Y0+向路由，然后可以转入使用虚信道1和Z通道路由，但不
能再使用虚信道0。○4 类路由则先使用虚信道1向X1－、Y1+和Z向路由，然后可以转入虚信
道使用虚信道0中X0－、Y0+路由，但不能再使用虚信道1和Z向路由。○6 类路由则先使用虚
信道1向X1+Y1－和Z向路由，然后可以转入虚信道使用虚信道0中通道X0+、Y0－路由，但
不能再使用虚信道1和Z向路由。算法的伪代码略。
算法 2（Double XY 算法）：
输入：当前节点坐标（Xcurrent，Ycurrent，Zcurrent），目的节点坐标（Xdest，Ydest，Zdest），节点类型
NodeFlag 以及源节点 Z 向坐标 Zsource。
- 6 -
输出：选择的输出通道 Channel。
过程：
Xoffset :＝ Xdest － Xcurrent;
Yoffset :＝ Ydest － Ycurrent;
Zoffset :＝ Zdest － Zcurrent;
Zsrcoffset :＝ Zsource － Zdest；
if (Zoffset ≥ 0 and
( Zsrcoffset > 0 or Zsrcoffset = 0 )) then
if (NodeFlag = Black) then
if (Xoffset > 0) then
Channel := X0+;
if (Yoffset > 0) then
Channel := Y0+;
if (Zoffset > 0) then
Channel := Z+;
if (NodeFlag = White) then
if (Xoffset < 0) then
Channel := X0－;
if (Yoffset < 0) then
Channel := Y0－;
if (Zoffset ≤ 0 and Zsrcoffset < 0) then
if (NodeFlag = White) then
if (Xoffset < 0) then
Channel := X1－;
if (Yoffset < 0) then
Channel := Y1－;
if (Zoffset < 0) then
Channel := Z－;
if (NodeFlag = Black) then
if (Xoffset > 0) then
Channel := X1+;
if (Yoffset > 0) then
Channel := Y1+;
if (Xoffset = 0 and Yoffset = 0 and Zoffet = 0) then
Channel := internal;
4. 仿真实验
为了简化计算，在仿真实验中我们作以下假设。我们将所有通道包括虚信道都视为物理
通道，而且所有的通道都具有相同的物理带宽，20 微片每微秒。微片大小等于信道容量，
通道的缓冲大小等于微片的大小。模拟中以足够小的时间间隔路由报文。处理器在等时间间
隔内产生的报文数量的服从负指数分布。每个报文分割的微片数量服从均匀分布。路由传输
模型的目的地址服从均匀分布。我们并假设路由器可以同时处理多个通道的数据，而且处理
器可立刻处理完传来的数据。我们使用两个度量来评价路由算法的性能，平均时延和标准化
可接受流量。时延以微秒为单位，标准化可接受流量数值等于相对于最大理论吞吐量的百分
数。
- 7 -
0
5
10
15
20
25
30
35
40
0 5 10 15 20
标准化可接受流量
平
均
时
延
Mesh West-first
Double XY
X-Y+ first
a) H6 蜂窝网格与 16×16 网格路由性能
0
5
10
15
20
25
30
35
40
0 5 10 15 20
标准化可接受流量
平
均
时
延
X-Y+ First 200 flits
Double XY 200 flits
X-Y+ First 100 flits
Double XY 100 flits
b) H4蜂窝网格路由性能
图5 蜂窝网络与二维网格路由性能比较
我们以 H4 蜂窝网格 96 个节点和 H6 蜂窝网格 216 个节点为例。除此之外，为了方便与
二维网格进行对比，我们另外以 16×16 网格 256 个节点作参考来对照 H6 的路由性能。图 5
中 a)图是 16×16 网格和 H6 的性能对比，每个报文的微片数从 10 到 200 个不等。b)是 H4 的
性能评估，报文的微片最大数目采用两种情况，一个是 200 个微片，另一个是 100 微片。通
过分析对比，我们可以发现 Double XY 算法是优于 X－Y+优先算法的，但由于 Double XY
算法采用了虚信道技术，增加了路由元件的复杂性。另外，蜂窝网格的性能在低吞吐量时的
时延与二维网格差别不大，但随着吞吐量的增加，蜂窝网格比普通网格更快进入饱和状态。
5. 结束语
本文介绍了六角形蜂窝网格基于转弯模型的单信道虫孔路由算法的设计和基于虚信道
技术的虫孔路由算法的设计，并证明了它们的无死锁特性。两个算法各有各自的优点和缺点，
X－Y+优先算法简单易行，而 double XY 使用虚信道技术实现了最短路径路由。最后通过对
这两个算法的性能模拟的结果进行比较和分析，发现 double XY 和 X－Y+优先算法都具有
较好的性能。另外，我们也发现蜂窝网格的吞吐量是相对较弱于普通网格。
参考文献
[1] I. Stojmenovic. Honeycomb networks: topological properties and communication algorithms[J]. IEEE trans
Parallel Distributed Systems, 1997, 8(10) : 1036-1042.
- 8 -
[2] XiaoFan Yang. The diameter of honeycomb rhombic tori[J]. Applied Mathematics Letters, 2004, 17: 167-172.
[3] Megson, . Yang Xiaofan, Liu Xiaoping. Honeycomb tori are Hamiltonian[J]. Information Processing
Letters, 1999, 72(3-4): 99-103.
[4] Xiaofan Yang, David J. Evans, Hongjian Lai, et al. Generalized honeycomb torus is hamiltonian[J].
Information Processing Letters, 2004, 92: 31-37.
[5] W. J. Dally, C. L. SeitZ. DeadLock-free message routing in multiprocessor interconnection networks[J]. IEEE
Transactions on Computers, 1987, 36: 547-553.
[6] C. J. Glass, L. M. Ni. The turn model for adaptive routing[C]. Proceedings of the 19th International Symposium
on Computer Architecture, 1992. 278-287.
[7] C. J. Glass, L. M. Ni. Maximally fully adaptive routing in 2D meshes[C]. Proceedings of the 1992 International
Conference on Parallel Processing, 1992. 101-104.
[8] W. J. Dally. Virtual-channel flow control[J], IEEE Transactions on Parallel and Distributed Systems, 1992, 3(2):
194-205.
[9] Jianping Song, et al. Optimal routing and multicasting in wormhole-routed honeycomb networks[C], High
Performance Computing in the Asia-Pacific Region, 2000. 142-144.
[10] J. Carle, . Myoupo, D. Seme. All-to-all broadcasting algorithms on honeycomb networks and
applications[J]. Parallel Processing Letters, 1999, 9(4): 539-550.
Wormhole-Routing Algorithms in Honeycomb Networks
Zhang Wei-wen, Yang Xiaofan
Department of Computer Science, Chongqing University, Chongqing, China
400044
Abstract:
Honeycomb network is a newly introduced interconnection network for parallel computing. This
network is like the 2D mesh, but some properties of honeycomb are better than those of 2D mesh.
However, the honeycomb network does not have any single channel minimal wormhole-routing
algorithms. Two wormhole-routing algorithms are designed for this network. One is a non-minimal
routing algorithm which used the turn model; the other is a minimal routing algorithm which used the
virtual channels technology. Both of them are adaptive and deadlock-free. The performances of these
algorithms are also analyzed by simulations.
Key words: interconnection network; virtual channel; turn model; deadlock-free routing; wormhole
作者简介：张伟文（1977-），男，广东东莞人，硕士研究生，主要研究方向为并行计算机
互连网络。
