Title :
Fault-tolerant hierarchical interconnection networks constructed by additional bypass linking with graph-node coloring
Author_Institution :
Adv. Res. Inst. for Sci. & Eng., Waseda Univ., Tokyo, Japan
Abstract :
A hierarchical redundancy scheme using additional bypass linking (ABL) is proposed for constructing fault-tolerant massively parallel computers with hierarchically ring-connected, mesh-connected and cube-connected interconnection networks. This scheme enables a redundant hierarchical network to be constructed with a simple nested structure by using a feature of the ABL scheme, which is that it uses graph-node coloring for bypass allocation to the component network in order to minimize the number of bypass links and that the redundant component network can be treated as a processing element (PE) with a fixed number of external connections if these connections are provided in the bypass links. The spare circuits with hierarchical structures can greatly enhance PE-to-PE communications while achieving strong fault tolerance
Keywords :
fault tolerant computing; graph colouring; multiprocessor interconnection networks; parallel architectures; redundancy; additional bypass linking; cube-connected type; fault-tolerant interconnection networks; graph-node coloring; hierarchical interconnection networks; hierarchical redundancy scheme; massively parallel computers; mesh-connected type; nested structure; ring-connected type; spare circuits; Circuit faults; Computer networks; Concurrent computing; Fault tolerance; Hardware; Hypercubes; Joining processes; Multiprocessor interconnection networks; Redundancy; Switching circuits;
Conference_Titel :
Defect and Fault Tolerance in VLSI Systems, 1997. Proceedings., 1997 IEEE International Symposium on
Conference_Location :
Paris
Print_ISBN :
0-8186-8168-3
DOI :
10.1109/DFTVS.1997.628329