Multistage interconnect network uses a master processor to...

Details Multistage interconnect network uses a master processor to... Multistage interconnect network uses a master processor to...

1998-11-10

2001-06-05

Luu, Le Hien (Department: 2152)

Multiplex communications

Network configuration determination

C370S255000

Reexamination Certificate

active

06243361

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to computer networks, and in particular to a scalable multi-stage interconnect network
14
for multiprocessor computers.
2. Description of Related Art
Parallel processing is considered an advantageous approach for increasing processing speeds in computer systems. Parallel processing can provide powerful communications and computer systems which can handle complex problems and manipulate large databases quickly and reliably.
One example of parallel processing can be found in U.S. Pat. No. 4,412,285, issued Oct. 25, 1983, to Neches et al., incorporated by reference herein. This patent describes a system using a sorting network to intercouple multiple processors so as to distribute priority messages to all processors.
Further examples of parallel processing can be found in U.S. Pat. No. 4,445,171, issued Apr. 24, 1984, to Neches, U.S. Pat. No. 4,543,630, issued Sep. 24, 1985, to Neches, and U.S. Pat. No. 4,814,979, issued Mar. 21, 1989, to Neches, all of which are incorporated by reference herein. These patents describe a multiprocessor system which intercouples processors with an active logic network having a plurality of priority determining nodes. Messages are applied concurrently to the network in groups from the processors and are sorted, using the data content of the messages to determine priority, to select a single or common priority message which is distributed to all processors with a predetermined total network delay time.
Communication within parallel processing systems such as those described above is typically classified as either tightly coupled wherein communication occurs through a common memory or loosely coupled wherein communication occurs via switching logic and communications paths. Various topologies and protocols for loosely coupled processors have been proposed and used in the prior art. These topologies tend to be grouped into two categories: static and dynamic.
Static topologies provide communication paths between processors which cannot be reconfigured. Examples of static topologies include linear arrays, rings, stars, trees, hypercubes, etc.
Dynamic topologies permit dynamic reconfiguration of communication paths between processors using switching elements within the network. Examples of dynamic topologies include single stage networks and multistage interconnect networks (MINs).
A single stage network has one stage of switching elements such that information can be re-circulated until it reaches the desired output port. A MIN has a plurality of switching element stages capable of connecting any input port of the network to any output port.
In general, MINs consist of several stages of switching elements or switch nodes that are wired together according to a regular pattern. Typically, each switch node is a small crossbar switch that usually has an equal number of inputs and outputs, e.g., a b×b switch node. Prior art MINs typically consist of log
b
N stages, wherein b is the number of input/output ports of a switch node, and N is the number of input/output ports of a network typically, such MINs are therefore constructed from the smallest number of links and switch nodes that allows any network input port to be connected to any network output port.
Prior attempts at implementing MINs suffer from several disadvantages. One disadvantage arises because each network input/output port pair typically has only one way to be connected, thereby making the MIN susceptible to internal contention. Internal contention occurs when two paths require the same link even though the paths may or may not be to the same network output port.
Another disadvantage is lessened reliability due to the number and complexity of components. If a fault occurs, it is often difficult to determine where the problem lies. Further, it may be impossible to reconfigure the system to exclude the failed component or service the system without shutting it down, thereby leaving the system inoperable until the problem is corrected.
Another disadvantage is complex, expensive, and time-consuming manufacturing and installation requirements. For large network configurations, cabling may be unmanageable due to the logistics of making sure every component is correctly cabled and plugged into the correct connector.
Still another disadvantage involves diminishing bandwidth. The bandwidth available to each processor tends to decrease as the system size grows.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses 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 b×b switch nodes arranged in |log
b
N|+1 (or more) stages, wherein b is the number of input/output ports of a switch node, N is the number of input/output ports of a network, 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.
The present invention provides numerous advantages. One advantage is reliability. The system is designed to keep working even when components fail by automatically reconfiguring itself when a fault is detected.
Still another advantage is serviceability. The error reporting method isolates faults to prevent them from propagating throughout the network.
Still another advantage is manufacturability. For large system configurations, cabling could be very unmanageable. However, the design of the present invention, along with flexible cable connection rules, ,make the problem tractable for large systems and nonexistent for small systems.
Still another advantage is simple installation. Any processor can be plugged into any available receptacle. This eliminates a source of errors by dropping the need to make sure every cable is plugged into the correct connector. All other systems we know of have this cabling constraint.
Still another advantage is high performance per processor. The high connectivity topology, extra stages of switch nodes, back-off capability, pipelining operation, back channel, and multicast window features combine to provide a high speed connection capability for each processor regardless of the number of processors in the system. In other systems, the bandwidth available to each processor ends to decrease as the system size grows.


REFERENCES:
patent: 3290446 (1966-12-01), Ceonzo
patent: 3317676 (1967-05-01), Ekbergh et al.
patent: 3491211 (1970-01-01), Bininda et al.
patent: 3581286 (1971-05-01), Beausolell
patent: 3582560 (1971-06-01), Banks
patent: 3693155 (1972-09-01), Crafton et al.
patent: 3963872 (1976-06-01), Hagstrom et al.
patent: 4022982 (1977-05-01), Hemdal
patent: 4038638 (1977-07-01), Hwang
patent: 4074072 (1978-02-01), Christensen et al.
patent: 4075693 (1978-02-01), Fox et al.
patent: 4081612 (1978-03-01), Hafner
patent: 4146749 (1979-03-01), Pepping et al.
patent: 4173713 (1979-11-01), Giesken
patent: 4177514 (1979-12-01), Rupp
patent: 4201889 (1980-05-01), Lawrence et al.
patent: 4201891 (1980-05-01), Lawrence et al.
patent: 4237447 (1980-12-01), Clark
patent: 4247892 (1981-01-01), Lawrence
patent: 4251879 (1981-02-01), Clark
patent: 4307446 (1981-12-01), Barton et al.
patent: 4317193 (1982-02-01), Joel, Jr.
patent: 4344134 (1982-08-01), Barnes
patent: 4347498 (1982-08-01), Lee et al.
patent: 4412285 (1983-10-01), Neches et al.
patent: 4417244 (1983-11-01), Melas
patent: 4417245 (1983-11-01), Melas
patent: 4445171 (1984-04-01), Neches
patent: 4456987 (1984-06-01), Wirsing
patent: 4466060 (1984-08-01), Riddle
patent: 4481623 (1984-11-01), Clark
p

Affiliated with

Also associated with

Rating

Multistage interconnect network uses a master processor to... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multistage interconnect network uses a master processor to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multistage interconnect network uses a master processor to... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2463097