Patent ID: 7773618
Filing Date: 2010-08-10
Classification: G06F,H04L

Abstract:
1. A method for preventing deadlock in a multiprocessor computer system having a plurality of processing nodes interconnected by a defined interconnection topology, in which a communication from a source processing node to a target processing node passes through one or more intermediate nodes en route to the target processing node, the method comprising: assigning a unique node identifier value to each processing node in the defined interconnection topology; for each link in the defined interconnection topology, associating a set of virtual channels, each virtual channel having corresponding communication buffers to store communication data, each virtual channel assigned a unique virtual channel identifier value; assigning a first virtual channel identifier value to a communication, the first virtual channel identifier value indicating a virtual channel on which to convey the communication from the source processing node to an intermediate processing node in the defined interconnection topology; at the intermediate processing node: encoding the communication sent to the intermediate processing node to include a string of route information, the string of route information indicating a link on which the communication is transmitted to the intermediate processing node; at the intermediate processing node receiving the communication, applying a bit shift operation to the string of route information to produce a shifted string of route information; and utilizing the shifted string of route information to identify an egress link of the intermediate processing node upon which to forward the communication on a path to the target processing node.