互连网络的通信与wormhole寻径

摘 要：并行处理机MPP由于其良好的可扩展性和联高性能比,已成为实现超高性能计算的重要支持工具.MPP系统性能的发挥极大程度上依赖于互连网络的通信性能,对于并行计算来说,寻径技术是至关重要的.互连网络中采用的寻径算法决定了消息在网络中如何选取路径,其性能对网络效率的发挥起着重要作用.该文以多机系统中的各种消息寻径方式概述为背景,着重讨论wormhole消息寻径方式.

关 键 词：直连网络；wormhole寻径；死锁的避免和恢复；虚拟通道

中图分类号：TP393文献标识码：A文章编号：1009-3044(2012)03-0558-02

对于大规模问题求解时,要求很高的计算求解的速度,电子技术的发展曾使计算机的运算速度获得惊人的提高,但现在已接近电子传输的物理极限,传统的大型机和向量巨型机由于自身物理因素和工艺水平的限制,在性能上很难进一步达到要求.因此,传统计算机的串行结构是阻碍速度提高的关键因素,并行处理技术就成了进一步提高性能的主要途径.

并行处理技术是并行计算机的关健技术,它涉及的范围很广,包括并行结构、并行算法、并行操作系统、并行语言及其编译系统等,其中并行结构是关键因素.

计算机根据指令流和数据流是单一的还是多个的进行分类,并行处理机可以分为SIMD（单指令流多数据流）和MIMD（多指令流多数据流）两大类.SIMD比较专用,世界上装用的数量并不多,MIMD则应用广泛,发展出多种类型.MIMD可进一步划分为以下五种类型：并行向量处理机（PVP）、对称多处理机（P）、大规模并行处理机（MPP）、分布共享存储器（D）多处理机、机群系统（COW）.

本文讨论当今较为常用的MPP计算机组成的关键部分――互连网络的结构,并对wormhole寻径技术展开分析和讨论.

1基本术语与性能指标

1.1消息、包和片

消息（Message）是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包.它是一种逻辑单位,可由任意数量的包构成.包（Packet）的长度随协议不同而不同,它是信息传送的最小单位,64-512位.片（Flit）的长度固定,一般为8位.1.2互连网络技术指标

互连网络用来在多计算机系统的处理结点之间传递消息.互连网络性能的两个重要指标是传输时延（TranissionLatency）和吞吐量（Throughput）.吞吐量指系统在每秒内发送或接收到的消息的字节数,它取决于节点的体系结构和通信机制.传输时延主要有三个部分组成：

一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间.一个网络的传输时延：在一定条件下发送消息的平均时延.

网络的吞吐量：单位时间内网络所能传输的消息数目或长度.

图1wormhole寻径

2Wormhole寻径（WormholeRouting）

首先把一个消息分成许多片,消息的头片包含了这个消息的所有寻径信息,尾片是一个其最后包含了消息结束符的片,中间的片均为数据片.片是最小信息单位.每个结点上只需要缓冲一个片就能满足要求.

Wormhole寻径方式如图1所示.

当消息的头片到达一个结点A的寻径器后,寻径器根据头片的寻径信息立即做出寻径选择：如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用,那么这个头片就不必等待,直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步.当消息的尾片向前“蠕动”一步后,它刚才所占用的结点就被放弃了.如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用,那么这个头片就必须在此结点的通信缓冲器中等待,直到上述两者都可用为止；其它片也在原来的结点上等待.此时,被阻塞的消息不从网络中移去,片不放弃它所占有的结点和通道.这是Wormhole技术和其它流控制技术都不同的地方.

Wormhole方式从管道消息流的概念中所继承的.它的优点是每个结点的缓冲器的需求量小,易于用VLSI实现；较低的网络传输延迟；所有的片以流水方式向前传送.而在存储转发中,消息是整个的从一个结点“跳”向另一个结点,通道的使用是串行的.Wormhole与线路开关的网络传输延迟正比于消息包的长度,传输距离对它的影响很小（消息包较长时的情况）.通道共享性好、利用率高.对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道.易于实现Multicast和Broadcast.允许寻径器复制消息包的片并把它们从多个输出通道输出.

由于wormhole技术淡化了路径长度对网络性能的负面影响,使人们有希望采用简单、规整的低维网格结构来实现高性能的大规模并行处理（MPP）互连网络.所以,wormhole技术已被广泛用于MPP互连网络中,并收到了较好的效果.

3虚拟通道与死锁

对于wormhole寻径方式最重要的问题在于防止消息传递的阻塞和死锁.一个消息有可能在一个向相反方向传递的消息后阻塞,如图2所示.

图2Wormhole寻径的阻塞

图中,源2与目的2两各节点之间首先开始传输片,这样就阻塞了源1到目的1的片的传送.在这种情况下,通常使用虚拟通道来解决阻塞的问题.一个虚拟通道是一个物理通道的逻辑抽象概念,与一个物理通道关联的所有虚拟通道具有不同的片缓存,并且它们时分复用该物理通道.与此类似,每个与虚拟通道相关联的缓存实际上是该物理通道的缓存的一部分,如图3所示.

图3虚通道示意图

在图3所示的虚通道示意图中,两个虚通道共用一个物理通道,实现了物理通道的时分复用,从而解决了阻塞的问题.在虚拟通道中,一条物理通道在逻辑上分成两个传输方向相反的通道,每一个虚拟通道为单向且有自己的缓存区；一条物理通道上的虚拟通道逻辑上被划分成多个虚拟通道,这些虚拟通道共享这条物理通道发送或接收信息.由于虚拟通道能够有效的减小冲突和阻塞,因此为增强性能和设计非死锁的寻径算法方面,在多计算机系统尤其是MPP中使用的非常频繁.

综上所述,wormhole技术的通道具有共享性好,灵活的连接方式,较高的吞吐率等优点.在wormhole技术中,对通道的预约和释放是结合在一起的一个完整过程.当占有一段新的通道后,将立即释放用过的一段旧通道,充分考虑多个数据包对通道资源的共享.数据包经过的每一段通道既不在数据包到达之前预约,也不在数据之后继续占有,仅仅在数据包到达时才被使用.对于某一段通道来讲,在数据包到达之前它不必空闲等待,当数据包经过之后它立即可以为其它数据包所利用.

4避免死锁的wormhole寻径方式

4.1维序寻径

维数排序路由是一种确定的wormhole寻径方式,它规定了消息传递时所选择的路径的维数即方向的顺序.这种网络的维数按照时限定好的单调的顺序排序.消息首先在最高维或最低维进行置换,直到它在这一维的方向上到目的节点的距离为0,然后消息再在一个相邻的维上进行交换,重复这个过程,直到该消息抵达目的节点.所有的消息不会反向传送,不会形成循环,因此就保证了死锁的避免.

维数排序路由将最短路径分布在整个网络中,这样同时均衡分布了网络的通信量.对于不对称工作量的网络来说,有些通道就会比其他通道繁忙得多,而由于这种算法将路径限制在一个固定的通道上,即使在冲突或网络发生错误的情况下也不能够分散流量.对于所有的确定的wormhole寻径方式中,都存在这个问题.因此,这是确定的wormhole寻径方式的局限性.

（下转第591页）

4.2转向模型（TurnModel）

转向模型开创了避免死锁的自适应算法新方向.它要求通道独立图中没有自环.转向模型针对无附加通道的网络提供了一套发展自适应寻径算法的系统方法,无论是完全自适应还是部分自适应.在这样的情况下死锁的发生是因为包的寻径转向形成了自环.

[4]PrasantMohapatra.WormholeRoutingTechniqueorDirectlyConnectedMultiputerSystems[J].ACMComputingSurveys,1998,30(3):374.

[5]郑纬民.高等计算机系统结构[M].北京:清华大学出版社,2001.