BWR——带缓冲的虫孔路由技术

MPP互联网中通常使用虫孔路由WR（Wormhole Routing)交换技术来提高网络性能，采用该技术，每个结点所需的通信缓冲小；并且当消息长度远远大于微片长度时，消息的传输延迟时间与传输距离无关。但WR技术也具有容易阻塞和产生刹车问题的缺点。该文在WR技术的基础上，提出了带缓冲的虫孔路由BWR（Buffered Wormhole Routing)交换技术，并对采用BWR技术的k-ary n-mesh的消息平均传输延迟进行理论分析与模型模拟。结果均表明BWR技术可以较好地解决WR技术带来的问题，可以较好地提高网络的性能。

BWR

The processing nodes in the MPP system communicate with eachother through the interconnection network. The factors influencing the performance of the network mostly include network topology, switching mechanism and routing algorithm. Wormhole routing (WR) is widely used in modern MPP systems, in which a message is split into several units called flits and the flits of the same message are transferred in the network in a pipelined fashion. WR technique requires fewer buffers (size of 1 flit) and makes message latency insensitive to the distance that message traverses.When the first flit of the message is blocked, the network must “tell” the following flits to stop transferring; and when the first flit begin to transfer, the network also need to let the following flits know to continue transferring. This is called the brake problem. The WR switching also has some drawbacks. It is difficult to solve brake problem of WR and the congestion problem that will take place easily under heavy traffic.Based on the WR technology, this paper proposes buffered wormhole routing (BWR) switching technique. More buffers are added to the router in the network. Whether the flits can be transferred into the buffers of the next node in the path depends on the fullness of those buffers. Thus the brake problem is solved because the router only needs to know the situation of the buffers of the next router. The network can hold more messages, and the block possibility is lowered down at the same time. The mean message latency of k-ary n-mesh under BWR is focused on as the main performance metric. We proposed a method called backward algorithm to analyze the mean message latency of k-ary n-mesh under BWR and deterministic routing. In order to verify our result, a simulator for k-ary n-cube is built. The analysis and simulation results both show that BWR can solve the problems caused by WR, and can improve the network performance.