超立方体多处理机系统中基于扩展安全向量的容错路由  

A Fault-Tolerant Routing Strategy Based on Extended Safety Vectors in Hypercube Multicomputers

作　　者：高峰[1] 李忠诚[1] 闵应骅[1] 吴杰 

机构地区：[1]中国科学院计算技术研究所CAD开放实验室,北京100080 [2]美国佛罗里达大西洋大学计算机科学与工程系

出　　处：《计算机学报》2000年第3期248-254,共7页Chinese Journal of Computers

基　　金：国家自然科学基金!( 6973 3 0 10 ;6970 3 0 0 1)

摘　　要：针对超立方体结构的多处理机系统中存在链路故障的情况 ,修改了吴杰提出的安全向量的概念 ,提出了扩展安全向量的概念 ,并给出了一个基于扩展安全向量的容错路由算法 .与基于安全向量的路由算法相比 ,基于扩展安全向量的路由算法搜索最优通路的能力有了非常大的提高 ,即使故障数较多时 ,它仍能保证把绝大多数源、目的节点间有最优通路的消息沿最优通路传递 ,从而保证系统在有较多故障时仍能实现高效的信息传递 .超立方体结构中各节点扩展安全向量的赋值可以通过 n- 1轮邻接点间的信息交换完成 .This paper modifies the definition of safety vectors (SVs) [8] , which is proposed for hypercube multicomputers, and proposes a new concept extended safety vectors (ESVs). The values of extended safety vectors of nodes in a hypercube system can be determined in n-1 rounds information exchange between neighbors. Optimal unicasting between two nodes is guaranteed if the k th bit of extended safety vector of the source node is 1, where the k is equal to the Hamming distance between the two nodes. A fault tolerant routing algorithm is then proposed to make use of the information recorded in extended safety vectors. It can easily determine whether a path of length no greater than the Hamming distance between the source and destination plus 2 can be established. The simulation results show that it is much more powerful than those based on safety vectors in dealing with link faults.

关 键 词：安全向量 容错路由 超立方体 多处理机系统 

分 类 号：TP338.028[自动化与计算机技术—计算机系统结构]