计算机系统结构 蠕虫网技术动态.docx

基于omega网探讨蠕虫网的技术动态
---基于无阻塞omega网络的蠕虫网寻径方式
摘要
Omega网络由于自身结构的特点，无法实现任意置换的同时连通，在某些结点同时互联时会出现阻塞。对于该问题，一般的解决方法是将置换分批多次通过或增加器件，但这些方法都是以通信带宽的减小或硬件成本的增加为代价的，无法体现Omega网络自身的优越性。同时并行处理机由于其良好的可扩展性和联高性能价格比，已成为实现超高性能计算的重要支持工具。并行处理机系统性能的发挥极大程度上依赖于互连网络的通信性能，对于并行计算来说，寻径技术是至关重要的。互连网络中采用的寻径算法决定了消息在网络中如何选取路径，其性能对网络效率的发挥起着重要作用。
本文首先分析了现有几种主要的Omega组合网络以及对应的寻径算法，然后提出了Omega网络的无阻塞方案：通过对简单Omega网络进行改进，只增加了少量的部件和连线。该文还以多机系统中的各种消息寻径方式概述为背景，着重讨论wormhole消息寻径方式。
关键词：omega网阻塞机间通信蠕虫寻径方法及其优势

1无阻塞Omega网络
Omega网络是多级互联网络的一种。通常的多级网络是动态连接网络，即不采用固定连接，而是沿着连接通路使用开关与仲裁器来提供动态连接特性。简单Omega网络的构成单元是2×2开关。一个n输入的Omega网络通常需要log2n级，每级n/2个，共n*log2n/2个2×2开关。网络左右两侧各有n个结点，分别用二进制编号为xn-1xn-2⋯x0。其互联模式为两组对象的均匀洗牌连接（xn-1xn-2⋯x0→xn-2xn-3⋯x0xn-1）。
1.1Omega网络的阻塞特性
对于一个具体的置换连接，简单Omega网络由固定的算法来计算各开关如何设置。对于两个置换（xn-1xn-2⋯x0→yn-1yn-2⋯y0）和（pn-1pn-2⋯p0→qn-1qn-2⋯q0），若在开关设置的第i步出现xn-1-ixn-2-i⋯x0yn-1yn-2⋯yn+1-i＝pn-1-ipn-2-i⋯p0qn-1qn-2⋯qn+1-i，而yn-i≠qn-i，即同一开关上两个输入请求的是同一个输出，则这两个输出被阻塞。n输入的Omega网络一次通过可以实现nn/2个置换，但总共有n!个置换，无法保证每次置换都被完全通过。
1.2以器件为代价的无阻塞寻径算法
对于阻塞问题，一种解决方法是把所有的置换分为若干批，依次通过。一般来说，规模为n=2*k的Omega网络实现非阻塞连接最多需要通过的次数为k次，但是这样有效通信频带宽将降低为原来的1/k。另一种方法是采用多一倍的器件，配合较复杂的寻径算法，可以一次通过任意的n对n的置换，如Benes网络，所对应的算法称为循环算法，它的计算复杂度为O(N*logN)。Wu和Feng在1981年提出了混洗——交换类网络的通用结构和对应算法[3]，并给出一种用两个头对头的Omega网络互联起来组成的组合网络（称为Omega-1×Omega网络)，指出了它于Benes网络的拓扑等价性。但是这种结构的寻径算法是以Benes网络的循环算法为基础的，比循环算法还多出一些计算。在此基础上，Feng于1994年提出了类似的一种结构[1]，用两个Omega网络头对尾顺序连接起来(即Omega×Omega网络)，并给出了完全不同于循环算法的一种寻径算法，实现了复杂度为O(N)的计算量级。结点数为n的Omega×Omega网络中，对该网络两边的输入、输出结点依次编号为：0,1,2,⋯,n-1，对各级开关的级别编号为：1,2,⋯⋯,2k(这里n=2k)。通过对前k级开关的位置进行逆位序置换，Feng证明了该结构与Omega-1×Omega网络的拓扑等价性，并指出由此构成的Omega-1×Omega网络之间的连接是蝶式或变形蝶式的。
对于Omega-1×Omega网络，Feng提出了一种新的寻径算法[1]，对于每对置换，从网络中间的第k级开关和第k+1级开关开始，找出各自在这两级开关中所对应的位置，分别向两边按照简单Omega的寻径方法得出一条完整的路径。相对于计算复杂度为O(N*logN)的Benes类网络的循环算法，Feng算法具有明显的优越性，其总体计算时间为2N+logN-1，计算开销大大减少。不可避免的是，该算法仍然是以两倍的器件量为代价来取得网络的一次性置换连通。

2.Wormhole寻径（WormholeRouting）
蠕虫网络机间采用小容量缓冲存储器，实现消息分组寻径存储转发之用。在蠕虫网络中，将消息分组又分割成一系列更小的小组，同一分组中所有小组以异步流水方式按序不间断地传送，同一分组中的所有小组，只有头部的小组知道其所在整个分组传送的目的地，用硬件方式进行传送的应答。各个分组允许交叉传送，但不同