用最优通路矩阵实现超立方体多处理机系统的容错路由  

Fault-Tolerant Routing in Hypercube Multicomputers Using Optimal Path Matrices

作　　者：高峰[1] 李忠诚[1] 

机构地区：[1]中国科学院计算技术研究所CAD开放实验室,北京100080

出　　处：《计算机学报》2000年第3期242-247,共6页Chinese Journal of Computers

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

摘　　要：针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵 (OPM)的概念 ,并给出了一个基于最优通路矩阵的路由算法 .存储于超立方体各节点中的最优通路矩阵记录系统中的故障信息 ,用于判定消息的源节点和目的节点之间是否存在最优通路 (长度等于两节点间 Hamming距离的通路 ) .对于 n维超立方体 ,每个节点所需的存储开销为 n2 个字 .基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的 Hamm ing距离加 2 .This paper presents a new concept——Optimal Path Matrices for fault tolerant routing on hypercube multicomputers. Optimal Path Matrices (OPMs) stored on each node of a hypercube keep faulty information and indicate whether there is an optimal path from the node to a destination (the length of which is equal to the Hamming distance between the source and the destination). A simple fault tolerant routing algorithm based on Optimal Path Matrices is proposed to route messages from sources to destinations. It can easily establish a path for a message. And the length of the path is no greater than the Hamming distance between the source and the destination of the message plus two. The memory overhead is n 2 words on each node of an n dimensional hypercube.

关 键 词：容错路由 最优通路矩阵 超立方体 多处理机系统 

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