US5280607A — Method and apparatus for tolerating faults in mes…

Claim 1

Independent Claim 199 words

A fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, comprising: (a)N+k nodes, where the additional k nodes are of the same type as in mesh M, arranged in the form of a circulant graph; and (b)a plurality of edges for said circulant graph where, for k odd, the edges are defined by the union of the following sets of offsets: (1+j such that 0≦j≦(k-1)/2}; n 1 +j such that 0≦j≦(k-1)2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; and for k even, the edges are defined by the union of the following sets of offsets; {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}.

Claim 2

Dependent Claim 199 words

A fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, comprising: (a)N+k nodes, where the additional k nodes are of the same type as in mesh M, arranged in the form of a circulant graph; and (b)a plurality of edges for said circulant graph where, for k odd, the edges are defined by the union of the following sets of offsets: (1+j such that 0≦j≦(k-1)/2}; n 1 +j such that 0≦j≦(k-1)2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; and for k even, the edges are defined by the union of the following sets of offsets; {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}.

Claim 3

Dependent Claim 32 words

Apparatus as set forth in claim 1, wherein the maximum degree of the circulant graph and corresponding mesh M k is d(k+1) when k is odd and d(k+2) when k is even.

Claim 4

Dependent Claim 23 words

Apparatus as set forth in claim 1, wherein fault tolerant mesh M k , for k=1, has the same degree as mesh M.

Claim 5

Independent Claim 216 words

A method of constructing a k fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧ 3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, comprising the steps of: (a) arranging the N nodes of mesh M and exactly k additional nodes, where the additional k nodes are of the same type as in mesh M, in the form of a circulant graph; (b) defining the edges of said circulant graph, for k odd, by the union of the following sets of offsets: {1+j such that 0≦j≦(k-1)/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; and (c) defining the edges of said circulant graph, for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}.

Claim 6

Independent Claim 216 words

A method of constructing a k fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧ 3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, comprising the steps of: (a) arranging the N nodes of mesh M and exactly k additional nodes, where the additional k nodes are of the same type as in mesh M, in the form of a circulant graph; (b) defining the edges of said circulant graph, for k odd, by the union of the following sets of offsets: {1+j such that 0≦j≦(k-1)/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; and (c) defining the edges of said circulant graph, for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}.

Claim 7

Independent Claim 253 words

A method for fabricating a d-dimensional k fault tolerant mesh M k from a given target mesh M which can be any d-dimensional mesh with N=n 1 ×n 2 x . . . x n d nodes, where each n i specifies the length of the i-th dimension, and d≧2 and n d ≧3, comprising the steps of: (a) determining the dimension d of target mesh M; (b) identifying the structure of target mesh M by inputting the values of n 1 , n 2 , . . . , n d ; (c) inputting k, the number of faults to be sustained by the fault tolerant mesh M k being constructed; (d) defining a circulant graph having exactly N+k nodes; (e) defining the edges of said circulant graph, for k odd, by the union of the following sets of offsets; {1+j such that 0≦j≦(k-1)/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; (f) defining the edges of said circulant graph for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+such that 0 ≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}; and (g) constructing the mesh that corresponds to said circulant graph to form the d-dimensional k fault tolerant mesh M k .

Claim 8

Independent Claim 253 words

A method for fabricating a d-dimensional k fault tolerant mesh M k from a given target mesh M which can be any d-dimensional mesh with N=n 1 ×n 2 x . . . x n d nodes, where each n i specifies the length of the i-th dimension, and d≧2 and n d ≧3, comprising the steps of: (a) determining the dimension d of target mesh M; (b) identifying the structure of target mesh M by inputting the values of n 1 , n 2 , . . . , n d ; (c) inputting k, the number of faults to be sustained by the fault tolerant mesh M k being constructed; (d) defining a circulant graph having exactly N+k nodes; (e) defining the edges of said circulant graph, for k odd, by the union of the following sets of offsets; {1+j such that 0≦j≦(k-1)/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; (f) defining the edges of said circulant graph for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+such that 0 ≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}; and (g) constructing the mesh that corresponds to said circulant graph to form the d-dimensional k fault tolerant mesh M k .

Claim 9

Independent Claim 201 words

A method for locating a healthy target mesh M in a fault tolerant mesh M k , in the presence of up to k faults, and reconfiguring M k to obtain M, given (1) the dimension d of M, (2) the value of k, (3), the values of n 1 , n 2 , . . . , n d , where each n i is the length of a side in the d-dimensional mesh M, and d≧2 and n 2 ≧3, where x is the number of faulty nodes, (4) the structure of the fault tolerant mesh M k in terms of a circulant graph model, and (5) the locations of the up to k faults in M k , comprising the steps of: (a) determining if the number of faults sustained in M k is less than k; (b) choosing k-x nonfaulty nodes and designating the k-x nodes as faulty if x<k, for a total of k faulty nodes; (c) identifying node 0 in the target mesh M from among the nonfaulty nodes remaining in M k ; and (d) relabeling the nodes in M k to obtain healthy mesh M using a row-major ordering starting at node 0.

Claim 10

Independent Claim 201 words

A method for locating a healthy target mesh M in a fault tolerant mesh M k , in the presence of up to k faults, and reconfiguring M k to obtain M, given (1) the dimension d of M, (2) the value of k, (3), the values of n 1 , n 2 , . . . , n d , where each n i is the length of a side in the d-dimensional mesh M, and d≧2 and n 2 ≧3, where x is the number of faulty nodes, (4) the structure of the fault tolerant mesh M k in terms of a circulant graph model, and (5) the locations of the up to k faults in M k , comprising the steps of: (a) determining if the number of faults sustained in M k is less than k; (b) choosing k-x nonfaulty nodes and designating the k-x nodes as faulty if x<k, for a total of k faulty nodes; (c) identifying node 0 in the target mesh M from among the nonfaulty nodes remaining in M k ; and (d) relabeling the nodes in M k to obtain healthy mesh M using a row-major ordering starting at node 0.

Claim 11

Independent Claim 128 words

A method for finding healthy mesh M in a fault tolerant mesh M k , given a set of up to k faults, where M k has N+k=(n 1 ×n 2 x . . . x n d )+k nodes, where each n i specifies the length of the i-th dimension, where d≧2 and n d ≧3, and M has N nodes, comprising the steps of: (a) determining which nonfaulty nodes in M k are to be considered as candidates for node 0 in mesh M; (b) determining which of the candidate nonfaulty nodes is to be node 0 in the target mesh; and (c) assigning an identifier to each nonfaulty node, starting with node 0, where the set of identifiers represents a row-major ordering of mesh M.

Claim 12

Independent Claim 128 words

A method for finding healthy mesh M in a fault tolerant mesh M k , given a set of up to k faults, where M k has N+k=(n 1 ×n 2 x . . . x n d )+k nodes, where each n i specifies the length of the i-th dimension, where d≧2 and n d ≧3, and M has N nodes, comprising the steps of: (a) determining which nonfaulty nodes in M k are to be considered as candidates for node 0 in mesh M; (b) determining which of the candidate nonfaulty nodes is to be node 0 in the target mesh; and (c) assigning an identifier to each nonfaulty node, starting with node 0, where the set of identifiers represents a row-major ordering of mesh M.

Claim 13

Dependent Claim 245 words

A process for locating a target d-dimensional mesh M having N nodes, where N=n 1 ×n 2 x . . . x n d , where each n i specifies the length of the i-th dimension, and d≧2 and n d ≧3 in a k fault tolerant mesh M k that has sustained up to k faults, where M k can be represented by a circulant graph model, and where the largest offset in said graph is j=n 1 ×n 2 x . . . x n d-1 , comprising the steps of: (a) inputting the identification of each faulty and nonfaulty node in M k and the circulant graph representation thereof; (b) counting the number of faulty nodes and nonfaulty nodes in M k for all nodes i in M k , where 0≦i≦N+k-1, by visiting each node, starting a node i, proceeding in a first preselected direction around the circulant graph; (c) checking the nonfaulty node count after each nonfaulty node is detected and determining if the nonfaulty node count is greater than j; (d) terminating the visitation of nodes in said first preselected direction if the nonfaulty node count is greater than j; (e) determining, after said step of terminating, if the number of faulty nodes is greater than k/2 and if so, designating node i as a marked node, otherwise designating node i as unmarked; and (f) reiterating the aforestated process for each node i in mesh M k for 0≦i≦N+k-1.

Claim 14

Dependent Claim 245 words

A process for locating a target d-dimensional mesh M having N nodes, where N=n 1 ×n 2 x . . . x n d , where each n i specifies the length of the i-th dimension, and d≧2 and n d ≧3 in a k fault tolerant mesh M k that has sustained up to k faults, where M k can be represented by a circulant graph model, and where the largest offset in said graph is j=n 1 ×n 2 x . . . x n d-1 , comprising the steps of: (a) inputting the identification of each faulty and nonfaulty node in M k and the circulant graph representation thereof; (b) counting the number of faulty nodes and nonfaulty nodes in M k for all nodes i in M k , where 0≦i≦N+k-1, by visiting each node, starting a node i, proceeding in a first preselected direction around the circulant graph; (c) checking the nonfaulty node count after each nonfaulty node is detected and determining if the nonfaulty node count is greater than j; (d) terminating the visitation of nodes in said first preselected direction if the nonfaulty node count is greater than j; (e) determining, after said step of terminating, if the number of faulty nodes is greater than k/2 and if so, designating node i as a marked node, otherwise designating node i as unmarked; and (f) reiterating the aforestated process for each node i in mesh M k for 0≦i≦N+k-1.

Claim 15

Dependent Claim 23 words

A method as set forth in claim 8, wherein each nonfaulty marked node is a candidate for node 0 in target mesh M.

Claim 16

Dependent Claim 29 words

A method as set forth in claim 9, further comprising the step of determining which nonfaulty marked node is to be designated as node 0 in target mesh M.

Claim 17

Dependent Claim 171 words

A method as set forth in claim 10, wherein said step of determining which nonfaulty marked node is to be designated as node 0 in target mesh M further comprises the steps of: (a) visiting the nodes of said circulant graph, starting with an arbitrary node, in a second preselected direction; (b) counting, as each node is visited, the number of nonfaulty unmarked nodes, resetting the count whenever a nonfaulty marked node is visited; (c) terminating the step of visiting when the number of nonfaulty unmarked nodes is greater than or equal to N/2, and designating the node being visited at the time of termination as the starting node of a second visitation process; (d) visiting the nodes of said circulant graph in a second visitation process, beginning with said starting node, in the opposite direction of said second preselected direction, and terminating said second visitation process when a nonfaulty node which is marked is encountered; and (e) designating the encountered nonfaulty marked node as node 0 of target mesh M.

Claim 18

Dependent Claim 20 words

A method as set forth in claim 11, further comprising the step of assigning node identifiers to each nonfaulty node.

Claim 19

Dependent Claim 68 words

A method as set forth in claim 11, wherein said step of assigning node identifiers to each nonfaulty node further comprises the steps of: (a) visiting the nodes of said circulant graph in an ascending order, starting with node 0; and (b) assigning the nodes visited after node 0, in order, the values 1, 2, . . . , N-1, creating a row-major ordering of the nonfaulty mesh.

Claim 20

Dependent Claim 58 words

A method as set forth in claim 13, further comprising the steps of: (a) determining if the number of faults sustained in M k is less than k; and (b) choosing k-x nonfaulty nodes and designating the k-x nodes as faulty if x<k, for a total of k faulty nodes, where x is the number of faulty nodes.

Claim 21

Independent Claim 302 words

A method of constructing a k fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, and locating M in M k when up to k faults are sustained by M k , comprising the steps of: (a) arranging the N nodes of mesh M and exactly k additional nodes, where the additional k nodes are of the same type as in mesh M, in the form of a circulant graph; (b) defining the edges of said circulant graph for k odd, by the union of the following sets of offsets: {1+j such that 0+j≦(k-1 )/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; (c) defining the edges of said circulant graph for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}; (d) determining which nonfaulty nodes in M k are to be considered as candidates for node 0 in mesh M whenever M k sustains up to k faults; (e) determining which of the candidates nonfaulty nodes is to be node 0 in target mesh M; and (f) assigning an identifier to each nonfaulty node, starting with node 0, where the set of identifiers represents a row-major ordering of mesh M.

Claim 22

Independent Claim 302 words

A method of constructing a k fault tolerant mesh M k that includes a d-dimensional mesh M having N=n 1 ×n 2 x . . . x n d identical nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, where M k can sustain up to k faults and be reconfigured without switches to form mesh M, and locating M in M k when up to k faults are sustained by M k , comprising the steps of: (a) arranging the N nodes of mesh M and exactly k additional nodes, where the additional k nodes are of the same type as in mesh M, in the form of a circulant graph; (b) defining the edges of said circulant graph for k odd, by the union of the following sets of offsets: {1+j such that 0+j≦(k-1 )/2}; {n 1 +j such that 0≦j≦(k-1)/2}; {(n 1 ×n 2 )+j such that 0≦j≦(k-1)/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦(k-1)/2}; (c) defining the edges of said circulant graph for k even, by the union of the following sets of offsets: {1+j such that 0≦j≦k/2}; {n 1 +j such that 0≦j≦k/2}; {(n 1 ×n 2 )+j such that 0≦j≦k/2}; up to {(n 1 ×n 2 x . . . x n d-1 )+j such that 0≦j≦k/2}; (d) determining which nonfaulty nodes in M k are to be considered as candidates for node 0 in mesh M whenever M k sustains up to k faults; (e) determining which of the candidates nonfaulty nodes is to be node 0 in target mesh M; and (f) assigning an identifier to each nonfaulty node, starting with node 0, where the set of identifiers represents a row-major ordering of mesh M.

Claim 23

Dependent Claim 33 words

A method as set forth in claim 15, wherein the maximum degree of the circulant graph and corresponding mesh M k is d(k+1) when k is odd and d(k+2) when k is even.

Claim 24

Dependent Claim 24 words

A method as set forth in claim 15, wherein fault tolerant mesh M k , for k=1, has the same degree as mesh M.

Claim 25

Dependent Claim 158 words

Apparatus for identifying a health mesh M in a fault tolerant mesh M k , given a set of up to k faults, where M k has N+k=(n 1 ×n 2 x . . . x n d )+k nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, and M has N nodes, comprising: (a) means for identifying which nonfault nodes in M k are to be considered as candidates for node 0 in mesh M; (b) means for determining which of the candidate nonfaulty nodes is to be node 0 in target mesh M, wherein said means for determining is responsive to input from said means for identifying; and (c) reconfiguration means for assigning an identifier to each nonfaulty node in mesh M k , starting with node 0, as identified by said means for determining, where the set of identifiers represents a row-major order of mesh M.

Claim 26

Dependent Claim 158 words

Apparatus for identifying a health mesh M in a fault tolerant mesh M k , given a set of up to k faults, where M k has N+k=(n 1 ×n 2 x . . . x n d )+k nodes, where each n i specifies the length of the i-th dimension, with d≧2 and n d ≧3, and M has N nodes, comprising: (a) means for identifying which nonfault nodes in M k are to be considered as candidates for node 0 in mesh M; (b) means for determining which of the candidate nonfaulty nodes is to be node 0 in target mesh M, wherein said means for determining is responsive to input from said means for identifying; and (c) reconfiguration means for assigning an identifier to each nonfaulty node in mesh M k , starting with node 0, as identified by said means for determining, where the set of identifiers represents a row-major order of mesh M.

Claim 27

Dependent Claim 33 words

Apparatus as set forth in claim 18, wherein said M k , in the presence of up to k faults, may be reconfigured into healthy target mesh M without the use of switches.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1997-01-17	1997-07-19	1998-01-18	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2001-01-17	2001-07-19	2002-01-18	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2005-01-17	2005-07-19	2006-01-18	$7700.00	Window Closed / Lapsed

Method and apparatus for tolerating faults in mesh architectures

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag