# US 2008/0107106 A1 · System and method for preventing deadlock in richly-connected multi-processor computer system using dynamic assignment of virtual channels > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2008/0107106 A1 - Document ID: US20080107106A1 - Status: Published application - Kind: A1 - Application number: 11/594,426 - Filed: 2006-11-08 - Published: 2008-05-08 - Earliest claimed: 2006-11-08 - Assignees: SiCortex, Inc. - Inventors: Judson S. Leonard; Matthew H. Reilly; Nitin Godiwala - Web page: https://patentgrep.com/patent/US20080107106A1 ## CPC - G06F 15/17381: {Two dimensional, e.g. mesh, torus} - H04L 47/10: Flow control; Congestion control - H04L 47/11: Identifying congestion - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 1 A method for preventing deadlock in a multiprocessor computer system having a large plurality of processing nodes interconnected by a defined interconnection topology, in which a communication from a source processing node to a target processing node may pass through one or more intermediate nodes en route to the target processing node, the method comprising: for each link in the 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 to convey the communication from the source processing node; at an intermediate processing node, assigning a different virtual channel to convey the communication toward the target processing node, wherein the assignment of the different virtual channel 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. ### Claim 2 (depends on 1) The method of claim 1 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 the immediately prior processing node and the immediately subsequent processing node in the route of the communication through the topology. ### Claim 3 (depends on 2) The method of claim 2 wherein the processing node identifiers are numbers and wherein the rules determine if the intermediate processing node has a greater identifier than the identifiers of both the immediately prior processing node and the immediately subsequent processing node and if so the rules decrement the virtual channel assignment for the communication. ### Claim 4 (depends on 1) The method of claim 1 wherein a communication from a source processing node to a 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 route of the communication through the topology. ### Claim 5 (depends on 1) The method of claim 1 wherein the defined interconnection topology is a Kautz topology of plural degree and plural diameter. ### Claim 6 (depends on 5) The method of claim 5 wherein the initial channel identifier is a function of the diameter of the topology. ### Claim 7 (depends on 3) The method of claim 3 wherein the 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 should be changed on a given route, said programmable registers being programmed in accordance with the known topology and processing node identifiers and in accordance with the pre-defined rules. ### Claim 8 A large scale multiprocessor computer system, comprising: a large plurality of processing nodes; a defined interconnection topology having links interconnecting the processing nodes; wherein each processing node 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 a different virtual channel should be assigned, and wherein the predefined rules avoid a cycle of dependency of communication buffer resources. ### Claim 9 (depends on 8) The system of claim 8 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. ### Claim 10 (depends on 1) The system of claim 1 wherein the defined interconnection topology is a Kautz topology of plural degree and plural diameter.