FAULT TOLERANT MESH AND ITS CONSTITUTION METHOD

摘要

PURPOSE: To provide a fault tolerant mesh architecture with a minimum rise of cost and a minimum degradation of performance. CONSTITUTION: The method and device tolerant of a maximum of k faults in a d-dimensional mesh architecture are provided based on a technique for addition of spare components (nodes) and extra links (edges) which adds m pieces of spare nodes (m>=k) to keep the maximum number of links per node (the order of the mesh) small. When the d-dimensional mesh architecture has N pieces of nodes (N=n1×n2×...×n4 , the fault tolerant mesh can be expressed with a diagonal or annular graph having N+m-k nodes. The characteristic of this graph is utilized that the part of the graph except faulty nodes can include a graph corresponding to a target mesh M as a subgraph only at the time of d>=2 and n4 >=3 after execution of a prescribed node renaming process in the case of the existence of k pieces of or less faulty nodes.