Patent US5513313A successfully refreshed from Google Patents.
US5513313A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for generating hierarchical fault-tolerant mesh architectures
Assignee: Cisco Technology Inc
•
Filing: 1995-08-31
•
Granted: 1996-04-30
•
Expires: 2015-08-31
Abstract
Abstract A method is disclosed, for use with a multiprocessing hardware mesh architecture including nodes and a network of interconnections between the nodes, for defining and implementing a target logical mesh architecture utilizing a given subset of the nodes and the interconnections of the hardware architecture. Typically, the hardware mesh architecture includes redundant nodes and interconnections, sot hat the target logical mesh architecture may be defined from the hardware architecture several different ways. As a consequence, the target logical mesh architecture may be defined even in the presence of faulty nodes or interconnections in the hardware architecture. Frequently, the logical mesh is defined in terms of some regular pattern of interconnections. The method of the invention facilitates the definition of the desired logical mesh architecture from the hardware architecture, given the possibility that one or more faults are present, by initially defining logical blocks of nodes from among the functional nodes of the hardware architecture. Then, functional edges between the nodes defined within the logical blocks are defined as logical interconnections between the nodes of the logical blocks, such that the logical blocks, with the interconnections, are structurally consistent with portions of the logical mesh. Finally, additional edges are defined as logical interconnections between nodes in different logical blocks, these additional edges also being consistent with the structure of the logical mesh. The result is that the logical mesh has been fully defined from functional nodes and interconnections in the hardware architecture.
Inventors
- 👤 Jehoshua Bruck
- 👤 Robert E. Cypher
- 👤 Ching-Tien Ho
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 13:03
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/202; G06F11/2051
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
176 words
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 to be configured of healthy components of the multiprocessor network, the method comprising the steps of: a) creating 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; b) adding edges within each said block of nodes; c) adding 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 d) configuring the physical mesh M as per the added edges.
Claim 2
Independent Claim
176 words
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 to be configured of healthy components of the multiprocessor network, the method comprising the steps of: a) creating 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; b) adding edges within each said block of nodes; c) adding 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 d) configuring the physical mesh M as per the added edges.
Claim 3
Dependent Claim
26 words
A method as defined in claim 1 wherein the edges added in step (b) form an identical connection pattern in each of said blocks of nodes.
Claim 4
Independent Claim
191 words
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≦d'≦d; b) creating a respective block of 2 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 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.
Claim 5
Independent Claim
191 words
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≦d'≦d; b) creating a respective block of 2 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 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.
Claim 6
Dependent Claim
22 words
A method as defined in claim 3 wherein the edges added in step (c) correspond to those edges present in a block.
Claim 7
Dependent Claim
26 words
A method as defined in claim 3 wherein the edges added in step (c) comprise the edges present in a block and diagonal and anti-diagonal edges.
Claim 8
Dependent Claim
245 words
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 1 , S 2 , . . . , S d , where n, d, and d' are positive integers, where 1≦d'≦d, and where each S i , where 1≦i≦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 1 , x 2 , . . . , x d' ) in d'-cube j, where 0≦j≦n-1, is connected to node (x 1 , x 2 , . . . , x i-1 , complement (x i ), x i+1 , . . . , x d' ) in d'-cube (j+(2x i -1)s) mod n, where sεS i and 1≦i≦d', and (ii) wherein each node with d'-cube label (x 1 , x 2 , . . . , x d' ) in d'-cube j, where 0≦j≦n-1, is further connected to node (x 1 , x 2 , . . . , x d' ) in d'-cube (j+s) mod n, where sεS i and d'≦i≦d.
Claim 9
Dependent Claim
245 words
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 1 , S 2 , . . . , S d , where n, d, and d' are positive integers, where 1≦d'≦d, and where each S i , where 1≦i≦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 1 , x 2 , . . . , x d' ) in d'-cube j, where 0≦j≦n-1, is connected to node (x 1 , x 2 , . . . , x i-1 , complement (x i ), x i+1 , . . . , x d' ) in d'-cube (j+(2x i -1)s) mod n, where sεS i and 1≦i≦d', and (ii) wherein each node with d'-cube label (x 1 , x 2 , . . . , x d' ) in d'-cube j, where 0≦j≦n-1, is further connected to node (x 1 , x 2 , . . . , x d' ) in d'-cube (j+s) mod n, where sεS i and d'≦i≦d.
Claim 10
Dependent Claim
223 words
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.
Claim 11
Dependent Claim
223 words
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.
Claim 12
Dependent Claim
51 words
A computer program product as defined in claim 7 wherein the means for instructing to add edges within each said block of nodes includes means recorded on said recording medium for instructing said computer system to add edges which form an identical connection pattern in each of said blocks of nodes.
Claim 13
Dependent Claim
243 words
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≦d'≦d; c) means recorded on said recording medium for instructing said computer system to create a respective block of 2 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 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.
Claim 14
Dependent Claim
243 words
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≦d'≦d; c) means recorded on said recording medium for instructing said computer system to create a respective block of 2 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 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.
Claim 15
Dependent Claim
41 words
A computer program product as defined in claim 9 wherein the means d) for instructing to add edges includes means, recorded on said recording medium, for instructing aid computer system to add edges which correspond to edges present in a block.
Claim 16
Dependent Claim
45 words
A computer program product as defined in claim 9 wherein the means d) for instructing to add edges includes means, recorded on said recording medium, for instructing said computer system to add edges which comprise edges present in a block and diagonal and anti-diagonal edges.
References Cited (Backward Citations)
US4047163A
Cited
US4051354A
Cited
US4302819A
Cited
US4507726A
Cited
US4698807A
Cited
US4605928A
Cited
EP0190813A2
Cited
US5065308A
Cited
US4922408A
Cited
US4722084A
Cited
US4783782A
Cited
US4833635A
Cited
US4791603A
Cited
US4891810A
Cited
US4918662A
Cited
US5170482A
Cited
US4951220A
Cited
US4942517A
Cited
US4868818A
Cited
EP0398971A1
Cited
US4907232A
Cited
US4970724A
Cited
WO1990009635A1
Cited
US5072371A
Cited
GB2231985A
Cited
US5201044A
Cited
US5251131A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-30 | 1999-10-30 | 2000-04-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-30 | 2003-10-30 | 2004-04-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-30 | 2007-10-30 | 2008-04-30 | $7700.00 | Window Closed / Lapsed |