超立方体系统中基于安全通路向量的容错路由  

Fault-Tolerant Routing Based on Safety Path Vectors in Hypercube System

作　　者：王雷[1] 林亚平[1] 陈治平[1] 文学[1] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082

出　　处：《软件学报》2004年第5期783-790,共8页Journal of Software

基　　金：湖南省自然科学基金01JJY1007~~

摘　　要：n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外,与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销,且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.Hypercube multicomputer system has good performance in parallel and distributed computation. With the increasing size of a multicomputer network system, the fault possibility of computers and their links increases. As a result, it becomes very important to seek for better fault-tolerant routing strategies for realizing more effective fault-tolerant routing when lots of faults occur in the multicomputer system. An innovative fault-tolerant routing algorithm is proposed, in which each node uses a safety path vector (SPV) to record the optimal paths to the other nodes. The safety path vector is an approximate measure of the number and distribution of the faults in the neighborhood and can be setup or updated through the n-1 rounds of information exchanges among neighboring nodes by consuming only n bits storage space. Compared with previous fault-tolerant routing algorithms such as the safety vectors (SVs), extended safety vectors (ESVs), optimal path matrices (OPMs) and extended optimal path matrices (EOPMs), SPVs have stronger ability in tracing optimal paths with equal or less storage cost. Analysis and simulation are given to show the merit of the SPVs.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]