摘要
针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵 (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.
出处
《计算机学报》
EI
CSCD
北大核心
2000年第3期242-247,共6页
Chinese Journal of Computers
基金
国家自然科学基金!( 6973 3 0 10
6970 3 0 0 1)
关键词
容错路由
最优通路矩阵
超立方体
多处理机系统
fault-tolerant routing, optimal path matrices, hypercube, multicomputers
