超立方体中基于极大安全通路矩阵的容错路由

Fault-Tolerant Routing for Hypercube Multi-Computers Based on Maximum Safety-Path Matrices

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximumsafetypathmatrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路;与基于最优通路矩阵(optimalpathmatrices,简称OPMs)及扩展最优通路矩阵(extendedoptimalpathmatrices,简称EOPMs)的容错路由算法相比,MSPMs是OPMs以及EOPMs的最大扩展,解决了如何用矩阵的形式来记录最多最优通路的问题.

Hypercube multi-computers system is of good performance in parallel and distributed computation. With the increasing size of a multi-computers system, the fault possibility of computers and their links increases. It is very important to seek for better fault-tolerant routing strategies to realize an effective fault-tolerant routing. A novel fault-tolerant routing algorithm in hypercube multi-computers system is proposed, in which each node uses a maximum safety path matrices (MSPMs) to record the optimal paths to the other nodes. It proves that MSPMs can record most of the optimal paths by n-1 rounds of information exchanges between neighboring nodes. Furthermore, it proves that MSPMs is the final extension of the Optimal Path Matrices (OPMs) and the Extended Optimal Path Matrices (EOPMs) which also use the matrices to record the optimal paths in hypercube multi-computers system, so the problem of how to record the most of optimal paths in the n dimensional hypercube multi-computers system by using matrices is solved finally.