System and method for arbitration for virtual channels to prevent livelock in a richly-connected multi-processor computer system

A method of preventing livelock, the method comprising:

• defining a set of virtual channels on which to forward data packets through an interconnection topology of multiple processor nodes;
• at each processor node in the interconnection topology, allocating sets of buffers for temporary storage of data packets transmitted through the interconnection topology, each of the data packets having a respective virtual channel identifier value indicating a corresponding virtual channel on which to forward a corresponding data packet;
• at an intermediate processor node in the interconnection topology between a sending node and a receiving node:
• receiving a particular data packet, the particular data packet being transmitted through the interconnection topology from the sending node to the receiving node;
• storing the particular data packet in a first set of buffers;
• in a first arbitration stage at the intermediate processor node:
• identifying a respective oldest data packet in each of the sets of buffers;
• identifying that the particular data packet is an oldest data packet amongst multiple data packets in the first set of buffers;
• in response to comparing ages of oldest data packets in each of the sets of buffers, identifying that the particular data packet has been waiting longest amongst the respective oldest data packets for transmission on the virtual channel from the intermediate processing node to a next hop node towards the receiving node;
• in a second arbitration stage at the intermediate processor node:
• identifying a particular virtual channel on which to forward the particular data packet, the particular virtual channel being specified by a virtual channel identifier in the particular data packet;
• identifying a set of buffers storing data packets that contend for use of the particular virtual channel, each of the data packets in the identified set of buffers having a same respective virtual channel identifier value as the virtual channel identifier in the particular data packet;
• accessing history information to determine a given set of buffers of the identified set of buffers to most recently transmit a respective data packet on the particular virtual channel, the given set of buffers being a second set of buffers of the sets of buffers;
• in a third arbitration stage at the intermediate processor node:
• in lieu of selecting the particular data packet from the first set of buffers for transmission over the particular virtual channel, selecting a data packet from the second set of buffers;
• transmitting the selected data packet from the second set of buffers over the particular virtual channel.

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;
• storing a first set of data packets in a first set of buffers, each data packet in the first set of buffers indicating a respective virtual channel on which to be forwarded in the interconnection topology;
• storing a second set of data packets in a second set of buffers, each data packet in the second set indicating a respective virtual channel on which to be forwarded in the interconnection topology;
• storing a third set of data packets in a third set of buffers, each data packet in the third set indicating a respective virtual channel on which to be forwarded in the interconnection topology;
• identifying a first data packet as being an oldest stored data packet in the first set of buffers;
• identifying a second data packet as being an oldest stored data packet in the second set of buffers;
• identifying a third data packet as being an oldest stored data packet in the third set of buffers;
• identifying that the first data packet is an oldest stored data packet amongst the first data packet, the second data packet, and the third data packet;
• identifying a virtual channel identifier value in the first data packet, the virtual channel identifier value in the first data packet indicating a virtual channel on which to transmit the first data packet, the virtual channel being one of multiple virtual channels in the interconnection topology;
• identifying that the third data packet includes a same virtual channel identifier value as the first data packet;
• accessing history information indicating which one of the first set of buffers and the third set of buffers most recently transmitted a data packet on the virtual channel as specified by the virtual channel identifier value in the first data packet;
• and
• in response to detecting that the third set of buffers was least recently serviced to transmit a data packet on the virtual channel, initiating transmission of the third data packet on the virtual channel as specified by the virtual channel identifier value in the first data packet.