Multistage interconnect network combines back channel replies received from destinations into a single result and transmits to the source

• US 7,058,084 B2
• Filed: 02/14/2001
• Issued: 06/06/2006
• 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/783,923
• Publication Number:
  US 20020010735A1
• Time in Patent Office: 1,938 Days
• Field of Search: 370/254, 370/230, 370/235, 370/473, 370/336, 370/404, 370/335, 370/342, 370/343, 370/345, 370/255, 370/464, 714/4, 714/798, 709/239
• US Class Current: 370/473
• 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 connected together, each of the switch nodes comprising a first plurality of input ports selectively connectable to a second plurality of output ports, the multistage interconnect network comprising more than ┌

log_b N┐

stages of switch nodes, wherein b is a total number of switch node input/output port pairs, N is a total number of network input/output port pairs, and ┌

log_b N┐

indicates a ceiling function providing the smallest integer not less than log_b N, the stages thereby providing a plurality of paths between any network input port and network output port to enhance fault tolerance and lessen contention;

(b) the multistage interconnect network including forward channel and back channel signal paths between the switch nodes;

(c) the multistage interconnect network capable of multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network;

(d) the multistage interconnect network capable of combining back channel replies received from the destinations into a single result, wherein the result is transmitted on the back channel to the source.

2. The system of claim 1 wherein the multistage interconnect network steers a multicast request for a supercluster to a bounce back point within the network, wherein all multicast requests to the supercluster use the same bounce back point.

3. The system of claim 2 wherein the multistage interconnect network steers a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster.

4. The system of claim 1 wherein the multistage interconnect network permits only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.

5. A method of operating a multistage interconnect network comprising:

(a) multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network, wherein the multistage interconnect network comprises a plurality of switch nodes connected together, the multistage interconnect network including forward channel and back channel signal paths between the switch nodes, each of the switch nodes comprising a first plurality of input ports selectively connectable to a second plurality of output ports, the multistage interconnect network comprising more than ┌

log_b N┐

stages of switch nodes, wherein b is a total number of switch node input/output port pairs, N is a total number of network input/output port pairs, and ┌

log_b N┐

indicates a ceiling function providing the smallest integer not less than log_b N the stages thereby providing a plurality of paths between any network input port and network output port to enhance fault tolerance and lessen contention; and

(b) combining back channel replies received from the destinations into a single result in the multistage interconnect network, wherein the result is transmitted on the back channel to the source.

6. The method of claim 5 further comprising steering a multicast request for a supercluster to a bounce back point within the multistage interconnect network, wherein all multicast requests to the supercluster use the same bounce back point.

7. The method of claim 6 further comprising steering a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster within the multistage interconnect network.

8. The method of claim 6 further comprising permitting only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.

9. A system for transmitting messages, comprising:

(a) a plurality of switch nodes connected together in a multistage interconnect network using forward channel and back channel signal paths therebetween; and

(b) means for multicast transmitting forward channel messages from a source connected to the multistage interconnect network to one or more destinations connected to the multistage interconnect network; and

(c) means for combining back channel replies received from the destinations into a single result, wherein the result is transmitted on the back channel to the source.

10. The system of claim 9 further comprising means for steering a multicast request for a supercluster to a bounce back point within the network, wherein all multicast requests to the supercluster use the same bounce back point.

11. The system of claim 10 further comprising means for steering a multicast request from one supercluster to a destination supercluster through a bounce back point for the destination supercluster.

12. The system of claim 10 further comprising means for permitting only one multicast request at a time within a supercluster, thereby preventing deadlock between competing multicast requests.