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 value of a distinct identifier of the intermediate switch B in relation to values of 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.