Route prediction in packet switched networks
Communicating among nodes in a network includes: sending a packet from an origin node to a destination node over a route including plural nodes. At each node in the route, routing of the packet is initiated according to a predicted path concurrently with verifying the correctness of the predicted path based on analyzing route information in the packet. In response to results of verifying the correctness of the predicted path, the routing of the packet is completed according to the predicted path or initiating a routing of the packet according to an actual path based on the route information in the packet.
1. A method for communicating among nodes in a network, the method comprising:
sending a packet from an origin node to a destination node over a route including plural nodes according to a routing scheme, by:
at each node in the route,
predicting a switch output port for a predicted path that is a most likely path for the packet according to the routing scheme;
initiating routing of the packet to the predicted output port by preparing to couple the packet from a switch input port to the predicted output port;
verifying concurrently with initiating the correctness of the predicted path based on analyzing route information in the packet; and
in response to results of verifying the correctness of the predicted path, completing the routing of the packet by coupling the packet to an output port of the switch according to the predicted path or initiating a routing of the packet according to an actual path based on the route information in the packet.
2. The method of claim 1 , wherein the predicted output port of the switch is related to the input port of the switch according to the predicted path.
3. The method of claim 2 , wherein preparing to couple the packet comprises providing control signals to a multiplexer in the switch of the node at which the packet arrives.
4. The method of claim 2 , wherein the network comprises a two-dimensional mesh network in which each of multiple nodes is connected to four neighboring nodes, and the predicted path is straight along one of the dimensions, and the predicted output port is related to the input port to route the packet over a straight path through the node at which the packet arrives.
5. The method of claim 4 , wherein the route including one or more nodes comprises a route including multiple nodes that is dimension ordered such that all hops along the route in a first dimension occur before any hops along the route in a second dimension occur.
6. The method of claim 1 , wherein the predicted path is stored in a given node and is used for multiple packets received at the given node.
7. The method of claim 1 , wherein the predicted path for a given packet received at a given node is chosen based on past performance of predicted paths chosen for previous packets received at the given node.
8. The method of claim 1 , wherein the nodes in the network comprise cores in a computing system, with each core comprising a processor and a switch.
9. The method of claim 1 , wherein verifying the correctness of the predicted path based on analyzing route information in the packet comprises calculating the actual path based on the route information in the packet and comparing the predicted path to the actual path.
10. The method of claim 1 , wherein verifying the correctness of the predicted path based on analyzing route information in the packet comprises a verification procedure that is faster than calculating the actual path.
11. The method of claim 1 , wherein the route information comprises an address of the destination node.
12. A computer-readable storage device storing a computer program for communicating among nodes in a computing system, the computer program including instructions for causing the computing system to:
send a packet from an origin node to a destination node over a route including plural nodes according to a routing scheme, by:
at each node in the route,
predict a switch output port for a predicted path that is a most likely path for the packet according to the routing scheme;
initiate routing of the packet to the predicted output port according to the predicted path;
verify concurrently with initiate routing, the correctness of the predicted path based on analyzing route information in the packet; and
in response to results of verifying the correctness of the predicted path, complete the routing of the packet according to the predicted path to the predicted output port or initiate a routing of the packet according to an actual path based on the route information in the packet.
13. A computing system, comprising:
a plurality of cores;
each of one or more of the cores comprising a switch; and
each of one or more of the cores comprising a processor, the processors configured to:
send a packet from an origin core to a destination core over a route including plural cores according to a routing scheme, by:
at each core in the route,
predict a switch output port for a predicted path that is a most likely path for the packet according to the routing scheme;
initiate routing of the packet to the predicted output port according to the predicted path;
verify concurrently with initiate routing, the correctness of the predicted path based on analyzing route information in the packet; and
in response to results of verifying the correctness of the predicted path, complete the routing of the packet to the predicted output port according to the predicted path or initiating a routing of the packet according to an actual path based on the route information in the packet.
14. The device of claim 12 , wherein instructions to initiate routing of the packet according to the predicted path comprise instructions to prepare to couple the packet from an input port of a switch in a node at which the packet arrives to a predicted output port of the switch that is related to the input port of the switch according to the predicted path.
15. The device of claim 14 , wherein instructions to prepare to couple the packet comprise instructions to provide control signals to a multiplexer in the switch of the node at which the packet arrives.
16. The device of claim 12 , wherein instructions to predict, predict a route over the network that comprises a two-dimensional mesh network in which each of multiple nodes is connected to four neighboring nodes, and the predicted path is straight along one of the dimensions, and the predicted output port is related to the input port to route the packet over a straight path through the node at which the packet arrives.
17. The device of claim 16 , wherein instructions to predict the route, predict for a route that includes one or more nodes comprising the route that includes multiple nodes that is dimension ordered such that all hops along the route in a first dimension occur before any hops along the route in a second dimension occur.
18. The device of claim 12 , wherein instructions cause the predicted path to be stored in a node for multiple packets received at the node.
19. The device of claim 12 , wherein the predicted path for a packet received at a node is determined based on past performance of predicted paths chosen for previous packets received at the node.
20. The device of claim 12 , wherein the instructions to predict, predict for nodes in the network, which comprise cores in a computing system, with each core comprising a processor and a switch.
21. The device of claim 12 , wherein the instructions to verify the correctness of the predicted path based on analyzing route information in the packet comprise instructions to:
calculate the actual path based on the route information in the packet; and
compare the predicted path to the actual path.
22. The device of claim 12 , wherein the instructions to verify the correctness of the predicted path based on analyzing route information in the packet comprise instructions to:
apply a verification procedure that is faster than calculating the actual path.
23. The device of claim 12 , wherein the route information comprises an address of the destination node.
24. The system of claim 13 , wherein instructions to initiate routing of the packet according to the predicted path comprise instructions to prepare to couple the packet from an input port of a switch in a node at which the packet arrives to a predicted output port of the switch that is related to the input port of the switch according to the predicted path.
25. The system of claim 13 , wherein instructions to prepare to couple the packet comprise instructions to provide control signals to a multiplexer in the switch of the node at which the packet arrives.
26. The system of claim 13 , wherein the processors are further configured to predict a route over a network that comprises a two-dimensional mesh network in which each of multiple nodes is connected to four neighboring nodes, and the predicted path is straight along one of the dimensions, and the predicted output port is related to the input port to route the packet over a straight path through the node at which the packet arrives.
27. The system of claim 26 , wherein the processors are further configured to predict the route, which includes one or more nodes comprising the route that includes multiple nodes that is dimension ordered such that all hops along the route in a first dimension occur before any hops along the route in a second dimension occur.
28. The system of claim 13 , wherein the processors are further configured to cause the predicted path to be stored in a node for multiple packets received at the node.
29. The system of claim 13 , wherein the predicted path for a packet received at a node is determined based on past performance of predicted paths chosen for previous packets received at the node.
30. The system of claim 13 , wherein the processors are further configured to predict, predict for nodes in the network, which comprise cores in a computing system, with each core comprising a processor and a switch.
31. The system of claim 13 , wherein the processors are further configured to verify the correctness of the predicted path based on analyzing route information in the packet by:
calculating the actual path based on the route information in the packet; and
comparing the predicted path to the actual path.
32. The system of claim 13 , wherein the processors are further configured to verify the correctness of the predicted path based on analyzing route information in the packet, by:
applying a verification procedure that is faster than calculating the actual path.
33. The system of claim 13 , wherein the route information comprises an address of the destination node.