Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Publishing Venue
IBM
Related People
Bruck, J: AUTHOR [+3]
Abstract
Disclosed is an efficient method for tolerating link faults in a d-dimensional mesh, based on the technique of the so-called wildcard dimensions and error correcting codes theory.
Wildcard Dimensions, Coding Theory and Fault Tolerant Meshes and Hypercubes
Disclosed is
an efficient method for tolerating link faults in
a d-dimensional mesh, based on the technique of the so-called
wildcard dimensions and error correcting codes theory.
It is known
that a hypercube can be extended by one wildcard
dimension resulting in a folded hypercube, which has better fault
tolerance and communication capabilities.
Also, a d-dimensional
torus having n nodes can be extended by up to n-d+1 wildcard
dimensions. Using techniques from error
correcting codes,
specifically a Maximum Distance Separable (MDS) code such as the
extended Reed-Solomon codes and an extension of the Vandermonde
matrix, we construct a d-dimensional fault-tolerant mesh which has
degree 2s and can tolerate 2s - 2d+1 edge faults, for any d < s
< n+1, regardless of the faults distribution. The faults are
tolerated in the sense that the remaining (fault-free) network still
guaranteed to contain a d-dimensional mesh of the same size as a
subgraph. Thus, programs designed for
the original mesh can be run
on the fault-tolerant mesh without slowdown, even after up to 2s -
2d+1 link failures.
Disclosed anonymously.