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.times.b switch node.  Prior art MINs typically consist of log.sub.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 maybe impossible to reconfigure the system to exclude the failed component or service he 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.