US5444701A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of packet routing in torus networks with two buffers per edge
Assignee: International Business Machines Corp
•
Filing: 1992-10-29
•
Granted: 1995-08-22
•
Expires: 2012-10-29
Abstract
Abstract A method is for routing packets in parallel computers with torus interconnection networks of arbitrary size and dimension having a plurality of nodes, each of which contains at least 2 buffers per edge incident to the node. For each packet which is being routed or which is being injected into the communication network, a waiting set is specified which consists of those buffers to which the packet can be transferred. The packet can be transferred to any buffer in its waiting set which has enough storage available to hold the packet. This waiting set is specified by first defining a set of nodes to which the packet is allowed to move and then defining a candidate set of buffers within the defined set of nodes. Then, defining an ordering of the nodes across the network from smallest to largest. The buffers in each node are then classified into four classes. After the buffers in each node have been classified, a set of rules for placing into the waiting set those classes of candidate buffers to which the packet can move is provided such that the routing method is free of deadlock, livelock, and starvation.
Inventors
- 👤 Robert E. Cypher
- 👤 Luis Gravano
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 14:48
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/06
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
94 words
A method for creating a waiting set for a packet in a toroidal interconnection network having a plurality of nodes, each of which contains a plurality of buffers per edge incident to the node, the method comprising the steps of: (a) defining a set of nodes to which the packet is allowed to move; (b) defining a candidate set of buffers within the defined set of nodes; (c) classifying the buffers into a plurality of classes; and (d) placing into the waiting set those classes of candidate buffers to which the packet can move.
Claim 2
Independent Claim
94 words
A method for creating a waiting set for a packet in a toroidal interconnection network having a plurality of nodes, each of which contains a plurality of buffers per edge incident to the node, the method comprising the steps of: (a) defining a set of nodes to which the packet is allowed to move; (b) defining a candidate set of buffers within the defined set of nodes; (c) classifying the buffers into a plurality of classes; and (d) placing into the waiting set those classes of candidate buffers to which the packet can move.
Claim 3
Dependent Claim
68 words
A method as defined in claim 1 wherein the set of nodes to which a packet is allowed to move comprises each node to y such that y is adjacent to x in the torus and there exists a minimal length path from x to the packer's destination node which contains the edge from x to y, wherein x is the node at which the packet is located.
Claim 4
Dependent Claim
46 words
A method as defined in claim 1 wherein the candidate set of buffers within the defined set of nodes comprises those buffers in the defined set of nodes which are associated with an edge which is incident to the node at which the packet is located.
Claim 5
Dependent Claim
25 words
A method as defined in claim 1 wherein the method further comprises the step of defining an ordering of the nodes from smallest to largest.
Claim 6
Dependent Claim
32 words
A method as defined in claim 4 wherein the step of classifying the buffers into a plurality of classes further comprises the step of designating a first, second, third, and fourth class.
Claim 7
Dependent Claim
54 words
A method as defined in claim 5 wherein the step of classifying the buffers further comprises the step of: (1) associating buffers of the first and third classes with each edge which connects to a node that is larger in the defined ordering than the node containing the first and third classes of buffers.
Claim 8
Dependent Claim
54 words
A method as defined in claim 5 wherein the step of classifying the buffers further comprises the step of: (1) associating buffers of the second and fourth classes with each edge which connects to a node that is smaller in the defined ordering than the node containing the second and fourth classes of buffers.
Claim 9
Dependent Claim
54 words
A method as defined in claim 5 wherein the step of classifying the buffers further comprises the step of: (1) associating buffers of the second and fourth classes with each edge which connects to a node that is smaller in the defined ordering than the node containing the second and fourth classes of buffers.
Claim 10
Dependent Claim
20 words
A method as defined in claim 4 wherein the defined ordering of the nodes from smallest to largest is inside-increasing.
Claim 11
Dependent Claim
83 words
A method as defined in claim 9 wherein the inside-increasing ordering of the nodes is defined as the value given to the node (a d-1 , a d-2 , . . . , a 0 ) by the function Inside, wherein Inside(a.sub.d-1, a.sub.d-2, . . . , a.sub.0)=Eval(ƒ.sub.I (a.sub.d-1, n.sub.d-1), ƒ.sub.I (a.sub.d-2 , n.sub.d-2), . . . , ƒ.sub.I (a.sub.0,n.sub.0)), and wherein ##EQU15## and wherein ##EQU16## and wherein ##EQU17## and wherein n j is the length of the jth dimension of the torus.
Claim 12
Dependent Claim
92 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet can move comprises the additional step of placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) at least one of the nodes in the defined set of nodes is larger than the node at which the packet is being injected into the network.
Claim 13
Dependent Claim
92 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet can move comprises the additional step of placing into the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first or second class buffer; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node currently containing the buffer in which the packet resides.
Claim 14
Dependent Claim
92 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet can move comprises the additional step of placing in the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node at which the packet is being injected into the network.
Claim 15
Dependent Claim
94 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet; can move comprises the additional step of placing into the waiting set the second and third classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) at least one of the nodes in the defined set of nodes is smaller in the defined ordering than the node currently containing the buffet in which the packet resides.
Claim 16
Dependent Claim
90 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet can move comprises the additional step of placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) all of the nodes in the defined set of nodes are larger in the defined ordering than the node currently containing the buffer in which the packet resides.
Claim 17
Dependent Claim
59 words
A method as defined in claim 5 wherein the step of placing into the waiting set those classes of buffers to which the packet can move comprises the additional step of placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that the packet is currently in a fourth class buffer.
Claim 18
Independent Claim
571 words
A method for creating a waiting set for a packet in a toroidal interconnection network having a plurality of nodes, each of which contains a plurality of buffers per edge incident to the node, the method comprising the steps of: (a) defining a set of nodes to which the packet is allowed to move; (b) defining a candidate set of buffers within the defined set of nodes; (c) defining an ordering of the nodes from smallest to largest; (d) classifying the buffers into first, second, third, and fourth classes comprising the steps of: (1) associating buffers of the first and third classes with each edge which connects to a node that is larger in the defined ordering than the node containing the first and third classes of buffers; and (2) associating buffers of the second and fourth classes with each edge which connects to a node that is smaller in the defined ordering than the node containing the second and fourth classes of buffers, (e) placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first or second class buffer; and (2) at least one of the nodes in the defined set of nodes is larger in the defined ordering than the node currently containing the buffer in which the packet resides; (f) placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) at least one of the nodes in the defined set of nodes is larger than the node at which the packet is being injected into the network; (g) placing into the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first or second class buffer; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node currently containing the buffer in which the packet resides; (h) placing in the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node at which the packet is being injected into the network; (i) placing into the waiting set the second and third classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) at least one of the nodes in the defined set of nodes is smaller in the defined ordering than the node currently containing the buffer in which the packet resides; (j) placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) all of the nodes in the defined set of nodes are larger in the defined ordering than the node currently containing the buffer in which the packet resides; and (k) placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a fourth class buffer.
Claim 19
Independent Claim
571 words
A method for creating a waiting set for a packet in a toroidal interconnection network having a plurality of nodes, each of which contains a plurality of buffers per edge incident to the node, the method comprising the steps of: (a) defining a set of nodes to which the packet is allowed to move; (b) defining a candidate set of buffers within the defined set of nodes; (c) defining an ordering of the nodes from smallest to largest; (d) classifying the buffers into first, second, third, and fourth classes comprising the steps of: (1) associating buffers of the first and third classes with each edge which connects to a node that is larger in the defined ordering than the node containing the first and third classes of buffers; and (2) associating buffers of the second and fourth classes with each edge which connects to a node that is smaller in the defined ordering than the node containing the second and fourth classes of buffers, (e) placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first or second class buffer; and (2) at least one of the nodes in the defined set of nodes is larger in the defined ordering than the node currently containing the buffer in which the packet resides; (f) placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) at least one of the nodes in the defined set of nodes is larger than the node at which the packet is being injected into the network; (g) placing into the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first or second class buffer; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node currently containing the buffer in which the packet resides; (h) placing in the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node at which the packet is being injected into the network; (i) placing into the waiting set the second and third classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) at least one of the nodes in the defined set of nodes is smaller in the defined ordering than the node currently containing the buffer in which the packet resides; (j) placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) all of the nodes in the defined set of nodes are larger in the defined ordering than the node currently containing the buffer in which the packet resides; and (k) placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a fourth class buffer.
Claim 20
Dependent Claim
67 words
A method as defined in claim 17 wherein the set of nodes to which a packet is allowed to move comprises each node y such that y is adjacent to x in the torus and there exists a minimal length path From x to the packer's destination node which contains the edge from x to y, wherein x is the node at which the packet is located.
Claim 21
Dependent Claim
46 words
A method as defined in claim 17 wherein the candidate set of buffers within the defined set of nodes comprises those buffers in the defined set of nodes which are associated with an edge which is incident to the node at which the packet is located.
Claim 22
Independent Claim
20 words
A method as defined in claim. 17 wherein the defined ordering of the nodes from smallest to largest is inside-increasing.
Claim 23
Dependent Claim
83 words
A method as defined in claim 20 wherein the inside-increasing ordering of the nodes is defined as the value given to the node (a d-1 , a d-2 , . . . , a 0 ) by the function Inside, wherein Inside(a.sub.d-1, a.sub.d-2, . . . , a.sub.0)=Eval(ƒ.sub.I (a.sub.d-1, n.sub.d-1), ƒ.sub.I (a.sub.d-2 , n.sub.d-2), . . . , ƒ.sub.I (a.sub.0,n.sub.0)), and wherein ##EQU18## and wherein ##EQU19## and wherein ##EQU20## and wherein n j is the length of the jth dimension of the torus.
Claim 24
Dependent Claim
99 words
A toroidal interconnection network for use in creating a wait set for a data packet, comprising a plurality of nodes interconnected in a selected configuration, wherein each node contains a processor and a plurality of buffers per edge incident to the node, processors being programmed to perform method steps comprising: defining set of nodes to which the packet is allowed to move; defining a candidate set of buffers within the defined set of nodes; classifying the buffers into a plurality of classes; and placing into the waiting set those classes of candidate buffers to which the packet can move.
Claim 25
Dependent Claim
99 words
A toroidal interconnection network for use in creating a wait set for a data packet, comprising a plurality of nodes interconnected in a selected configuration, wherein each node contains a processor and a plurality of buffers per edge incident to the node, processors being programmed to perform method steps comprising: defining set of nodes to which the packet is allowed to move; defining a candidate set of buffers within the defined set of nodes; classifying the buffers into a plurality of classes; and placing into the waiting set those classes of candidate buffers to which the packet can move.
Claim 26
Dependent Claim
28 words
A network as defined in claim 22, wherein the processors are further programmed to perform method steps of defining an ordering of the nodes from smallest to largest.
Claim 27
Dependent Claim
39 words
A network as defined in claim 23 wherein the processors are programmed such that the method step of classifying the buffers into a plurality of classes further comprises a step of designating a first, second, third, and fourth class.
Claim 28
Dependent Claim
60 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of classifying the buffers further comprises a step of associating buffers of the first and third classes with each edge which connects to a node that is larger in the defined ordering than the node containing the first and third classes of buffers.
Claim 29
Dependent Claim
60 words
A network as defined in claim 24 wherein the processors are performed such that the method step of classifying the buffers further comprises a step of associating buffers of the second and fourth classes with each edge which connects to a node that is smaller in the defined ordering than the node containing the second and fourth classes of buffers.
Claim 30
Dependent Claim
98 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing into the waiting set the first and second classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) at least one of the nodes in the defined set of nodes is larger than the node at which the packet is being injected into the network.
Claim 31
Dependent Claim
98 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing into the waiting set the third class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a first and second class buffer; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node currently containing the buffer in which the packet resides.
Claim 32
Dependent Claim
98 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing in the waiting set the third classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently being injected into the toroidal network; and (2) all of the nodes in the defined set of nodes are smaller in the defined ordering than the node at which the packet is being injected into the network.
Claim 33
Dependent Claim
100 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing into the waiting set the second and third classes of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) at least one of the nodes in the defined set of nodes is smaller in the defined ordering than the node currently containing the buffer in which the packet resides.
Claim 34
Dependent Claim
96 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that: (1) the packet is currently in a third class buffer; and (2) all of the nodes in the defined set of nodes are larger in the defined ordering than the node currently containing the buffer in which the packet resides.
Claim 35
Dependent Claim
65 words
A network as defined in claim 24 wherein the processors are programmed such that the method step of placing into the waiting set those classes of buffers to which the packet can move includes a step of placing into the waiting set the fourth class of buffers contained in the candidate set of buffers provided that the packet is currently in a fourth class buffer.
References Cited (Backward Citations)
US5008815A
Cited
US4805091A
Cited
US4742511A
Cited
US4814980A
Cited
US4933933A
Cited
US4984235A
Cited
US5105424A
Cited
GB2227341A
Cited
US5157692A
Cited
EP0460599B1
Cited
US5151900A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-21 | 1999-02-20 | 1999-08-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-21 | 2003-02-20 | 2003-08-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-21 | 2007-02-20 | 2007-08-22 | $7700.00 | Window Closed / Lapsed |