Adaptive routing mechanism for torus interconnection network

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.

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.

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.