Method of packet routing in torus networks with two buffers per edge

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.

What is claimed and desired to be secured by United States Letters Patent is: 
     
       1. 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.   
     
     
       2. 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. 
     
     
       3. 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. 
     
     
       4. 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. 
     
     
       5. 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. 
     
     
       6. 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.   
     
     
       7. 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.   
     
     
       8. 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.   
     
     
       9. A method as defined in claim 4 wherein the defined ordering of the nodes from smallest to largest is inside-increasing. 
     
     
       10. 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.   
     
     
       11. 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.   
     
     
       12. 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.   
     
     
       13. 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.   
     
     
       14. 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.   
     
     
       15. 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.   
     
     
       16. 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. 
     
     
       17. 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.     
     
     
       18. 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. 
     
     
       19. 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. 
     
     
       20. A method as defined in claim. 17 wherein the defined ordering of the nodes from smallest to largest is inside-increasing. 
     
     
       21. 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.   
     
     
       22. 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.   
     
     
       23. 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. 
     
     
       24. 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. 
     
     
       25. 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. 
     
     
       26. 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. 
     
     
       27. 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.   
     
     
       28. 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.   
     
     
       29. 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.   
     
     
       30. 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.   
     
     
       31. 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.   
     
     
       32. 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.