Fault-Tolerant Routing in Hypercube Multicomputers Using Optimal Path Matrices
Feng Gao · Chinese Journal of Computers · 2000
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.