US5701416A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive routing mechanism for torus interconnection network
Assignee: Morgan Stanley and Co LLC
•
Filing: 1995-04-13
•
Granted: 1997-12-23
•
Expires: 2015-04-13
Abstract
Abstract A routing mechanism includes two acyclic non-adaptive virtual channels having two types of virtual channel buffers to store packets along deterministic virtual paths between nodes in an n-dimensional networked system, and an adaptive virtual channel having a third type of virtual channel buffer to store the packets along non-deterministic virtual paths between the nodes. The packets are routed between the nodes along either selected portions of the deterministic virtual paths or selected portions of the non-deterministic virtual paths based on routing information such that a packet is never routed on a selected portion of one of the non-deterministic virtual paths unless the third type virtual channel buffer associated with the selected portion of the one non-deterministic virtual path has sufficient space available to store the entire packet.
Inventors
- 👤 Gregory M. Thorson
- 👤 Steven L. Scott
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 22:20
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17306; G06F15/17331; G06F15/17356; G06F15/17368; G06F15/17381
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
275 words
A method of routing a packet between a source node and a destination node in a networked system comprising a plurality of nodes and physical communication links interconnecting the nodes in an n-dimensional topology, the method comprising: generating a header including routing information; attaching the header to information to be transferred in order to form a packet; defining two acyclic non-adaptive virtual channels utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a deterministic virtual path from the source node to the destination node based on the routing information; defining an adaptive virtual channel utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a plurality of non-deterministic virtual paths from the source node to the destination node based on the routing information; selecting either a portion of the deterministic virtual path from the source node to an adjacent node along the deterministic virtual path or a portion of one of the non-deterministic virtual paths from the source node to an adjacent node along the one non-deterministic virtual path based on the routing information, wherein the portion of the one non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of the one non-deterministic virtual path has sufficient space available to store the entire packet; routing the packet from the source node to the adjacent node along the portion of the selected virtual path; and continuing to select virtual paths at each node from the source to the destination node and to route the packet on the selected virtual paths until the packet reaches the destination node.
Claim 2
Independent Claim
275 words
A method of routing a packet between a source node and a destination node in a networked system comprising a plurality of nodes and physical communication links interconnecting the nodes in an n-dimensional topology, the method comprising: generating a header including routing information; attaching the header to information to be transferred in order to form a packet; defining two acyclic non-adaptive virtual channels utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a deterministic virtual path from the source node to the destination node based on the routing information; defining an adaptive virtual channel utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a plurality of non-deterministic virtual paths from the source node to the destination node based on the routing information; selecting either a portion of the deterministic virtual path from the source node to an adjacent node along the deterministic virtual path or a portion of one of the non-deterministic virtual paths from the source node to an adjacent node along the one non-deterministic virtual path based on the routing information, wherein the portion of the one non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of the one non-deterministic virtual path has sufficient space available to store the entire packet; routing the packet from the source node to the adjacent node along the portion of the selected virtual path; and continuing to select virtual paths at each node from the source to the destination node and to route the packet on the selected virtual paths until the packet reaches the destination node.
Claim 3
Dependent Claim
38 words
The method of claim 1 further comprising the step of defining a direction order for routing packets, wherein the direction order defines a priority for routing the packets in each of 2n directions along the deterministic virtual path.
Claim 4
Dependent Claim
30 words
The method of claim 2 wherein the one non-deterministic virtual path is pre-selected for routing in the lowest priority direction of the 2n directions that is not blocked or disabled.
Claim 5
Dependent Claim
149 words
The method of claim 1 wherein the step of selecting a path for routing comprises the steps of: pre-selecting the one non-deterministic virtual path; requesting both the portion of the pre-selected non-deterministic virtual path and the portion of the deterministic virtual path for routing of the packet; granting or denying access to the physical communication links in response to said requests and other competing requests for the physical communication links, wherein if an adaptive virtual channel and a non-adaptive virtual channel are both requesting access of a physical communication link the non-adaptive virtual channel is granted access to the physical communication link; selecting the portion of a granted virtual path if at least one of said requests is granted, wherein the portion of the one non-deterministic virtual path is selected if both of said requests are granted; and retrying the requesting step if neither of said requests are granted.
Claim 6
Dependent Claim
63 words
The method of claim 1 wherein the method routes multiple packets between the plurality of nodes, and wherein the method further comprising the steps of: determining order dependent groups of packets which are required to arrive at the destination node in a pre-determined order; and selecting only the deterministic virtual paths for routing packets which are in an order dependent group of packets.
Claim 7
Dependent Claim
49 words
The method of claim 1 wherein the information to be transferred includes request and response information, and wherein the step of defining acyclic non-adaptive virtual channels includes defining two acyclic non-adaptive virtual channels for handling the request information and two acyclic non-adaptive virtual channels for handling the response information.
Claim 8
Dependent Claim
27 words
The method of claim 1 further comprising sending the packet in a free hop from the source node to an adjacent node prior to the selecting step.
Claim 9
Dependent Claim
57 words
The method of claim 7 wherein the n-dimensional topology comprises physical communication lines connecting nodes in 2n directions including first and second directions in each dimension, and wherein the step of sending the packet in a free hop from the source node to an adjacent node comprises sending the packet in any one of the first directions.
Claim 10
Dependent Claim
37 words
The method of claim 1 wherein the step of transferring the packet further comprises sending the packet on a final hop from a node adjacent to the destination node to complete the route to the destination node.
Claim 11
Dependent Claim
16 words
The method of claim 9 wherein the final hop is taken based on the routing information.
Claim 12
Dependent Claim
21 words
The method of claim 9 wherein the final hop is limited to a single direction in one of the n dimensions.
Claim 13
Independent Claim
336 words
A method of routing a packet between a source node and a destination node in a networked system comprising a plurality of nodes and physical communication links interconnecting the nodes in an n-dimensional topology, the method comprising: generating a header including routing information; attaching the header to information to be transferred in order to form a packet; defining two acyclic non-adaptive virtual channels utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a deterministic virtual path from the source node to the destination node based on the routing information; defining an adaptive virtual channel utilizing the third type of virtual channel buffers to store the packet along a plurality of non-deterministic virtual paths from the source node to the destination node based on the routing information; selecting either a portion of the deterministic virtual path from the source node to an adjacent node along the deterministic virtual path or a portion of one of the non-deterministic virtual paths from the source node to an adjacent node along the one non-deterministic virtual path based on the routing information, wherein the portion of the one non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of the one non-deterministic virtual path is empty; routing the packet from the source node to the adjacent node along the portion of the selected virtual path; if a packet is routed to the portion of the one non-deterministic virtual path, recording a direction and a deterministic virtual path the packet is on as the packet enters the portion of the one non-deterministic virtual path, and when the packet reenters the deterministic virtual path continue routing the packet in the recorded direction on the recorded deterministic virtual path if all transfers in the recorded direction are not completed; and continuing to select virtual paths at each node from the source to the destination node and to route the packet on the selected virtual paths until the packet reaches the destination node.
Claim 14
Independent Claim
336 words
A method of routing a packet between a source node and a destination node in a networked system comprising a plurality of nodes and physical communication links interconnecting the nodes in an n-dimensional topology, the method comprising: generating a header including routing information; attaching the header to information to be transferred in order to form a packet; defining two acyclic non-adaptive virtual channels utilizing associated virtual channel buffers assigned to the physical communication links to store the packet along a deterministic virtual path from the source node to the destination node based on the routing information; defining an adaptive virtual channel utilizing the third type of virtual channel buffers to store the packet along a plurality of non-deterministic virtual paths from the source node to the destination node based on the routing information; selecting either a portion of the deterministic virtual path from the source node to an adjacent node along the deterministic virtual path or a portion of one of the non-deterministic virtual paths from the source node to an adjacent node along the one non-deterministic virtual path based on the routing information, wherein the portion of the one non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of the one non-deterministic virtual path is empty; routing the packet from the source node to the adjacent node along the portion of the selected virtual path; if a packet is routed to the portion of the one non-deterministic virtual path, recording a direction and a deterministic virtual path the packet is on as the packet enters the portion of the one non-deterministic virtual path, and when the packet reenters the deterministic virtual path continue routing the packet in the recorded direction on the recorded deterministic virtual path if all transfers in the recorded direction are not completed; and continuing to select virtual paths at each node from the source to the destination node and to route the packet on the selected virtual paths until the packet reaches the destination node.
Claim 15
Dependent Claim
38 words
The method of claim 12 further comprising the step of defining a direction order for routing packets, wherein the direction order defines a priority for routing the packets in each of 2n directions along the deterministic virtual path.
Claim 16
Dependent Claim
30 words
The method of claim 12 wherein the one non-deterministic virtual path is pre-selected for routing in the lowest priority direction of the 2n directions that is not blocked or disabled.
Claim 17
Dependent Claim
149 words
The method of claim 12 wherein the step of selecting a path for routing comprises the steps of: pre-selecting the one non-deterministic virtual path; requesting both the portion of the pre-selected non-deterministic virtual path and the portion of the deterministic virtual path for routing of the packet; granting or denying access to the physical communication links in response to said requests and other competing requests for the physical communication links, wherein if an adaptive virtual channel and a non-adaptive virtual channel are both requesting access of a physical communication link the non-adaptive virtual channel is granted access to the physical communication link; selecting the portion of a granted virtual path if at least one of said requests is granted, wherein the portion of the one non-deterministic virtual path is selected if both of said requests are granted; and retrying the requesting step if neither of said requests are granted.
Claim 18
Dependent Claim
63 words
The method of claim 12 wherein the method routes multiple packets between the plurality of nodes, and wherein the method further comprising the steps of: determining order dependent groups of packets which are required to arrive at the destination node in a pre-determined order; and selecting only the deterministic virtual paths for routing packets which are in an order dependent group of packets.
Claim 19
Dependent Claim
49 words
The method of claim 12 wherein the information to be transferred includes request and response information, and wherein the step of defining acyclic non-adaptive virtual channels includes defining two acyclic non-adaptive virtual channels for handling the request information and two acyclic non-adaptive virtual channels for handling the response information.
Claim 20
Dependent Claim
27 words
The method of claim 12 further comprising sending the packet in a free hop from the source node to an adjacent node prior to the selecting step.
Claim 21
Dependent Claim
37 words
The method of claim 12 wherein the step of transferring the packet further comprises sending the packet on a final hop from a node adjacent to the destination node to complete the route to the destination node.
Claim 22
Dependent Claim
216 words
A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; means for generating headers having routing information; means for attaching the headers to information to be transferred between the processing element nodes in order to form packets; two acyclic non-adaptive virtual channels having virtual channel buffers assigned to each physical communication link to store the packets along deterministic virtual paths between the plurality of processing element nodes based on the routing information; an adaptive virtual channel having virtual channel buffers assigned to each physical communication link to store the packets along non-deterministic virtual paths between the plurality of processing element nodes based on the routing information; means for selecting either a portion of a deterministic virtual path between two processing element nodes along said deterministic virtual path or a portion of a non-deterministic virtual path between two processing element nodes along said non-deterministic virtual path based on the routing information, wherein the portion of said non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of said non-deterministic virtual path has sufficient space available to store an entire packet; and means for routing the packets between the processing element nodes along the selected portions of said virtual paths.
Claim 23
Dependent Claim
216 words
A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; means for generating headers having routing information; means for attaching the headers to information to be transferred between the processing element nodes in order to form packets; two acyclic non-adaptive virtual channels having virtual channel buffers assigned to each physical communication link to store the packets along deterministic virtual paths between the plurality of processing element nodes based on the routing information; an adaptive virtual channel having virtual channel buffers assigned to each physical communication link to store the packets along non-deterministic virtual paths between the plurality of processing element nodes based on the routing information; means for selecting either a portion of a deterministic virtual path between two processing element nodes along said deterministic virtual path or a portion of a non-deterministic virtual path between two processing element nodes along said non-deterministic virtual path based on the routing information, wherein the portion of said non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of said non-deterministic virtual path has sufficient space available to store an entire packet; and means for routing the packets between the processing element nodes along the selected portions of said virtual paths.
Claim 24
Dependent Claim
277 words
A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; means for generating headers having routing information; means for attaching the headers to information to be transferred between the processing element nodes in order to form packets; two acyclic non-adaptive virtual channels having virtual channel buffers assigned to each physical communication link to store the packets along deterministic virtual paths between the plurality of processing element nodes based on the routing information; an adaptive virtual channel having virtual channel buffers assigned to each physical communication link to store the packets along non-deterministic virtual paths between the plurality of processing element nodes based on the routing information; means for selecting either a portion of a deterministic virtual path between two processing element nodes along said deterministic virtual path or a portion of a non-deterministic virtual path between two processing element nodes along said non-deterministic virtual path based on the routing information, wherein the portion of said non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of said non-deterministic virtual path is empty; means for routing the packets between the processing element nodes along the selected portions of said virtual paths including means for recording a direction and a deterministic virtual path which a packet is on when the packet enters the portion of said non-deterministic virtual path, and means for routing the packet in the recorded direction on the recorded deterministic virtual path if all transfers in the recorded direction are not completed when the packet reenters the deterministic virtual path from the portion of said non-deterministic virtual path.
Claim 25
Dependent Claim
277 words
A multiprocessor computer system comprising: a plurality of processing element nodes; physical communication links interconnecting the processing element nodes in an n-dimensional topology; means for generating headers having routing information; means for attaching the headers to information to be transferred between the processing element nodes in order to form packets; two acyclic non-adaptive virtual channels having virtual channel buffers assigned to each physical communication link to store the packets along deterministic virtual paths between the plurality of processing element nodes based on the routing information; an adaptive virtual channel having virtual channel buffers assigned to each physical communication link to store the packets along non-deterministic virtual paths between the plurality of processing element nodes based on the routing information; means for selecting either a portion of a deterministic virtual path between two processing element nodes along said deterministic virtual path or a portion of a non-deterministic virtual path between two processing element nodes along said non-deterministic virtual path based on the routing information, wherein the portion of said non-deterministic virtual path is not selected unless the virtual channel buffer associated with the portion of said non-deterministic virtual path is empty; means for routing the packets between the processing element nodes along the selected portions of said virtual paths including means for recording a direction and a deterministic virtual path which a packet is on when the packet enters the portion of said non-deterministic virtual path, and means for routing the packet in the recorded direction on the recorded deterministic virtual path if all transfers in the recorded direction are not completed when the packet reenters the deterministic virtual path from the portion of said non-deterministic virtual path.
Claim 26
Dependent Claim
128 words
A routing mechanism for routing packets coming information to be transferred between nodes in an n-dimensional networked system, the routing mechanism comprising: two acyclic non-adaptive virtual channels having virtual channel buffers to store the packets along deterministic virtual paths between the nodes; an adaptive virtual channel having virtual channel buffers to store the packets along non-deterministic virtual paths between the nodes; means for routing the packets between the nodes along either selected portions of the deterministic virtual paths or selected portions of the non-deterministic virtual paths, wherein a packet is never routed on a selected portion of one of the non-deterministic virtual paths unless the virtual channel buffer associated with the selected portion of the one non-deterministic virtual path has sufficient space available to store the entire packet.
Claim 27
Dependent Claim
128 words
A routing mechanism for routing packets coming information to be transferred between nodes in an n-dimensional networked system, the routing mechanism comprising: two acyclic non-adaptive virtual channels having virtual channel buffers to store the packets along deterministic virtual paths between the nodes; an adaptive virtual channel having virtual channel buffers to store the packets along non-deterministic virtual paths between the nodes; means for routing the packets between the nodes along either selected portions of the deterministic virtual paths or selected portions of the non-deterministic virtual paths, wherein a packet is never routed on a selected portion of one of the non-deterministic virtual paths unless the virtual channel buffer associated with the selected portion of the one non-deterministic virtual path has sufficient space available to store the entire packet.
References Cited (Backward Citations)
USRE28577E
Cited
EP0501524A2
Cited
US5341504A
Cited
US4771391A
Cited
US4933933A
Cited
WO1988008652A1
Cited
US5170482A
Cited
US5008882A
Cited
US4868818A
Cited
US5105424A
Cited
US5347450A
Cited
US5031211A
Cited
US5157692A
Cited
US5218601A
Cited
US5280474A
Cited
US5218676A
Cited
US5331631A
Cited
US5239545A
Cited
US5175733A
Cited
US5313645A
Cited
US5555542A
Cited
US5517497A
Cited
US5550589A
Cited
US5548639A
Cited
US5313628A
Cited
EP0570729A2
Cited
US5333279A
Cited
US5440547A
Cited
US5353283A
Cited
US5546549A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-22 | 2001-06-23 | 2001-12-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-22 | 2005-06-23 | 2005-12-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-22 | 2009-06-23 | 2009-12-23 | $7700.00 | Window Closed / Lapsed |