Patent ID: 7773616
Filing Date: 2010-08-10
Classification: H04L

Abstract:
1. A method of communicating packets in a multiprocessor computer system having a plurality of processing nodes interconnected by an interconnection topology, the method comprising: creating virtual channels in the interconnection topology based on links between the processing nodes 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, assigning a respective virtual channel to convey the communication to a target processing node; at a processing node, providing a set of buffers to associate with virtual channels, a first subset of buffers being dedicated for fixed correspondence to virtual channel identifiers, and a second subset of buffers being dedicated for dynamic allocation and assignment to virtual channels; arbitrating transmission of data packets to next processing nodes in the interconnection topology based on a combination of: 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; and 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; and 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 first 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; identifying a virtual channel and next hop processing node associated with the first data packet; identifying that the third data packet specifies a same virtual channel identifier value and next hop processing node as the first data packet; based on the servicing history information, identifying that the first set of buffers has been waiting longer to forward a data packet than the third set of buffers; and subsequent to forwarding of the first data packet on an egress link from the processing node, initiating forwarding of the third data packet on the egress link.