文档介绍：
蜂窝网格的虫孔路由算法1
张伟文，杨小帆
重庆大学 计算机学院, 重庆市 （400044）
E-mail: ******@
摘 要:六角形蜂窝网格是一种新近提出的并行多处理机互连网络。蜂窝网格在某些特性上优
于二维网格。不过，这种网络不存在单信道最短路径无死锁路由算法。文中针对该网络设计
了两个部分自适应无死锁虫孔路由算法。一个是基于转弯模型单信道非最短路径路由算法，
另一个则是采用了虚拟双信道的最短路径路由算法。对第二个算法，还进一步使用转弯模型
对其改进。通过仿真实验，结果显示这两个路由算法都具有较好的性能。
关键词: 互连网络; 虚信道; 转弯模型; 无死锁路由; 虫孔
中图法分类号: TP338；TP393
1. 引言
并行多处理器互连网络（简称互连网络），是指处理器已一定方式相互连接而构成的网
络。在互连网络中，为了实现某些功能，处理器之间经常需要交换信息，例如，处理器之间
的任务分配、负载平衡和同步等。大部分这些直接网络是通过交互消息或者报文来实现节点
之间的通信。路由算法则是建立消息或报文在网络中将要执行的传递路径。所以，路由算法
性能的效率会直接影响到并行机的性能。对规则网络来说，利用好网络的拓扑性质才能实现
高效的路由算法。另外，互连网络中路由算法的设计往往也跟采用交换方式相关。在早期的
并行计算机中采用的交换技术主要是电路交换和报文交换技术。这些技术的时延较大，已经
很少应用在并行计算机中了。虫孔交换技术由于时延短，已被广泛应用于当今的并行计算机
中。例如，Cray T3E，Intel Paragon 和曙光系列并行机等。虫孔路由有一个很大的优点是对
数据传输距离不敏感。不过，它相对一般交换技术更加容易引起死锁。解决死锁问题是虫孔
路由设计的难点。
根据图论的知识，已经有许多网络拓扑结构被提出来。一些经典结构（超立方体、网格
等）已被广泛的研究和应用。而一些新的网络结构，研究还比较欠缺。最近，Stojmenovic
提出一种新的网络[1]，六角形蜂窝网格。该网络是一种平面拓扑的互连网络，它类似于二
维网格，不过节点连接度只有 3，比网格少 1，而同时具有类似网格的拓扑性质( 对称性、
低连接度、可递归构造性等 )， 有些特性还优于网格[1，2，3，4]。针对该网络的路由设计
的研究还比较欠缺。文献[1]中提出了一个简单的单播路由算法，不过该算法是死锁的。广
播算法的研究主要有 J. Carle 提出的一种 all-to-all 全广播算法[10]和 Song 针对单口传播方式
提出的一个点广播算法[9]。本文的研究主要是设计了六角形蜂窝网格的两个单播路由算法，
一个是基于转