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

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

作　　者：刘燕[1] 孙利民[1] 杨晓东[1] 

机构地区：[1]国防科学技术大学计算机科学系

出　　处：《计算机研究与发展》1999年第4期500-504,共5页Journal of Computer Research and Development

基　　金：国家"八六三"高技术计划;"九五"国防预研基金

摘　　要：大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用．文中在虫孔路由的直接网络中提出了一种虚网叠加的自适应路由算法构造框架ＶＮＯＦ，框架中为每条物理通道上设置多条虚通道，将物理网络划分成一组独立的虚拟子网，在不同的虚拟子网中根据不同的应用目的可采用不同的路由算法，但保证有一子网中采用的路由算法是无死锁的，由此达到整个网络的无死锁性．基本框架还保证了算法的无活锁性和自适应性．文中最后给出了基于该框架设计的几个典型算法，为具体算法设计提供指导．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.

关 键 词：虚网叠加 自适应路由算法 互联网络 并行计算机 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP338.602[自动化与计算机技术—计算机科学与技术]