Deadlock prevention in direct networks of arbitrary topology
Aspects of the invention pertain to routing packets in a computer system while avoiding deadlock. A turn rule is set according to unique identifiers associated with switches in the system. Numeric values of switches in possible turns are compared to determine whether a turn is permissible. The rule applies to all nodes in the system. The rule may be violated when using virtual channels. Here, a violation is permissible when using monotonically increasing virtual channel numbers or monotonically decreasing virtual channel numbers. Alternatively, the violations of the turn rule may be allowed if they force a packet to change to a later virtual channel in some fixed ordering of virtual channels. Deadlock can thus be avoided in many different types of architectures, including mesh, torus, butterfly and flattened butterfly configurations.
1. A method of routing packets in a computer network to avoid deadlock, the method comprising:
setting a turn rule for routing packets across the computer network, the turn rule prohibiting sending packets from a first switch (A) to a second switch (C) via an intermediate switch (B) given a selected condition, the condition being selected from the group consisting of:
a distinct identifier of intermediate switch B has a value greater than values of distinct identifiers of both first switch A and second switch C, or
the distinct identifier of intermediate switch B has a value less than the values of the distinct identifiers of both first switch A and second switch C; and
providing the turn rule to each of the first switch A, second switch C and intermediate switch B for routing the packets across the computer network according to the turn rule.
2. The method of claim 1 , wherein one or more of the first switch A, second switch C and intermediate switch B are configured for adaptive routing.
3. The method of claim 1 , wherein one or more of the first switch A, second switch C and intermediate switch B maintain multiple routing tables.
4. The method of claim 1 , further comprising assigning the distinct identifier to first switch A, second switch C and intermediate switch B, wherein the distinct identifier of each respective switch is a hash of a hardware identifier.
5. The method of claim 1 , wherein the method further comprises:
supporting a plurality of virtual channels in first switch A, second switch C and intermediate switch B;
determining whether the turn rule would be violated given the selected condition;
setting a virtual channel rule that permits violation of the turn rule by selecting a unique ordering of the plurality of virtual channels; and
routing the packets across the computer network according to the virtual channel rule.
6. The method of claim 1 , wherein the method further comprises:
supporting a plurality of virtual channels in first switch A, second switch C and intermediate switch B;
determining whether the turn rule would be violated given the selected condition; and
setting a virtual channel rule that permits violation of the turn rule if one and only one of the following conditions occurs:
monotonically increasing a virtual channel number from a first channel number to a higher channel number, or
monotonically decreasing the virtual channel number from the first channel number to a lower channel number.
7. The method of claim 1 , wherein the computer network is a butterfly network architecture.
8. The method of claim 1 , wherein the computer network comprises a chip multiprocessor architecture and the first switch A, second switch C and intermediate switch B are each coupled to an associated processor.
9. The method of claim 1 , wherein the selected condition is maintained for subsequent packet routing.
10. A computer-readable recording medium having instructions stored thereon, the instructions, when executed by a processor, cause the processor to perform the operations of:
setting a turn rule for routing packets across the computer network, the turn rule prohibiting sending packets from a first switch (A) to a second switch (C) via an intermediate switch (B) given a selected condition, the condition being selected from the group consisting of:
a distinct identifier of intermediate switch B has a value greater than values of distinct identifiers of both first switch A and second switch C, or
the distinct identifier of intermediate switch B has a value less than the values of the distinct identifiers of both first switch A and second switch C; and
providing the turn rule to each of the first switch A, second switch C and intermediate switch B for routing the packets across the computer network according to the turn rule.
11. The recording medium of claim 10 , wherein the operations further comprise:
determining whether the turn rule would be violated given the selected condition;
setting a virtual channel rule that permits violation of the turn rule by selecting a unique ordering of the plurality of virtual channels; and
routing the packets across the computer network according to the virtual channel rule.
12. The recording medium of claim 10 , wherein the operations further comprise:
determining whether the turn rule would be violated given the selected condition; and
setting a virtual channel rule that permits violation of the turn rule if one and only one of the following conditions occurs:
monotonically increasing a virtual channel number from a first channel number to a higher channel number, or
monotonically decreasing the virtual channel number from the first channel number to a lower channel number.
13. A computer system, comprising:
a plurality of switching elements being disposed at respective nodes in the computer system;
each switching element implementing a turn rule for routing packets in the computer system, the turn rule prohibiting sending packets from a first switching element (A) to a second switching element (C) via an intermediate switching element (B) given a selected condition, the condition being selected from the group consisting of:
a distinct identifier of intermediate switching element B has a value greater than values of distinct identifiers of both first switching element A and second switching element C, or
the distinct identifier of intermediate switching element B has a value less than the values of the distinct identifiers of both first switching element A and second switching element C.
14. The computer system of claim 13 , wherein one or more of the first switching element A, second switching element C and intermediate switching element B are configured for adaptive routing.
15. The computer system of claim 13 , wherein one or more of the first switching element A, second switching element C and intermediate switching element B store multiple routing tables.
16. The computer system of claim 13 , wherein the distinct identifier of each switching element is a hash of a hardware identifier of that respective switching element.
17. The computer system of claim 13 , wherein switching elements A, B and C each support a plurality of virtual channels and employ a virtual channel rule permitting violation of the turn rule by following a preselected unique ordering of the plurality of virtual channels.
18. The computer system of claim 13 , wherein switching elements A, B and C each support a plurality of virtual channels and employ a virtual channel rule permitting violation of the turn rule if one and only one of the following conditions occurs:
monotonically increasing a virtual channel number from a first channel number to a higher channel number, or
monotonically decreasing the virtual channel number from the first channel number to a lower channel number.
19. The computer system of claim 13 , wherein the computer system has a butterfly network architecture.
20. The computer system of claim 13 , wherein the computer system has a mesh network architecture.
21. The computer system of claim 13 , wherein the computer system comprises a chip multiprocessor architecture and switching elements A, B and C are each coupled to an associated processor.
22. The computer system of claim 13 , wherein the switching elements A, B and C comprise routers in the nodes of a computer network, at least some of the routers connecting to hosts for transmitting data packets across the network.