About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SPDP 1992
Conference paper
Tolerating faults in a mesh with a row of spare nodes
Abstract
We present an efficient method for tolerating faults in a twodimensional mesh architecture. Our approach is based on adding spare components (nodes) and extra links (edges) such that the resulting architecture can be reconfigured as a mesh in the presence of faults. We optimize the cost of the faulttolerant mesh architecture by adding about one row of redundant nodes in addition to a set of к spare nodes (while tolerating up to к node faults) and minimizing the number of links per node. Our results are surprisingly efficient and seem to be practical for small values of k. The degree of the faulttolerant architecture is к + 5 for odd k, and к + 6 for even k. Our results can be generalized to ddimensional meshes such that the number of spare nodes is less than the length of the shortest axis plus k, and the degree of the faulttolerant mesh is (dl)fc + d + 3 when к is odd and (dl)k + 2d + 2 when к is even.