Patent ID: 7773617
Filing Date: 2010-08-10
Classification: G06F

Abstract:
1. A method of preventing livelock in a multiprocessor computer system having a plurality of processing nodes, the processing node interconnected as defined by an 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, and in which each processing node has a plurality of input links and a plurality of egress links, the method comprising: associating a set of virtual channels to each link in the interconnection topology, each virtual channel having an associated virtual channel identifier; for each communication between a source processing node and a target processing node in the interconnection topology, assigning a virtual channel to convey the communication; at a processing node in a route of the communication, buffering communication data from the plurality of input links in cross point buffers, each communication including a respective virtual channel identifier, the respective virtual channel identifier indicating which of the multiple virtual channels on which to transmit the communication to the target processing node; a subset of the cross point buffers bidding for use of an egress link; arbitrating among the subset of cross point buffers and selecting a communication from the cross point buffers on which to transmit over the egress link based on predetermined arbitration rules; identifying, based on the respective virtual channel identifier, the virtual channel of the selected communication; determining whether any other communications bidding for use of the egress link are associated with the identified virtual channel and if so whether any communication has been waiting longer than the selected communication; allowing a communication bidding for use of the egress link and associated with the identified virtual channel and that has been waiting longer than the selected communication to use the egress link before the selected communication; providing a first set of data packet buffers to store a first set of data packets, each data packet buffer in the first set configured to request forwarding of a respective stored data packet when a buffer is available in a downstream processor node in the interconnection topology; providing a second set of data packet buffers to store a second set of data packets, each data packet buffer in the second set configured to request forwarding of a respective stored data packet when a buffer is available in a downstream processor node in the interconnection topology; providing a third set of data packet buffers to store a third set of data packets, each data packet buffer in the third set configured to request forwarding of a respective stored data packet when a buffer is available in a downstream processor node in the interconnection topology; storing first history information indicating an order of receiving data packets stored in the first set of data packet buffers; storing second history information indicating an order of receiving data packets stored in the second set of data packet buffers; storing third history information indicating an order of receiving data packets stored in the third set of data packet buffers; utilizing the first history information to identify a first data packet, the first data packet being an oldest data packet in the first set of data packet buffers for forwarding through the interconnection topology; utilizing the second history information to identify a second data packet, the second data packet being an oldest data packet in the second set of data packet buffers for forwarding through the interconnection topology; utilizing the third history information to identify a third data packet, the third data packet being an oldest data packet in the third set of data packet buffers for forwarding through the interconnection topology; based on servicing history information, identifying that the third set of data packet buffers was least recently chosen from the first set, the second set, and the third set for forwarding of a respective data packet to a target destination; and in response to identifying that the third set of data packet buffers was least recently chosen from the first set, the second set, and the third set for forwarding of a respective data packet to a target destination, initiating transmission of the third data packet over a virtual channel as specified by a virtual channel identifier value in the first data packet.