Patent
1995-08-31
1996-04-30
Beausoliel, Jr., Robert W.
G06F 1100
Patent
active
055133134
ABSTRACT:
A method is disclosed, for use with a multiprocessing hardware mesh architecture including nodes and a network of interconnections between the nodes, for defining and implementing a target logical mesh architecture utilizing a given subset of the nodes and the interconnections of the hardware architecture. Typically, the hardware mesh architecture includes redundant nodes and interconnections, sot hat the target logical mesh architecture may be defined from the hardware architecture several different ways. As a consequence, the target logical mesh architecture may be defined even in the presence of faulty nodes or interconnections in the hardware architecture. Frequently, the logical mesh is defined in terms of some regular pattern of interconnections. The method of the invention facilitates the definition of the desired logical mesh architecture from the hardware architecture, given the possibility that one or more faults are present, by initially defining logical blocks of nodes from among the functional nodes of the hardware architecture. Then, functional edges between the nodes defined within the logical blocks are defined as logical interconnections between the nodes of the logical blocks, such that the logical blocks, with the interconnections, are structurally consistent with portions of the logical mesh. Finally, additional edges are defined as logical interconnections between nodes in different logical blocks, these additional edges also being consistent with the structure of the logical mesh. The result is that the logical mesh has been fully defined from functional nodes and interconnections in the hardware architecture.
REFERENCES:
patent: 4047163 (1977-09-01), Choate et al.
patent: 4051354 (1977-09-01), Choate
patent: 4302819 (1981-11-01), Ware
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: 4891810 (1990-01-01), de Corlieu et al.
patent: 4907232 (1990-03-01), Harper et al.
patent: 4918662 (1990-04-01), Kondo
patent: 4922408 (1990-05-01), Davis et al.
patent: 4942517 (1990-07-01), Cok
patent: 4951220 (1990-08-01), Ramacher et al.
patent: 4970724 (1990-11-01), Yung
patent: 5065308 (1991-11-01), Evans
patent: 5072371 (1991-12-01), Benner et al.
patent: 5170482 (1992-12-01), Shu et al.
patent: 5201044 (1993-04-01), Frey, Jr. et al.
patent: 5251131 (1993-10-01), Masand et al.
Tien et al., Reconfiguring Embedded Task Graphs in Faulty Hypercubes by Automorphisms, System Sciences 1990 Annual Conference, pp. 91-100.
Dutt et al., Designing Fault-Tolerant Systems Using Automorphisms, Journal of Parallel and Distributed Computing, Jul. 1991, pp. 249-268.
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. pp. 285-296, Oct. 1990.
Kung et al., "Fault-Tolerant Array Processors Using Single-Track Switches", IEEE Trans. Computers, vol. C-38, No. 4, pp. 501-514, Apr. 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., "Mininum 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., "Efficient Fault-Tolerant Meshes and Hypercubes Architectures", IBM Research Report RJ 8566, Jan. 1992.
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.
J. Bruck et al., Tolerating Faults in a Mesh with a Row of Spare Nodes, RJ 8762 (78576) May 5, 1992.
Bruck Jehoshua
Cypher Robert E.
Ho Ching-Tien
Beausoliel, Jr. Robert W.
Blair Philip E.
International Business Machines - Corporation
Pintner James C.
Snyder Glenn
LandOfFree
Method for generating hierarchical fault-tolerant mesh architect 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 for generating hierarchical fault-tolerant mesh architect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating hierarchical fault-tolerant mesh architect will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-636175