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

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safetypathvectors,简称spvs)概念,并给出了建立spvs及其容错路由算法.其中spvs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为nbits,因此,spvs是安全向量(svs)与扩展安全向量(esvs)的一种扩展,具有比svs和esvs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimalpathmatrices,简称opms)及扩展最优通路矩阵(extendedoptimalpathmatrices,简称eopms)的容错路由算法相比,spvs呈指数级地降低了算法的存储开销，且能够记录opms和eopms所不能记录到的最优通路信息.理论分析和仿真实验验证了spvs的上述性能.