虚网叠加构造自适应路由算法的有效框架

大规模并行处理机系统中路由算法对互联网络通信性能和系统性起着重要作用。

VIRTUAL-NETWORK OVERLAPPING: A FRAMEWORK FOR DEADLOCK-FREE ADAPTIVE ROUTING ALGORITHMS

In a massively parallel processors(MPP) system,a routing algorithm constitutes the primary factor influencing the performance of the interconnect network and MPP system. Many adaptive algorithms have been proposed, but there doesn't exist an efficient framework to design deadlock free adaptive wormhole routing algorithms to satisfy various conditions. Here presented is a virtual network overlapping framework(VNOF) for designing adaptive routing algorithm in direct networks using wormhole switching technology. Based on VNOF, several virtual channels are placed on a physical channel,and thus divides the physical network into several virtual networks. Different routing algorithms can be used in different virtual networks, and the overall network is deadlock free, provided the routing algorithm used in one virtual network is deadlock free. The routing algorithms in any other virtual networks can be fully adaptive for different purposes, such as supporting full adaptivity or fault tolerance or other to increase performance. Finally, the deadlock free, livelock free and adaptive property of the algorithms based on VNOF are proved. As examples of VNOF framework, two deadlock free fully adaptive wormhole routing algorithms based on VNOF, a multi request PBFAA algorithm and a single request SFAA algorithm are presented,giving guidelines to design new adaptive rouing algorithms based on VNOF.