Method for generating hierarchical fault-tolerant mesh architectures

A method for configuring a fault-tolerant target mesh M' from a multiprocessor network, the multiprocessor network having components including a plurality of processor nodes and interconnections therebetween, the components being either healthy or faulty, the multiprocessor network being configured topologically as a d-dimensional fault-tolerant physical mesh M, such that the fault-tolerant target mesh M' is configured of healthy components of the multiprocessor network, the method comprising the steps of:

• a) selecting a dimension d', where 1.ltoreq.d'.ltoreq.d;
• b) creating a respective block of 2.sup.d' nodes in the target mesh M' corresponding to each respective one of the nodes in M, the nodes in the blocks of nodes having bit labels;
• c) adding edges within said blocks of 2.sup.d' nodes;
• d) for each edge in M, adding edges in the target mesh M' that link nodes located in the blocks corresponding to the nodes connected by said edge in M, based on the bit labels of the nodes in the different blocks, and based on complements of bits of the bit labels of the nodes in the different blocks;
• and
• e) configuring the physical mesh M as per the added edges.

A multiprocessor network comprising:

• a plurality of processor nodes;
• an interconnection network coupled between the processor nodes, the interconnection network including a plurality of respective edges, each respective edge being coupled between a respective pair of the nodes;
• and
• means for defining a fault-tolerant mesh from the nodes and the interconnection network, the fault-tolerant mesh being given by parameters n, d, d', and S.sub.1, S.sub.2, . . . , S.sub.d, where n, d, and d' are positive integers, where 1.ltoreq.d'.ltoreq.d, and where each S.sub.i, where 1.ltoreq.i.ltoreq.d, is a subset of {1, 2, . . . , n-1}, the means for defining including means for defining a set of n labeled d'-cubes numbered 0 through n-1,
• (i) wherein each node with d'-cube label (x.sub.1, x.sub.2, . . . , x.sub.d') in d'-cube j, where 0.ltoreq.j.ltoreq.n-1, is connected to node (x.sub.1, x.sub.2, . . . , x.sub.i-1, complement (x.sub.i), x.sub.i+1, . . . , x.sub.d') in d'-cube (j+(2x.sub.i -1)s) mod n, where s.epsilon.S.sub.i and 1.ltoreq.i.ltoreq.d', and
• (ii) wherein each node with d'-cube label (x.sub.1, x.sub.2, . . . , x.sub.d') in d'-cube j, where 0.ltoreq.j.ltoreq.n-1, is further connected to node (x.sub.1, x.sub.2, . . . , x.sub.d') in d'-cube (j+s) mod n, where s.epsilon.S.sub.i and d'.ltoreq.i.ltoreq.d.

A computer program product:

• for use on a computer system, for generating a fault-tolerant target mesh M' from a multiprocessor network, the multiprocessor network having components including a plurality of processor nodes and interconnections therebetween, the components being either healthy or faulty, the multiprocessor network being configured topologically as a d-dimensional fault-tolerant physical mesh M, such that the fault-tolerant target mesh M' is to be configured of healthy components of the multiprocessor network, the computer program product comprising:
• a) a recording medium;
• b) means recorded on said recording medium for instructing said computer system to create a plurality of respective blocks of nodes in the mesh M' corresponding to respective ones of the nodes in M, the nodes in the blocks of nodes having bit labels;
• c) means recorded on said recording medium for instructing said computer system to add edges within each said block of nodes;
• d) means recorded on said recording medium for instructing said computer system to add edges between the nodes in the different blocks of nodes in the target mesh M' corresponding to the edges in M, based on the bit labels of the nodes in the different blocks, and based on complements of bits of the bit labels of the nodes in the different blocks;
• and
• e) configuring the physical mesh M as per the added edges.

A computer program product for use on a computer system for generating a fault-tolerant target mesh M' from a multiprocessor network, the multiprocessor network having components including a plurality of processor nodes and interconnections therebetween, the components being either healthy or faulty, the multiprocessor network being configured topologically as a d-dimensional fault-tolerant physical mesh M, such that the fault-tolerant target mesh M' is configured of healthy components of the multiprocessor network, the computer program product comprising:

• a) a recording medium;
• b) means recorded on said recording medium for instructing said computer system to select a dimension d', where 1.ltoreq.d'.ltoreq.d;
• c) means recorded on said recording medium for instructing said computer system to create a respective block of 2.sup.d' nodes in the mesh M' corresponding to each respective node in M, the nodes in the blocks of nodes having bit labels;
• d) means recorded on said recording medium for instructing said computer system to add edges within said blocks of 2.sup.d' nodes;
• e) means, recorded on said recording medium, for instructing said computer system, for each edge in M, to add edges in M' that link nodes located in the blocks corresponding to the nodes connected by said edge in M, based on the bit labels of the nodes in the different blocks, and based on complements of bits of the bit labels of the nodes in the different blocks;
• and
• f) configuring the physical mesh M as per the added edges.