Method and apparatus for tolerating faults in mesh architectures

Details Method and apparatus for tolerating faults in mesh architectures Method and apparatus for tolerating faults in mesh architectures

1991-06-28

1994-01-18

Beausoliel, Jr., Robert W.

Excavating

371 111, G06F 1100

Patent

active

052806073

ABSTRACT:
A method and apparatus are presented for tolerating up to k faults in d-dimensional mesh architectures based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where exactly k spare nodes are added and the number of links per node (degree of the mesh) is kept to a minimum. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults. According to one aspect of the invention, given a d-dimensional mesh architecture M having N=n.sub.1 .times.n.sub.2 x . . . x n.sub.d nodes, the fault tolerant mesh can be represented by a circulant graph having exactly N+k nodes. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a predetermined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to target mesh M so long as d.gtoreq.2 and n.sub.d .gtoreq.3. The invention also relates to a method and apparatus for efficiently locating a healthy "target mesh" in the presence of up to k faulty network components, given a fault tolerant mesh constructed in accordance with the teachings set forth herein.

REFERENCES:
patent: 4047163 (1977-09-01), Choate et al.
patent: 4051354 (1977-09-01), Choate
patent: 4295218 (1981-10-01), Tanner
patent: 4302819 (1981-11-01), Ware
patent: 4466064 (1984-08-01), Martin
patent: 4507726 (1985-03-01), Grinberg et al.
patent: 4605928 (1986-08-01), Georgiou
patent: 4698807 (1987-10-01), Marwood et al.
patent: 4722084 (1988-01-01), Morton
patent: 4783782 (1988-11-01), Morton
patent: 4791603 (1988-12-01), Henry
patent: 4833635 (1989-05-01), McCanny et al.
patent: 4868818 (1989-09-01), Madan et al.
patent: 4875207 (1989-10-01), Van Twist et al.
patent: 4891810 (1990-01-01), Corlieu
patent: 4907232 (1990-03-01), Harper et al.
patent: 4918662 (1990-04-01), Kondo
patent: 4922408 (1990-05-01), Davis et al.
patent: 4951220 (1990-08-01), Ramacher et al.
patent: 4970724 (1990-11-01), Yung
patent: 5020059 (1991-05-01), Gorin et al.
patent: 5038386 (1991-08-01), Li
patent: 5088091 (1992-02-01), Schroeder et al.
patent: 5103220 (1992-04-01), Brunle
patent: 5133073 (1992-07-01), Jackson et al.
patent: 5134690 (1992-07-01), Samatham
patent: 5173689 (1992-12-01), Kusano
Banerjee et al, "Algorithm-Based Fault Tolerance on a Hypercube Multiprocessor", vol. 39 No. 9 Sep. 1990, IEEE Transactions on Computers, pp. 1132-1145.
Kenneth Mason Publications Ltd. "Diagonal Replacement Scheme To Recover Fault In a Mesh" Research Disclosure No. 309, Jan. 1990.
Dutt et al, "On Designing and Reconfiguring K-Fault-Tokrant Tree Architectures", IEEE Trans. on Computers, vol. 39, No. 4 1990 pp. 490-503.
Dutt et al, "Design and Reconfiguration Strategies for New-Optimal K-Fault Tokrant-Tree Architectures", IEEE 1988 pp. 328-333.
M. Sami and R. Stefanelli, Reconfigurable Architectures for VLSI Processing Arrays, Proceedings of the IEEE, vol. 74, No. 5, May 1986, pp. 712-721.
S-Y Kuo and W. K. Fuchs, Efficient Spare Allocation for Reconfigurable Arrays, IEEE Design and Test, 1987, pp. 24-31.
Y. Ueoka, C. Minagawa, M. Oka and A. Ishimoto, A Defect-Tolerant Design for Full-Wafer Memory LSI, IEEE Journal of Solid-State Circuits, vol. SC-19, No. 3, Jun. 1984, pp. 319-324.
K. E. Batcher, Design of a Massively Parallel Processor, IEEE Transactions on Computers, vol. C-29, No. 9, Sep. 1980, pp. 836-840.
V. P. Roychowdhury, J. Bruck, T. Kailath, Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays, IEEE Transactions on Computers, vol. 39, No. 4, Apr. 1990, pp. 480-489.
A. L. Rosenberg, The Diogenes Approach to Testable Fault-Tolerant Arrays of Processor, IEEE Transactions on Computers, vol. C-32, No. 10, Oct. 1983, pp. 902-910.
F. T. Leighton and C. E. Leiserson, Wafer-Scale Integration of Systolic Arrays, IEEE Computer Society's Tech. Committee on Math. Foundation of Computing, Issn No. 0272-5428, Nov. 3-5, 1982, pp. 297-311.

Affiliated with

Also associated with

Rating

Method and apparatus for tolerating faults in mesh architectures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for tolerating faults in mesh architectures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for tolerating faults in mesh architectures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1142656