US5271014A — Method and apparatus for a fault-tolerant mesh wi…

Claim 1

Independent Claim 153 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein at least one of the extra nodes is an input/output node.

Claim 2

Dependent Claim 153 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein at least one of the extra nodes is an input/output node.

Claim 3

Dependent Claim 154 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is topologically equivalent to at least one hexagon.

Claim 4

Dependent Claim 154 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is topologically equivalent to at least one hexagon.

Claim 5

Dependent Claim 261 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3; and the number of extra nodes m is given by m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even; for k being odd, the edges are defined by the union of the following sets of offsets: ##EQU4## for k being even, the edges are defined by the union of the following sets of offsets: ##EQU5##

Claim 6

Dependent Claim 261 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3; and the number of extra nodes m is given by m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even; for k being odd, the edges are defined by the union of the following sets of offsets: ##EQU4## for k being even, the edges are defined by the union of the following sets of offsets: ##EQU5##

Claim 7

Dependent Claim 35 words

A fault-tolerant mesh as recited in claim 3, wherein the degree of each node of the circulant graph and corresponding mesh M k is (d-1)k+d+3 when k is odd and (d-1)k+2d+2 when k is even.

Claim 8

Dependent Claim 220 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is d-dimensional, and the number of nodes n is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3; and the mesh is two-dimensional, d=2, n 1 equals a number of columns c, and n 2 equals a number of rows r.

Claim 9

Dependent Claim 220 words

A fault-tolerant mesh M k comprising: (a) N+m nodes, the mesh M k being capable of supporting a target mesh M from which a mesh M may be defined, the mesh M having N nodes, m being a number of extra nodes in the mesh M k , wherein the nodes may be represented by one of a diagonal graph and a circulant graph, each node has an identifier assigned thereto, the value of each identifier being determined with respect to the graph, the fault-tolerant mesh M k being able to sustain up to k faults while facilitating definition of the mesh M; and (b) a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; wherein the mesh M k is d-dimensional, and the number of nodes n is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3; and the mesh is two-dimensional, d=2, n 1 equals a number of columns c, and n 2 equals a number of rows r.

Claim 10

Dependent Claim 39 words

A fault-tolerant mesh as recited in claim 5 wherein, for k being odd, the edges are defined by the following set of offsets: {c+j|-1≦j≦(k+1)/2}; and for k being even, the edges are defined by the set of offsets: {c+j|-1≦j≦(k+2)/2}.

Claim 11

Dependent Claim 29 words

A fault-tolerant mesh as recited in claim 6, wherein the number of extra nodes m is given by m=k+c-1 for c being odd and m=k+c-2 for c being even.

Claim 12

Dependent Claim 31 words

A fault-tolerant mesh as recited in claim 6, wherein the degree of each node of the mesh M k is k+5 when k is odd and k+6 when k is even.

Claim 13

Dependent Claim 26 words

A fault-tolerant mesh as recited in claim 5, wherein the number of extra nodes m equals the number of faults k which are to be tolerated.

Claim 14

Dependent Claim 22 words

A fault-tolerant mesh as recited in claim 9, wherein each node (i,j) of M is assigned an identifier in a row-major order.

Claim 15

Dependent Claim 39 words

A fault-tolerant mesh as recited in claim 10, wherein the connection pattern for the edges connecting the nodes is defined by a set of offsets {1, 2, . . . , k+1, c, c+1, . . . , c+k}.

Claim 16

Dependent Claim 23 words

A fault-tolerant mesh as recited in claim 10, wherein the degree of each node of the mesh M k is at most 4k+4.

Claim 17

Dependent Claim 21 words

A fault-tolerant mesh as recited in claim 9, wherein each node (i,j) of M is assigned an identifier in antidiagonal-major order.

Claim 18

Dependent Claim 29 words

A fault-tolerant mesh as recited in claim 13, wherein the connection pattern for the edges is defined by a set of offsets {c, c+1, . . . , c+k+1}.

Claim 19

Dependent Claim 23 words

A fault-tolerant mesh as recited in claim 13, wherein the degree of each node of the mesh M k is at most 2k+4.

Claim 20

Dependent Claim 21 words

A fault-tolerant mesh as recited in claim 9, wherein each node of M is assigned an identifier in interleaved antidiagonal-major order.

Claim 21

Dependent Claim 33 words

A fault-tolerant mesh as recited in claim 16, wherein the connection pattern for the edges is defined by a set of offsets {a, a+1, . . . , b+k} where a=rc/2-r/2 and b=rc/2+r/2.

Claim 22

Dependent Claim 46 words

A fault-tolerant mesh as recited in claim 16, wherein the degree of each node of the mesh M k is at most k+r+1 for r being odd and c being even, at most k+r for r being even, and at most k+r for c being odd.

Claim 23

Dependent Claim 35 words

A fault-tolerant mesh as recited in claim 9, wherein the number of rows r is odd, and each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=(i(r-1)/2) mod r.

Claim 24

Dependent Claim 29 words

A fault-tolerant mesh as recited in claim 19, wherein the connection pattern for the edges connecting the nodes is defined by a set of offsets {(r-1)c/2,(r-1)c/2+1, . . .,(r-1)c/2+k+1}.

Claim 25

Dependent Claim 31 words

A fault-tolerant mesh as recited in claim 19, wherein the degree of each node of the mesh M k is at most 2k+4 for k≦c-3, and at most c+k+1 for k>c-3.

Claim 26

Dependent Claim 30 words

A fault-tolerant mesh as recited in claim 9, wherein r mod 4=0, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-1)i) mod r.

Claim 27

Dependent Claim 30 words

A fault-tolerant mesh as recited in claim 22, wherein the connection pattern for the edges connecting the nodes is defined by a set of offsets {(r/2-1)c,(r/2-1)c+1, . . . ,(r/2-1)c+k+1}.

Claim 28

Dependent Claim 31 words

A fault-tolerant mesh as recited in claim 22, wherein the degree of each node of the mesh M k is at most 2k+4 for k≦2c-3, and at most 2c+k+1 for k>2c-3.

Claim 29

Dependent Claim 30 words

A fault-tolerant mesh as recited in claim 9, wherein r mod 4=2, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-2)i) mod r.

Claim 30

Dependent Claim 30 words

A fault-tolerant mesh as recited in claim 25, wherein the connection pattern for the edges connecting the nodes is defined by a set of offsets {(r/2-2)c,(r/2-2)c+1, . . . ,(r/2-2)c+k+1}.

Claim 31

Dependent Claim 30 words

A fault-tolerant mesh as recited in claim 25, wherein the degree of each node of the mesh M k is at most 2k+4for k≦4c-3, and at most 4c+k+1 for k>4c-3.

Claim 32

Independent Claim 152 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is topologically equivalent to at least one hexagon.

Claim 33

Independent Claim 152 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is topologically equivalent to at least one hexagon.

Claim 34

Independent Claim 194 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh which is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3.

Claim 35

Independent Claim 194 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh which is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3.

Claim 36

Dependent Claim 68 words

A method as recited in claim 29 wherein, in the step of utilizing, m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even, and the step of utilizing includes defining the edges, for k odd, by the union of the following set of offsets: ##EQU6## defining the edges, for k even, by the union of the following sets of offsets: ##EQU7##

Claim 37

Dependent Claim 138 words

A method as recited in claim 29, wherein the step of utilizing includes: (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 one of a diagonal graph and a circulant graph having N+m nodes, where m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even; (e) defining the edges of the graph, for k odd, by the union of the following sets of offsets: ##EQU8## (f) defining the edges of the graph, for k even, by the union of the following sets of offsets: ##EQU9##

Claim 38

Independent Claim 163 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh which is two-dimensional, wherein d=2, n 1 equals a number of columns c, and n 2 equals a number of rows r.

Claim 39

Independent Claim 163 words

A method for constructing a mesh M k tolerating up to k faults, comprising the steps of: (a) utilizing one of a diagonal graph representation and a circulant graph representation for the mesh M k , which includes a target mesh M having N nodes, and m additional spare nodes, as a model for fabricating M k ; (b) assigning an identifier to each node, the value of each identifier being determined with respect to the graph; (c) defining a plurality of edges connected between respective ones of the nodes in accordance with a connection pattern defined in terms of the identifiers assigned to the nodes and the positions of the nodes in the graph; and (d) fabricating said k-fault-tolerant mesh M k based on the graph representation; wherein the step of utilizing includes utilizing a graph representation of a mesh which is two-dimensional, wherein d=2, n 1 equals a number of columns c, and n 2 equals a number of rows r.

Claim 40

Dependent Claim 37 words

A method as recited in claim 32, wherein, for k being odd, the edges are defined by the set of offsets: {c+j|-1≦j≦(k+1)/2}; and for k being even, the edges are defined by the set of offsets: {c+j|-1≦j≦(k+2)/2}.

Claim 41

Dependent Claim 28 words

A method as recited in claim 33, wherein the number of extra nodes m is given by m=k+c-1 for c being odd and m=k+c-2 for c being even.

Claim 42

Dependent Claim 25 words

A method as recited in claim 32 wherein the number of spare nodes m is equal to the number of faults k to be tolerated.

Claim 43

Dependent Claim 19 words

A method as recited in claim 35, wherein each node of M is assigned an identifier in row-major order.

Claim 44

Dependent Claim 38 words

A method as recited in claim 36, wherein the edges are defined according to a connection pattern is defined by a set of offsets {1, 2, . . . , k+1, c, c+1, . . . , c+k}.

Claim 45

Dependent Claim 20 words

A method as recited in claim 35, wherein each node (i,j) of M is assigned an identifier in antidiagonal-major order.

Claim 46

Dependent Claim 28 words

A method as recited in claim 38, wherein the connection pattern for the edges is defined by a set of offsets {c, c+1, . . . , c+k+1}.

Claim 47

Dependent Claim 20 words

A method as recited in claim 35, wherein each node of M is assigned an identifier in interleaved antidiagonal-major order.

Claim 48

Dependent Claim 41 words

A method as recited in claim 40, wherein the edges are defined according to a connection pattern defined by a set of offsets {a, a+1, . . . , b+k} where a= rc/2 - r/2 and b= rc/2 + r/2 .

Claim 49

Dependent Claim 34 words

A method as recited in claim 35, wherein the number of rows r is odd, and each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=(i(r-1))/2 mod r.

Claim 50

Dependent Claim 28 words

A method as recited in claim 42, wherein the edges are defined according to a connection pattern defined by a set of offsets {(r-1)c/2,(r-1)c/2+1, . . . ,(r-1)c/2+k+1}.

Claim 51

Dependent Claim 29 words

A method as recited in claim 35, wherein r mod 4=0, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-1)i) mod r.

Claim 52

Dependent Claim 28 words

A method as recited in claim 44, wherein the edges are defined according to a connection pattern defined by a set of offsets {(r/2-1)c,(r/2-1)c+1, . . . ,(r/2-1)c+k+1}.

Claim 53

Dependent Claim 29 words

A method as recited in claim 35, wherein r mod 4=2, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-2)i) mod r.

Claim 54

Dependent Claim 29 words

A method as recited in claim 46, wherein the edges are defined according to a connection pattern defined by a set of offsets {(r/2-2)c,(r/2-2)c+1, . . . , (r/2-2)c+k+1}.

Claim 55

Independent Claim 264 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 value of n 1 , n 2 , . . . , n d , the values of the lengths of the sides of the d-dimensional mesh M, where n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3, (4) the structure of the fault-tolerant mesh M k in terms of one of a diagonal graph model and a circulant graph model, and (5) the location of 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 non-faulty nodes and designating the k-x nodes as faulty if x<k, where x is the number of actual faulty nodes, for a total of k faults; (c) identifying a first node of the target mesh M from among the non-faults remaining in M k ; and (d) relabeling the nodes in M k , in relation to the first node to obtain the healthy mesh M; wherein, starting with the first node of the target mesh, an identifier l is assigned to each non-faulty node (i 1 , i 2 , . . . , i d ), where ##EQU10## and where nodes with label l for which i d <0 or i d ≧n d are omitted.

Claim 56

Independent Claim 264 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 value of n 1 , n 2 , . . . , n d , the values of the lengths of the sides of the d-dimensional mesh M, where n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3, (4) the structure of the fault-tolerant mesh M k in terms of one of a diagonal graph model and a circulant graph model, and (5) the location of 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 non-faulty nodes and designating the k-x nodes as faulty if x<k, where x is the number of actual faulty nodes, for a total of k faults; (c) identifying a first node of the target mesh M from among the non-faults remaining in M k ; and (d) relabeling the nodes in M k , in relation to the first node to obtain the healthy mesh M; wherein, starting with the first node of the target mesh, an identifier l is assigned to each non-faulty node (i 1 , i 2 , . . . , i d ), where ##EQU10## and where nodes with label l for which i d <0 or i d ≧n d are omitted.

Claim 57

Dependent Claim 215 words

A process for locating a target d-dimensional mesh M having N nodes, where N=n 1 ×n 2 × . . . ×n d , with n 1 ≦n 2 < . . . ≦n d 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 j=n 1 ×n 2 × . . . ×n d-1 , comprising the steps of: (a) identifying each faulty and non-faulty node in M k and the circulant graph representation thereof; (b) counting the number of faults and non-faults in M k for all nodes i in M k , where 0≦i≦N+m-k-1, starting at node i, proceeding in a first order around the circulant graph model; (c) checking the non-fault count after each non-faulty node is detected and determining if the non-fault count is greater than j; (d) terminating the step of counting if the non-fault count is greater than j; (e) determining, after said step of terminating, if the number of faults is greater than k/2 and if so, designating node i as a marked node, otherwise designating node i as unmarked; and (f) repeating steps (a) through (e) for each node i in mesh M k for 0≦i≦N+m-k-1.

Claim 58

Dependent Claim 215 words

A process for locating a target d-dimensional mesh M having N nodes, where N=n 1 ×n 2 × . . . ×n d , with n 1 ≦n 2 < . . . ≦n d 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 j=n 1 ×n 2 × . . . ×n d-1 , comprising the steps of: (a) identifying each faulty and non-faulty node in M k and the circulant graph representation thereof; (b) counting the number of faults and non-faults in M k for all nodes i in M k , where 0≦i≦N+m-k-1, starting at node i, proceeding in a first order around the circulant graph model; (c) checking the non-fault count after each non-faulty node is detected and determining if the non-fault count is greater than j; (d) terminating the step of counting if the non-fault count is greater than j; (e) determining, after said step of terminating, if the number of faults is greater than k/2 and if so, designating node i as a marked node, otherwise designating node i as unmarked; and (f) repeating steps (a) through (e) for each node i in mesh M k for 0≦i≦N+m-k-1.

Claim 59

Dependent Claim 25 words

A method as set forth in claim 49, wherein each non-faulty marked node is a candidate for the first node of the target mesh M.

Claim 60

Dependent Claim 31 words

A method as set forth in claim 50, further comprising the step of determining which non-faulty marked node is to be designated as the first node of the target mesh M.

Claim 61

Dependent Claim 174 words

A method as set forth in claim 51, wherein said step of determining which non-faulty marked node is to be designated as the first node of the target mesh M further comprises the steps of: (a) visiting the nodes of said circulant graph, starting with an arbitrary node, in a second pre-selected direction; (b) counting, as each node is visited, the number of non-faulty unmarked nodes, resetting the count whenever a non-faulty marked node is visited; (c) terminating the step of visiting when the number of non-faulty 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 pre-selected direction, and terminating said second visitation process when a non-fault which is marked is encounted; and (e) designating the encountered non-faulty marked node as the first node of the target mesh M.

Claim 62

Dependent Claim 20 words

A method as set forth in claim 52, further comprising the step of assigning node identifiers to each non-faulty node.

Claim 63

Dependent Claim 58 words

A method as set forth in claim 53, 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 non-faulty nodes and designating the k-x nodes as faulty if x<k, where x is the number of actually faulty nodes, for a total of k faults.

Claim 64

Independent Claim 195 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is topologically equivalent to at least one hexagon.

Claim 65

Independent Claim 195 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is topologically equivalent to at least one hexagon.

Claim 66

Independent Claim 239 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3.

Claim 67

Independent Claim 239 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the step of utilizing includes utilizing a graph representation of a mesh M k which is d-dimensional, and the number of nodes N is given by N=n 1 ×n 2 × . . . ×n d , where each n i represents the size of the mesh M in the i-th dimension, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3.

Claim 68

Dependent Claim 46 words

A method as recited in claim 56 wherein the step of defining edges defines the edges of the graph, representing connections between respective ones of the nodes, by the union of the following sets of offsets: (i) for k odd, ##EQU11## (ii) for k even, ##EQU12##

Claim 69

Dependent Claim 67 words

A method as recited in claim 56, wherein the step of assigning an identifier l to each non-fault employs a naming convention, starting with the first node of the target mesh M in which: (i 1 , i 2 , . . . , i d ), where ##EQU13## and where nodes with label l for which i d <0 or i d ≧n d are omitted.

Claim 70

Independent Claim 196 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the maximum degree of the circulant graph and corresponding mesh M k is (d-1)k+d+3 when k is odd and (d-1)k+2d+2 when k is even.

Claim 71

Independent Claim 196 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured 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) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the maximum degree of the circulant graph and corresponding mesh M k is (d-1)k+d+3 when k is odd and (d-1)k+2d+2 when k is even.

Claim 72

Independent Claim 196 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured to from mesh M, and locating M in M k when up to k faults are sustained by M k , comprising the steps of: (a) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the mesh M to be located is two-dimensional, d=2, n 1 =a number of columns c, and n 2 =a number of rows r.

Claim 73

Independent Claim 196 words

A method of constructing a k-fault-tolerant mesh M k that includes a mesh M having N nodes, where M k can sustain up to k faults and be reconfigured to from mesh M, and locating M in M k when up to k faults are sustained by M k , comprising the steps of: (a) representing the N nodes of M and m additional nodes in the form of one of a diagonal graph and a circulant graph; (b) defining edges of the graph representing connections between respective ones of the nodes in terms of a predetermined connection pattern; (c) determining which non-faults in M k are to be considered as candidates for a first node of the mesh M whenever M k sustains up to k faults; (d) determining which of the candidate non-faults is to be the first node of the target mesh M; and (e) assigning an identifier to each non-fault according to a predetermined naming convention and starting with the first node of the target mesh M; wherein the mesh M to be located is two-dimensional, d=2, n 1 =a number of columns c, and n 2 =a number of rows r.

Claim 74

Dependent Claim 37 words

A method as recited in claim 60, wherein for k being odd, the edges are defined by the set of offsets: {c+j|-1≦j≦(k+1)/2}; and for k being even, the edges are defined by the set of offsets: {c+j|-1≦j≦(k+2)/2}.

Claim 75

Dependent Claim 28 words

A method as recited in claim 60, wherein the number of extra nodes m is equal to the number of faulty nodes k which are to be tolerated.

Claim 76

Dependent Claim 35 words

A method as recited in claim 62, wherein each node of M is assigned an identifier in row-major order, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 77

Dependent Claim 35 words

A method as recited in claim 62, wherein each node of M is assigned an identifier in antidiagonal-major order, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 78

Dependent Claim 36 words

A method as recited in claim 62, wherein each node of M is assigned an identifier in interleaved antidiagonal-major order, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 79

Dependent Claim 50 words

A method as recited in claim 62, wherein the number of rows r is odd, and each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=(i(r-1))/2 mod r, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 80

Dependent Claim 45 words

A method as recited in claim 62, wherein r mod 4=0, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-1)i) mod r, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 81

Dependent Claim 45 words

A method as recited in claim 62, wherein r mod 4=2, each node (i,j) of M is assigned an identifier given by the formula f(i+j)c+j, with f(i)=((r/2-2)i) mod r, and the step of relabeling is done in relation to the identifiers assigned to the nodes.

Claim 82

Independent Claim 201 words

An apparatus for identifying a healthy mesh M in a fault-tolerant mesh M k , given a set of up to k faults, where M k has N+m=(n 1 ×n 2 × . . . ×n d )+m nodes, and m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3, comprising: (a) means for identifying which nodes in M k are to be considered as candidates for a first node of the mesh M; (b) means for determining which of the candidate nodes is to be the first node of the target mesh M, wherein said means for determining is responsive to input from said means for identifying; and (c) reconfiguration means for assigning identifier to nodes in mesh M k , starting with the first node, as identified by said means for determining, wherein said set of identifiers are determined by ##EQU14## and where nodes with label l for which i d <0 or i d ≧n d are omitted. and where nodes with label l for which i d <0 or i d ≧n d are omitted.

Claim 83

Independent Claim 201 words

An apparatus for identifying a healthy mesh M in a fault-tolerant mesh M k , given a set of up to k faults, where M k has N+m=(n 1 ×n 2 × . . . ×n d )+m nodes, and m=k+n 1 -1 for n 1 being odd and m=k+n 1 -2 for n 1 being even, with n 1 ≦n 2 ≦ . . . ≦n d and n d ≧3, comprising: (a) means for identifying which nodes in M k are to be considered as candidates for a first node of the mesh M; (b) means for determining which of the candidate nodes is to be the first node of the target mesh M, wherein said means for determining is responsive to input from said means for identifying; and (c) reconfiguration means for assigning identifier to nodes in mesh M k , starting with the first node, as identified by said means for determining, wherein said set of identifiers are determined by ##EQU14## and where nodes with label l for which i d <0 or i d ≧n d are omitted. and where nodes with label l for which i d <0 or i d ≧n d are omitted.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1996-12-13	1997-06-14	1997-12-14	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2000-12-13	2001-06-14	2001-12-14	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2004-12-13	2005-06-14	2005-12-14	$7700.00	Window Closed / Lapsed

Method and apparatus for a fault-tolerant mesh with spare nodes

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag