System and method for preventing deadlock in richly-connected multi-processor computer system using dynamic assignment of virtual channels

• US 7,773,618 B2
• Filed: 11/08/2006
• Issued: 08/10/2010
• Est. Priority Date: 11/08/2006
• Status: Expired due to Fees

• Current Assignee: Hercules Technology
• Original Assignee: SicorTex Incorporated
• Inventors: Reilly, Matthew H., Godiwala, Nitin, Leonard, Judson S.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): CHAU, PETER P
• Application Number:
  US11/594,426
• Publication Number:
  US 20080107106A1
• Time in Patent Office: 1,371 Days
• Field of Search: None
• US Class Current: 370/409
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion

Abstract

Systems and methods for preventing deadlock in richly-connected multiprocessor computer system using dynamic assignment of virtual channels. Deadlock is prevented in a multiprocessor computer system having a large plurality of processing nodes interconnected by a defined interconnection topology. Each link in the interconnection topology is associated with a set of virtual channels. Each virtual channel has corresponding communication buffers to store communication data and each virtual channel has an associated virtual channel identifier. Each communication between a source processing node and a target processing node is assigned an initial virtual channel to convey the communication from the source processing node. At an intermediate processing node, a different virtual channel is assigned to convey the communication toward the target processing node, in accordance with pre-defined rules to avoid a cycle of dependency of communication buffer resources.

Claims

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;

receiving the communication;

identifying a node identifier value of a previous hop node from which the communication is received;

identifying a node identifier value of a next hop node on which to forward the communication from the intermediate processing node towards the target processing node;

initiating a comparison of a node identifier value assigned to the intermediate processing node to both the node identifier value of the previous hop node and the node identifier value of the next hop node;

based on results of the comparison, assigning a second virtual channel identifier value to the communication in place of the first virtual channel identifier value, the second virtual channel identifier value indicating a virtual channel on which to convey the communication from the intermediate processing node to the next hop node toward the target processing node, wherein assignment of the second virtual channel identifier value is in accordance with pre-defined rules to avoid a cycle of dependency of communication buffer resources; and

receiving the communication at the target 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.

2. The method of claim 1 further comprising:

storing the communication in a buffer of the intermediate processing node, the buffer of the intermediate processing node dedicated for storing communications transmitted on the virtual channel as specified by the first virtual channel identifier value; and

initiating arbitration of forwarding the communication from the buffer to the next hop node based on transmission of the communication over the virtual channel as specified by the second virtual channel identifier value.

3. The method of claim 2, wherein the results of the comparison indicate that a magnitude of the node identifier value of the intermediate processing node is greater than a magnitude of the node identifier value of the previous hop node.

4. The method of claim 3, wherein the results of the comparison indicate that a magnitude of the node identifier value of the intermediate processing node is greater than a magnitude of the node identifier value of the next hop node.

5. The method of claim 1, wherein initiating the comparison includes:

comparing a magnitude of the node identifier value of the intermediate processing node to a magnitude of the node identifier value of the previous hop node; and

comparing the magnitude of the node identifier value of the intermediate processing node to a magnitude of the node identifier value of the next hop node.

6. 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:

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 and each virtual channel having an associated virtual channel identifier;

for each communication between a source processing node and a target processing node, assigning an initial virtual channel on which to convey a communication from the source processing node;

at an intermediate processing node, assigning a different virtual channel to the communication in lieu of the initial virtual channel to convey the communication toward the target processing node via the different virtual channel, wherein assignment of the different virtual channel is in accordance with pre-defined rules to avoid a cycle of dependency of communication buffer resources;

receiving the communication at the target processing node;

wherein each processing node is assigned a processing node identifier, and wherein the rules to avoid a cycle of dependency consider the processing node identifiers of the intermediate processing node in relation to an immediately prior processing node relative to the intermediate processing node and an immediately subsequent processing node relative to the intermediate processing node, both the immediately prior processing node and the immediately subsequent processing node disposed in a path of the communication through the topology; and

wherein the processing node identifiers are numbers and wherein the rules determine if the intermediate processing node has a greater identifier value than identifier values of both the immediately prior processing node and the immediately subsequent processing node and, if so, the rules decrementing a virtual channel identifier value assigned to the communication.

7. The method of claim 6, wherein the communication from the source processing node to the target processing node passes through a plurality of intermediate processing nodes and wherein the virtual channel assignment is changed a plurality of times in the path of the communication as the communication is transmitted through the defined interconnection topology.

8. The method of claim 6, wherein the defined interconnection topology is a Kautz topology of plural degree and plural diameter.

9. The method of claim 8, wherein a virtual channel identifier assigned to the communication is generated based on a function of the diameter of the topology.

10. The method of claim 6, wherein the defined interconnection topology and processing node identifiers are known in advance and wherein each processing node includes a programmable register to indicate whether a virtual channel identifier for routing the communication should be changed on a given route, said programmable registers being programmed in accordance with the defined interconnection topology and processing node identifiers and in accordance with the pre-defined rules.

11. A multiprocessor computer system comprising:

a plurality of processing nodes;

a defined interconnection topology having links interconnecting the processing nodes;

wherein each processing node in the multiprocessor computer system includes link logic to transmit data on, and receive data from, links connected to the processing node,

communication buffers to store communication data from the links; and

virtual channel assignment logic to associate a virtual channel identifier with a communication buffer, wherein the virtual channel assignment logic includes logic to assign an initial virtual channel for a communication if the node is the source of the communication, and wherein the virtual channel assignment logic includes logic to dynamically and conditionally assign a different virtual channel to a communication in which the processing node is an intermediate node in the communication, wherein the logic to dynamically assign a different virtual channel uses pre-defined rules to determine if the different virtual channel should be assigned to the communication, and wherein the predefined rules avoid a cycle of dependency of communication buffer resources;

wherein the intermediate processing node is configured to;

receive a string of route information in the communication, the string of route information indicating a link on which the communication is transmitted to the intermediate node;

apply a bit shift operation to the string of route information to produce a shifted string of route information; and

utilize the shifted string of route information to identify an egress link of the intermediate node upon which to forward the

communication on a path toward a target processing node.

12. The system of claim 11, wherein each processing node is assigned a processing node identifier, and wherein the predefined rules to avoid a cycle of dependency consider the processing node identifiers of an intermediate processing node in relation to the immediately prior processing node and the immediately subsequent processing node in the route of the communication through the topology.

13. The system of claim 11, wherein the defined interconnection topology is a Kautz topology of plural degree and plural diameter.

14. The multiprocessor computer system of claim 11, wherein the intermediate node includes a buffer to store the communication, the buffer of the intermediate node dedicated for storing communications transmitted on the virtual channel as specified by the virtual channel identifier value;

and

wherein the intermediate node includes arbitration logic to arbitrate forwarding of the communication from the buffer at the intermediate node to a next hop node over the different virtual channel.