Reconfigurable, fault tolerant, multistage interconnect network and protocol

• US 7,706,361 B2
• Filed: 09/20/2005
• Issued: 04/27/2010
• Est. Priority Date: 05/01/1991
• Status: Expired due to Fees

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: McMillen, Robert J., Watson, M. Cameron, Chura, David J.
• Primary Examiner(s): Patel; Jayanti K
• Assistant Examiner(s): SOL, ANTHONY M
• Application Number:
  US11/230,340
• Publication Number:
  US 20060013207A1
• Time in Patent Office: 1,680 Days
• Field of Search: None
• US Class Current: 370/388
• 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 communications system, comprising:

(a) a plurality of switch nodes, each switch node comprising a first plurality of input ports, a second plurality of output ports, and means for selectively connecting the input ports to the output ports; and

(b) means for connecting the switch nodes together in a multistage interconnect network, the means for connecting using forward channel and back channel signal paths coupled to each of the input and output ports in the switch nodes;

(c) wherein each of the switch nodes stores reconfigurable mapping data that identifies available interconnections between its input and output ports, the reconfigurable mapping data comprises input and output enable vectors indicating which of the input and output ports are operational, and each of the switch nodes arbitrarily interconnects any one of its input ports with (1) any one of its output ports, (2) a predetermined number of its output ports, and (3) all of its output ports.

2. The system of claim 1, wherein the back channel signal paths have a narrower bandwidth relative to the forward channel signal paths to simplify packaging.

3. The system of claim 1, wherein the switch nodes combine signals from the back channel signal paths.

4. The system of claim 1, wherein the switch nodes synchronously combine replies from the back channel signal paths so that the replies are sorted as they propagate through the switch nodes, and only the reply having a highest priority is transmitted to the next switch node on the back channel signal path.

5. The system of claim 1, wherein each switch node, when interconnecting the input ports with the output ports, arbitrates between competing messages to determine a priority of the messages in accordance with predetermined rules.

6. The system of claim 5, wherein each switch node arbitrates between competing messages by giving priority to the messages whose routing packets indicate more than one receiving destination.

7. The system of claim 5, wherein each switch node load levels the messages being transmitted through the switch node.

8. The system of claim 1, wherein each switch node returns a signal back to an input port as to an interconnection'"'"'s availability.

9. The system of claim 1, wherein each switch node re-routes a message between the input and output ports when a given path is unavailable.

10. A method for operating a communications system, comprising:

(a) connecting a plurality of switch nodes in a multistage interconnect network, each switch node comprising a first plurality of input ports, a second plurality of output ports, and each switch node selectively connecting the input ports to the output ports;

(b) wherein the switch nodes are connected together using forward channel and back channel signal paths coupled to each of the input and output ports in the switch nodes; and

(c) wherein each of the switch nodes stores reconfigurable mapping data that identifies available interconnections between its input and output ports, the reconfigurable mapping data comprises input and output enable vectors indicating which of the input and output ports are operational, and each of the switch nodes arbitrarily interconnects any one of its input ports with (1) any one of its output ports, (2) a predetermined number of its output ports, and (3) all of its output ports.

11. The method of claim 10, wherein the back channel signal paths have a narrower bandwidth relative to the forward channel signal paths to simplify packaging.

12. The method of claim 10, wherein the switch nodes combine signals from the back channel signal paths.

13. The method of claim 10, wherein the switch nodes synchronously combine replies from the back channel signal paths so that the replies are sorted as they propagate through the switch nodes, and only the reply having a highest priority is transmitted to the next switch node on the back channel signal path.

14. The method of claim 10, wherein each switch node, when interconnecting the input ports with the output ports, arbitrates between competing messages to determine a priority of the messages in accordance with predetermined rules.

15. The method of claim 14, wherein each switch node arbitrates between competing messages by giving priority to the messages whose routing packets indicate more than one receiving destination.

16. The method of claim 14, wherein each switch node load levels the messages being transmitted through the switch node.

17. The method of claim 10, wherein each switch node returns a signal back to an input port as to an interconnection'"'"'s availability.

18. The method of claim 10, wherein each switch node re-routes a message between the input and output ports when a given path is unavailable.