Multistage interconnection networks (MINs) are a class of high-speed computer networks usually composed of processing elements (PEs) on one end of the network and memory elements (MEs) on the other end, connected by switching elements (SEs). The switching elements themselves are usually connected to each other in stages, hence the name.
MINs are typically used in high-performance or parallel computing as a low-latency interconnection (as opposed to traditional packet switching networks), though they could be implemented on top of a packet switching network. Though the network is typically used for routing purposes, it could also be used as a co-processor to the actual processors for such uses as sorting; cyclic shifting, as in a perfect shuffle network; and bitonic sorting.
Interconnection network are used to connect nodes, where nodes can be a single processor or group of processors, to other nodes.
Interconnection networks can be categorized on the basis of their topology. Topology is the pattern in which one node is connected to other nodes.
There are two main types of topology: static and dynamic.
Static interconnect networks are hard-wired and cannot change their configurations. A regular static interconnect is mainly used in small networks made up of loosely couple nodes. The regular structure signifies that the nodes are arranged in specific shape and the shape is maintained throughout the networks.
Some examples of static regular interconnections are:[1] [2]
In dynamic interconnect networks, the nodes are interconnected via an array of simple switching elements.[3] This interconnection can then be changed by use of routing algorithms, such that the path from one node to other nodes can be varied. Dynamic interconnections can be classified as:
In crossbar switch, there is a dedicated path from one processor to other processors. Thus, if there are n inputs and m outputs, we will need n*m switches to realize a crossbar.
As number of outputs increase, number of switches increases by factor of n. For large network this will be a problem. An alternative to this scheme is staged switching.
In a single stage interconnect network, the input nodes are connected to output via a single stage of switches.
The figure shows 8*8 single stage switch using shuffle exchange.As one can see, from a single shuffle, not all input can reach all output. Multiple shuffles are required for all inputs to be connected to all the outputs.
A multistage interconnect network is formed by cascading multiple single stage switches. The switches can then use their own routing algorithm or controlled by a centralized router, to form a completely interconnected network.
Multistage Interconnect Network can be classified into three types:[4]
The number of switching elements required to realize a non-blocking network in highest, followed by rearrangeable non-blocking. Blocking network uses least switching elements.
Multiple types of multistage interconnection networks exist.
See main article: article and Omega network. An Omega network consists of multiple stages of 2*2 switching elements. Each input has a dedicated connection to an output. An N*N omega network has log(N) number of stages and N/2 number of switching elements in each stage for perfect shuffle between stages. Thus network has complexity of 0(N log(N)). Each switching element can employ its own switching algorithm. Consider an 8*8 omega network. There are 8! = 40320 1-to-1 mappings from input to output. There are 12 switching element for total permutation of 2^12 = 4096. Thus, it is a blocking network.
See main article: article and Clos network. A Clos network uses 3 stages to switch from N inputs to N outputs. In the first stage, there are r= N/n crossbar switches and each switch is of size n*m. In the second stage there are m switches of size r*r and finally the last stage is mirror of first stage with r switches of size m*n. A clos network will be completely non-blocking if m >= 2n-1. The number of connections, though more than omega network is much less than that of a crossbar network.
A Beneš network is a rearrangeably non-blocking network derived from the clos network by initializing n = m = 2. There are (2log(N) - 1) stages, with each stage containing N/2 2*2 crossbar switches. An 8*8 Beneš network has 5 stages of switching elements, and each stage has 4 switching elements. The center three stages has two 4*4 benes network. The 4*4 Beneš network, can connect any input to any output recursively.