Adaptive routing mechanism for torus interconnection network
First Claim
1. 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.
18 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
-
20. 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.
-
-
21. 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.
-
-
22. 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.
-
Specification