Single-Stage Networks

Figure 2.4: The different settings of the $2 \times 2$ SE.

• In this case, a single stage of switching elements (SEs) exists between the inputs and the outputs of the network.
• The simplest switching element that can be used is the $2 \times 2$ switching element (SE). Figure 2.4 illustrates the four possible settings that an SE can assume.
  1. Straight; the upper input is transferred to the upper output and the lower input is transferred to the lower output.
  2. Exchange; the upper input is transferred to the lower output and the lower input is transferred to the upper output.
  3. Upper-broadcast; the upper input is broadcast to both the upper and the lower outputs.
  4. Lower-broadcast; the lower input is broadcast to both the upper and the lower outputs.
• To establish communication between a given input (source) to a given output (destination), data has to be circulated a number of times around the network.
• A well-known connection pattern for interconnecting the inputs and the outputs of a single-stage network is the Shuffle-Exchange.
  • Two operations are used.
    1. Shuffle; $S(p_{m-1}p_{m-2} \ldots p_1p_0)=p_{m-2} \ldots p_1p_0p_{m-1}$
    2. Exchange; $E(p_{m-1}p_{m-2} \ldots p_1p_0)=p_{m-1}p_{m-2} \ldots p_1\overline{p_0}$
    With shuffle (S) and exchange (E) operations, data is circulated from input to output until it reaches its destination.
  • If the number of inputs, for example, processors, in a single-stage IN is N and the number of outputs, for example, memories, is N, the number of SEs in a stage is N/2. The maximum length of a path from an input to an output in the network, measured by the number of SEs along the path, is $log_2^N$.
• Example: In an 8-input single stage Shuffle-Exchange if the source is $0(000)$ and the destination is $6(110)$, then the following is the required sequence of Shuffle/ Exchange operations and circulation of data:
  $$E(000)\rightarrow 1(001) \rightarrow S(001) \rightarrow 2(010) \rightarrow E(010)\rightarrow 3(011) \rightarrow S(011) \rightarrow 6(110)$$
  The network complexity of the single-stage interconnection network is $O(N)$ and the time complexity is $O(N)$.
• In addition to the shuffle and the exchange functions, there exist a number of other interconnection patterns that are used in forming the interconnections among stages in interconnection networks. Among these are the Cube and the Plus-Minus $2^i$ (PM2I) networks.