Routing methods for a multinode SCI computer system

• US 5,898,827 A
• Filed: 09/27/1996
• Issued: 04/27/1999
• Est. Priority Date: 09/27/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Hornung, Bryan D., Marietta, Bryan D.
• Primary Examiner(s): Palys, Joseph E.
• Application Number:
  US08/720,331
• Time in Patent Office: 942 Days
• Field of Search: 395/182.02, 395/182.09, 395/200.15, 395/200.11, 395/200.1, 395/200.69, 395/200.68, 395/200.7, 395/200.71, 395/200.72, 395/200.73 , 395/200.74, 370/217, 370/351, 364/949.91
• US Class Current: 714/11
• CPC Class Codes: G06F 13/14 Handling requests for interconnection or transfer
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 3/14 Digital output to display device ; Cooperation and interconnection of the display device with other functional units
• CPC Class Codes: G09G 2370/025 LAN communication management
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A multi-dimensional node or processor arrangement allows a similar number of nodes in a linear array to be arranged in a more compact form, thus overcoming a latency problem in communications between the most distant nodes/processors. The multi-dimensional arrangement also allows for multiple paths between nodes. This feature greatly improves survivability of the system, such that when one node dies there is always at least one other path that is available to get to the other nodes in the system. Thus, the system can continue to run and only the resources of the one node that died are lost. A first set of routing rules governs the migration of communications between a source node and a destination node around the node array when all of the nodes are functioning. A secondary set of rules displaces or modifies the first set when a node is not functioning.

Claims

1. A multi-processor computer system comprising:

a two dimensional array of nodes having rows and columns, each node having at least one processor, and each node has a corresponding ID indicating a position of each node in the array;

a plurality of interface rings, wherein the nodes in each row are linked together by at least one of the rings, and the nodes in each column are linked together by at least one of the rings;

a plurality of controllers, with each node having at least one controller, and said one controller interfaces the node with two rings;

one ring being in a column direction and the other ring being in a row direction;

a data packet that includes an ID of a destination node, the packet is sent to a receiving controller in a receiving node, wherein the receiving controller compares an ID of the receiving node with the ID stored in data packet to determine whether a destination match has occurred;

when the destination match has occurred, the controller accepts the data packet for processing by the node; and

when the destination match has not occurred, the controller routes the data packet to an adjacent node; and

a plurality of configuration registers, with each node having a respective configuration register, each configuration register stores information for routing the packet around a failed node, wherein if the destination match has not occurred, the controller compares the information stored in the configuration register with the ID of the destination node to determine whether a failed match has occurred;

when the failed match has occurred, the controller routes the packet to a secondary adjacent node; and

when the failed match has not occurred, the controller routes the data packet to the adjacent node;

wherein each configuration register in all of the nodes on each column on either side of the column of the failed node contain the column ID of the failed node, each configuration register in all of the nodes on each row on either side of the row of the failed node contain the row ID of the failed node; and

wherein only four configuration registers contain both the row ID and the column ID of the failed node, and only the four configuration registers are enabled and all other configuration registers are disabled.

2. The multi-processor computer system according to claim 1, wherein:

the nodes number twenty eight; and

the array is a four by seven arrangement of nodes.

8. The multi-processor computer system of claim 1, wherein:

each ring is a SCI standard ring; and

each controller is a SCI controller.

3. A method for routing a data packet around a multi-processor computer system;

the system comprising a two dimensional array of nodes having rows and columns, with each node having a corresponding ID indicating a position of each node in the array, wherein each node ID has a column ID indicating a column position of each node in the array;

wherein each node includes a configuration register that stores information for routing the packet around a failed node, and each configuration register in all of the nodes on each column on either side of the column of the failed node contain the column ID of the failed node, and each configuration register in all of the nodes on each row on either side of the row of the failed node contain the row ID of the failed node;

the method comprising the steps of;

comparing an ID of a destination node contained within the packet with an ID of a current node position of the packet to determine whether a destination match has occurred;

accepting the data packet for further processing by the current node when the destination match has occurred;

comparing, when the destination match has not occurred, a column ID of the destination node contained within the packet with a column ID of the current node position of the packet to determine whether a column match has occurred;

routing the data packet to a first node in an adjacent row when the column match has occurred;

routing the data packet to a second node in an adjacent column when the column match has not occurred;

comparing, when one of the nodes has failed and the destination match has not occurred, the information stored in the configuration register with the ID of the destination node to determine whether a failed match has occurred;

routing the packet to a secondary adjacent node when the failed match has occurred;

routing the packet to the adjacent node when the failed match has not occurred;

enabling all configuration registers that contain both the row ID and the column ID of the failed node; and

disabling all other configuration registers;

wherein the step of comparing the information stored in the configuration register with the ID of the destination node to determine whether a failed match has occurred is performed only on the enabled configuration registers.

4. The method according to claim 3, wherein each node ID has a row ID indicating a row position of each node in the array, and a column match has occurred, the method further comprising the steps of:

comparing a row ID of the destination node contained within the packet with a row ID of the first node to determine whether a row match has occurred;

routing the data packet to a third node in a next adjacent row when the row match not has occurred; and

accepting the data packet for further processing by the first node when the row match has occurred.

5. A method for routing a data packet around a multi-processor computer system;

the system comprising a two dimensional array of nodes having rows and columns, with each node having a corresponding ID indicating a position of each node in the array, wherein each node ID has a row ID indicating a row position of each node in the array;

wherein each node includes a configuration register that stores information for routing the packet around a failed node, and each configuration register in all of the nodes on each column on either side of the column of the failed node contain the column ID of the failed node, and each configuration register in all of the nodes on each row on either side of the row of the failed node contain the row ID of the failed node;

the method comprising the steps of;

comparing an ID of a destination node contained within the packet with an ID of a current node position of the packet to determine whether a destination match has occurred;

accepting the data packet for further processing by the current node when the destination match has occurred;

comparing, when the destination match has not occurred, a row ID of the destination node contained within the packet with a row ID of the current node position of the packet to determine whether a row match has occurred;

routing the data packet to a first node in an adjacent column when the row match has occurred;

routing the data packet to a second node in an adjacent row when the row match has not occurred;

comparing, when one of the nodes has failed and the destination match has not occurred, the information stored in the configuration register with the ID of the destination node to determine whether a failed match has occurred;

routing the packet to a secondary adjacent node when the failed match has occurred;

routing the packet to the adjacent node when the failed match has not occurred;

enabling all configuration registers that contain both the row ID and the column ID of the failed node; and

disabling all other configuration registers;

wherein the step of comparing the information stored in the configuration register with the ID of the destination node to determine whether a failed match has occurred is performed only on the enabled configuration registers.

6. The method according to claim 5, wherein each node ID has a column ID indicating a column position of each node in the array, and a row match has occurred, the method further comprising the steps of:

comparing a column ID of the destination node contained within the packet with a column ID of the first node to determine whether a column match has occurred;

routing the data packet to a third node in a next adjacent column when the column match has not occurred; and

accepting the data packet for further processing by the first node when the column match has occurred.

7. A method for routing a data packet around a multi-processor computer system to a destination node and avoiding a failed node;

the system comprising a two dimensional array of nodes having rows and columns, with each node having a corresponding row ID and a corresponding column ID indicating a position of each node in the array, each node includes a configuration register that stores information for routing the packet around the failed node;

each configuration register in all of the nodes on each column on either side of the column of the failed node contain the column ID of the failed node;

each configuration register in all of the nodes on each row on either side of the row of the failed node contain the row ID of the failed node;

the method comprising the steps of;

enabling all configuration registers that contain both the row ID and the column ID of the failed node;

comparing a column ID of the destination node contained within the packet with a column ID of a first current node position of the packet to determine whether a first column match has occurred;

comparing, if the configuration register is enabled, the column ID of the destination node contained within the packet with a column ID of the configuration register of the first current node position to determine whether a second column match has occurred;

routing the data packet to an adjacent node in an adjacent column until either the first column match occurs or the second column match occurs;

comparing a row ID of the destination node contained within the packet with a row ID of a second current node position of the packet to determine whether a first row match has occurred;

comparing, if the configuration register is enabled, the row ID of the destination node contained within the packet with a row ID of the configuration register of the second current node position to determine whether a second row match has occurred;

routing the data packet to an adjacent node in an adjacent row until either the first row match occurs or the second row match occurs;

comparing a column ID of the destination node contained within the packet with a column ID of a third current node position of the packet to determine whether a third column match has occurred;

routing the data packet to an adjacent node in an adjacent column until the third column match occurs; and

accepting the data packet for further processing by the node where the third column match occurred.