Bruck, Jehoshua and Cypher, Robert and Ho, Ching-Tien (1992) Tolerating faults in a mesh with a row of spare nodes. In: IEEE Symposium on Parallel and Distributed Processing, 4th, Arlington, TX, 1-4 December 1992. IEEE , Piscataway, NJ, pp. 12-19. ISBN 0-8186-3200-3. https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp92a
![]()
|
PDF
- Published Version
See Usage Policy. 572kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp92a
Abstract
We present an efficient method for tolerating faults in a two-dimensional 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 fault-tolerant mesh architecture by adding about one row of redundant nodes in addition to a set of k spare nodes (while tolerating up to k 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 fault-tolerant architecture is k + 5 for odd k, and k + 6 for even k. Our results can be generalized to d-dimensional meshes such that the number of spare nodes is less than the length of the shortest axis plus k, and the degree of the fault-tolerant mesh is (d-1)k+d+3 when k is odd and (d-1)k+2d+2 when k is even.
Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
Additional Information: | © Copyright 1992 IEEE. Reprinted with permission. Meeting Date: 12/01/1992 - 12/04/1992. | |||||||||
Subject Keywords: | fault tolerant computing; parallel architectures; fault tolerance; fault-tolerant architecture; fault-tolerant mesh; spare components; two-dimensional mesh architecture | |||||||||
DOI: | 10.1109/SPDP.1992.242768 | |||||||||
Record Number: | CaltechAUTHORS:BRUispdp92a | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:BRUispdp92a | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 12403 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | INVALID USER | |||||||||
Deposited On: | 24 Nov 2008 23:04 | |||||||||
Last Modified: | 08 Nov 2021 22:28 |
Repository Staff Only: item control page