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

摘要：

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的上述性能.

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

所属期刊栏目：15

分类号：TP393(计算技术、计算机技术)

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

在线出版日期：2004-06-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：783-790