Multistage Networks

Figure 2.5: Multistage interconnection network and an example $8 \times 8$ Shuffle-Exchange network (SEN).

• Multistage interconnection networks (MINs) were introduced as a means to improve some of the limitations of the single bus system (to improve is the availability of only one single path) while keeping the cost within an affordable limit.
• Such MINs provide a number of simultaneous paths between the processors and the memory modules (see Fig. 2.5a).
• A general MIN consists of a number of stages each consisting of a set of $2 \times 2$ switching elements. Stages are connected to each other using Inter-stage Connection (ISC) Pattern. These patterns may follow any of the routing functions such as Shuffle-Exchange, Butterfly, Cube, and so on.
• Figure 2.5b shows an example of an $8 \times 8$ MIN that uses the $2 \times 2$ SEs described before. This network is known in the literature as the Shuffle-Exchange network (SEN).
• The figure shows how three simultaneous paths connecting the three pairs of input/output $000 \longrightarrow 101$, $101 \longrightarrow 011$, and $110 \longrightarrow 010$ can be established. It should be noted that the interconnection pattern among stages follows the shuffle operation.
• In MINs, the routing of a message from a given source to a given destination is based on the destination address (self-routing). There exist $log_2 N$ stages in an $N \times N$ MIN.
• The number of bits in any destination address in the network is $log_2 N$. Each bit in the destination address can be used to route the message through one stage. The destination address bits are scanned from left to right and the stages are traversed from left to right.
• The first (most significant bit) is used to control the routing in the first stage; the next bit is used to control the routing in the next stage, and so on. The convention used in routing messages is that if the bit in the destination address controlling the routing in a given stage is 0, then the message is routed to the upper output of the switch. On the other hand if the bit is 1, the message is routed to the lower output of the switch.
• Consider, for example, the routing of a message from source input 101 to destination output 011 in the $8 \times 8$ SEN shown in Figure 2.5b. Since the first bit of the destination address is 0, therefore the message is first routed to the upper output of the switch in the first (leftmost) stage. Now, the next bit in the destination address is 1, thus the message is routed to the lower output of the switch in the middle stage. Finally, the last bit is 1, causing the message to be routed to the lower output in the switch in the last stage.

  Figure 2.6: Multistage interconnection network and an example $8 \times 8$ Shuffle-Exchange network (SEN).
• The Banyan Network; A number of other MINs exist, among these the Banyan network is well known (see Fig. 2.6a, an example of an $8 \times 8$ Banyan network ).
• If the number of inputs, for example, processors, in an MIN is N and the number of outputs, for example, memory modules, is N, the number of MIN stages is $log_2 N$ and the number of SEs per stage is $N/2$, and hence the network complexity, measured in terms of the total number of SEs is $O(Nlog_2 N)$.
• The time complexity, measured by the number of SEs along the path from input to output, is $O(log_2 N)$. For example, in a $16 \times 16$ MIN, the length of the path from input to output is 4.
• The total number of SEs in the network is usually taken as a measure for the total area of the network. The total area of a $16 \times 16$ MIN is 32 SEs.
• The Omega Network; The Omega Network represents another well-known type of MINs. A size N omega network consists of n ($n=log_2 N$ single-stage) Shuffle-Exchange networks. Each stage consists of a column of N=2, two-input switching elements whose input is a shuffle connection. (Figure 2.6b illustrates the case of an $N=8$ Omega network.
• As can be seen from the figure, the inputs to each stage follow the shuffle interconnection pattern. Notice that the connections are identical to those used in the $8 \times 8$ Shuffle-Exchange network (SEN) shown in Fig. 2.6a.
• Owing to its versatility, a number of university projects as well as commercial MINs have been built. These include the Texas Reconfigurable Array Computer (TRAC) at the University of Texas at Austin, the Cedar at the University of Illinois at Urbana-Champaign, the RP3 at IBM, the Butterfly by BBN Laboratories, and the NYU Ultracomputer at New York University.
• The NYU Ultracomputer is an experimental shared memory MIMD architecture that could have as many as 4096 processors connected through an Omega MIN to 4096 memory modules.
• The MIN is an enhanced network that can combine two or more requests bound for the same memory address. The network interleaves consecutive memory addresses across the memory modules in order to reduce conflicts in accessing different data elements.
• The switch nodes in the NYU Ultracomputer are provided with queues (queue lengths of 8 to 10 messages) to handle messages collision at the switch. The system achieves one-cycle processor to memory access.