Multistage interconnect network uses a master processor to perform dynamic configuration for all switch nodes based on a predetermined topology

• US 6,243,361 B1
• Filed: 11/10/1998
• Issued: 06/05/2001
• Est. Priority Date: 05/01/1991
• Status: Expired due to Fees

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: McMillen, Robert J., Watson, M. Cameron, Chura, David J.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US09/189,853
• Time in Patent Office: 938 Days
• Field of Search: 370/230, 370/231, 370/212, 370/235, 370/237, 370/254, 370/351, 370/352, 370/353, 370/354, 370/355, 370/255
• US Class Current: 370/254
• CPC Class Codes: G01J 3/06 Scanning arrangements arrangements for order-selection
• CPC Class Codes: G06F 11/1423 by reconfiguration of paths
• CPC Class Codes: G06F 11/2005 using redundant communication controllers
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: G06F 11/22 Detection or location of defective computer hardware by testing during standby operation or during idle time, e.g. start-up testing
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/358 Infiniband Switches
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/555 Error detection
• CPC Class Codes: H04L 49/557 Error correction, e.g. fault recovery or fault tolerance
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

A multistage interconnect network (MIN) capable of supporting massive parallel processing, including point-to-point and multicast communications between processor modules (PMs) which are connected to the input and output ports of the network. The network is built using interconnected switch nodes arranged in 2 |log_b N| stages, wherein b is the number of switch node input/output ports, N is the number of network input/output ports and |log_b N| indicates a ceiling function providing the smallest integer not less than log_b N. The additional stages provide additional paths between network input ports and network output ports, thereby enhancing fault tolerance and lessening contention.

Claims

1. A multistage interconnect network, comprising:

(a) a plurality of switch nodes interconnected for communication therebetween, each switch node having at least one input port and at least one output port, wherein the input ports are selectively connected to the output ports; and

(b) a master processor, coupled to at least one of the switch nodes, for performing dynamic configuration of au of the switch nodes in the network herein the master processor determines a topology for the network based on how al of the switch nodes are interconnected and configures each of the switch nodes based on the determined topology, so that messages can be routed correctly between the switch nodes.

2. The network of claim 1, wherein each switch node includes at least one table for storing routing information generated by the master processor, so that messages can be routed correctly between the switch nodes.

3. The network of claim 2, wherein the switch nodes are queried to determine how they are interconnected and the table is generated in response thereto.

4. The network of claim 2, wherein the table is generated by the master processor.

5. The network of claim 2, wherein the table indicates how the switch nodes are interconnected.

6. The network of claim 1, wherein each switch node includes a path selector for selectively connecting the switch node'"'"'s input ports to the switch node'"'"'s output ports.

7. The network of claim 6, wherein the path selector connects an input port receiving a message to an output port sending the received message.

8. A method of operating a multistage interconnect network, comprising:

(a) interconnecting a plurality of switch nodes for communication therebetween, each switch node having at least one input port and at least one output port, wherein the input ports are selectively connected to the output ports; and

(b) performing dynamic configuration of all of the switch nodes in the network using a master processor coupled to at least one of the switch nodes, wherein the master processor determines a topology for the network based on how all of the switch nodes are interconnected and configures each of the switch nodes based on the determined topology, so that messages can be routed correctly between the switch nodes.

9. The method of claim 8, wherein each switch node includes at least one table for storing routing information generated by the master processor, so that messages can be routed correctly between the switch nodes.

10. The method of claim 9, wherein the switch nodes are queried to determine how they are interconnected and the table is generated in response thereto.

11. The method of claim 9, wherein the table is generated by the master processor.

12. The method of claim 9, wherein the table indicates how the switch nodes are interconnected.

13. The method of claim 8, wherein each switch node includes a path selector for selectively connecting the switch node'"'"'s input ports to the switch node'"'"'s output ports.

14. The method of claim 13, wherein the path selector connects an input port receiving a message to an output port sending the received message.