Multiprocessor computer system

• US 5,303,383 A
• Filed: 08/14/1992
• Issued: 04/12/1994
• Est. Priority Date: 05/01/1991
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Neches, Philip M., McMillen, Robert J., Watson, M. Cameron, Chura, David J.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US07/900,731
• Time in Patent Office: 606 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/200, 395/250, 395/325, 395/600, 395/700, 395/800
• US Class Current: 712/43
• 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 multiprocessor system, comprising:

(a) a plurality of processors;

(b) a network for connecting the processors, wherein the network comprises a plurality of switch nodes arranged into more than log_b N switch node stages, wherein b is a total number of switch node input/output ports, N is a total 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 switch node stages thereby providing a plurality of paths between any network input port and network output port to enhance fault tolerance and lessen contention, the switch node stages being configured to provide a plurality of bounce-back points at a highest switch node stage of the network for directing transmissions of messages through the network, the bounce-back points logically differentiating between switch nodes that load balance messages through the network from switch nodes that direct messages to receiving processors;

(c) means for partitioning the processors into one or more superclusters comprising logically independent subsets of processors; and

(d) means for multicast communicating within superclusters by steering a multicast message to a particular bounce-back point in the network for subsequent routing to the processors in the supercluster, thereby preventing deadlock in the network by permitting only one multicast message through the particular bounce-back point at a time and preventing multicast messages to different superclusters from interfering with each other.

2. The multiprocessor system of claim 1, wherein the means for multicast communicating comprises means for coordinating activities of the processors in the supercluster using the multicast message.

3. The multiprocessor system of claim 2, wherein the means for coordinating comprises means for receiving status information for the processors in the supercluster at the single transmitting processor.

4. The multiprocessor system of claim 1, wherein the supercluster is comprised of all processors in the system, so that a single transmitting processor can establish a connection to all other processors by multicast communicating to the supercluster.

5. The multiprocessor system of claim 1, wherein the means for multicast communicating comprises means for communicating between superclusters by transmitting a multicast message from a single transmitting processor outside the supercluster to the bounce-back point for the supercluster.

6. The multiprocessor system of claim 1, further comprising means for communicating between processors through the network via the bounce-back points in a point-to-point mode, wherein a plurality of point-to-point communications between different pairs of processors can occur through the network at the same time.