Method and apparatus for a fault-tolerant mesh with spare nodes

Details Method and apparatus for a fault-tolerant mesh with spare nodes Method and apparatus for a fault-tolerant mesh with spare nodes

1992-05-04

1993-12-14

Canney, Vincent P.

Excavating

371 113, 364230, 395575, G06F 1500

Patent

active

052710149

ABSTRACT:
A method and apparatus are presented for tolerating up to k faults in a d-dimensional mesh architecture based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where m spare nodes (m.gtoreq.k) are added and the maximum number of links per node (degree of the mesh) is kept small. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults, regardless of their distribution. According to one aspect of the invention, given a d-dimensional mesh architecture having N=n.sub.1 .times.n.sub.2 .times.. . . .times.n.sub.d nodes, the fault-tolerant mesh can be represented by a diagonal or circulant graph having N+m-k nodes, where m.gtoreq.k. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a pre-determined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to the 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 teaching set forth herein.

REFERENCES:
patent: 4047163 (1977-09-01), Choate et al.
patent: 4051354 (1977-09-01), Choate
patent: 4302819 (1981-11-01), Ware et al.
patent: 4605928 (1986-08-01), Georgiou
patent: 4698807 (1987-10-01), Marwood et al.
patent: 4722084 (1988-01-01), Morton
patent: 4791603 (1988-12-01), Henry
patent: 4868818 (1989-09-01), Madan et al.
patent: 4875207 (1989-10-01), Van Twist et al.
patent: 4891810 (1990-01-01), de Corlieu et al.
patent: 4907232 (1980-03-01), Harper et al.
patent: 4942517 (1990-07-01), Cok
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: 5065308 (1991-11-01), Evans
patent: 5201044 (1993-04-01), Frey, Jr. et al.
Li, "Diagonal Replacement Scheme to Recover Fault in a Mesh", Research Disclosure No. 309, Kenneth Mason Publications, Ltd. England, Jan. 1990.
Kaklamanis et al., "Asymptotically Tight Bounds for Computing with Faulty Array Processors", 31st IEEE Symp., Foundations of Computer Science.
Kung et al., "Fault-Tolerant Array Processors Using Single-Track Switches", IEEE Trans. Computers, vol. C-38, No. 4, pp. 501-514, Apri. 1989.
Hayes, "A Graph Model for Fault-Tolerant Computing Systems", IEEE Trans. Computers, vol. C-25, No. 9, pp. 875-884, Sep. 1976.
Wong, et al., "Minimum k-Hamiltonian Graphs", Journal of Graph Theory vol. 8, pp. 155-165, 1984.
Paoli et al., "Minimum k-Hamiltonian Graphs II," Journal of Graph Theory vol. 8, pp. 155-165, 1984.
Dutt et al., "On Designing and Reconfiguring k-Fault-Tolerant Tree Architectures", IEEE Trans. Computers, vol. C-39, No. 4, pp. 490-503, Apr. 1990.
Dutt et al., "An Automorphic Approach to the Design of Fault-Tolerant Microprocessors," Proceedings, 19th International Symposium on Fault-Tolerant Computing, pp. 496-503, Jun. 1989.
Bruck et al., U.S. Patent Application Ser. No. 07/723,287, "Method and Apparatus for Tolerating Faults in Mesh Architectures," Jun. 1991.
Bruck et al., "Efficient Fault-Tolerant Meshes and Hypercubes Architectures", IBM Research Report RJ 8566, Jan. 1991.
Bruck et al., "Fault-Tolerant Parallel Architectures with Minimum Numbers of Spares," IBM Research Report RJ 8029, Mar. 1991.
Bruck et al., "Fault-Tolerant Meshes and Hypercubes with Minimum Numbers of Spares," IBM Research Report RJ 8211, Jul. 1991.
Batcher, "Design of a Massively Parallel Processor", IEEE Trans. Computers vol. 9, pp. 836-840, Sep. 1980.
Elspas et al., "Graphs with Circulant Adjacency Matrices, Journal of combinatorial Theory", vol. 9, pp. 297-307, 1970.
Kuo et al., "Efficient Spare Allocation for Reconfigurable Arrays," IEEE Design and Test, pp. 24-31, Feb. 1987.
Leighton et al., "Wafer Scale Integration of Systolic Arrays," IEEE Trans. Computers, vol. 34, No. 5, (pp. 297-311), May 1985.
Roychowdhury et al., "Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays," IEEE Trans., Computers, vol. C-39, No. 4 pp. 480-489, Apr. 1990.
Rosenberg, "The Diogenes Approach to Testable Fault-Tolerant Arrays of Processors", IEEE Trans. Computers, vol. C-32, No. 10, pp. 802-910, Oct. 1983.
Sami et al., "Reconfigurable Architecture for VLSI Processing Arrays", Proceedings IEEE, vol. 74, No. 5, pp. 712-722, May 1986.
Ueoka et al., "A Defect-Tolerant Design for Full-Wafer Memory LSI", IEEE Journal of Solid-State Circuit, vol. SC-19, No. 3, pp. 319-324, Jun. 1984.
Skerret, "The Terflops", Popular Science, Mar. 1992, pp. 50-55, 88, 89.
Banerjee et al., Algorithm-Based Fault Tolerance on a Hypercube Multi-processor, vol. 39, No. 9, Sep. 1990, IEEE Transactions in Computers, pp. 1132-1145.

Affiliated with

Also associated with

Rating

Method and apparatus for a fault-tolerant mesh with spare nodes 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 a fault-tolerant mesh with spare nodes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a fault-tolerant mesh with spare nodes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1712161