Multistage interconnection networks
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 connection 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:
- Shared bus
In dynamic interconnect networks, the nodes are interconnected via an array of simple switching elements. 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:
- Single stage Interconnect Network
- Multistage interconnect Network
- Crossbar switch connections
Crossbar Switch Connections
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.
Single Stage Interconnect Network
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. We will need to do multiple shuffles for all inputs to be connected to all the outputs.
This will lead to development of multistage interconnect networks in the future.
Multistage Interconnect Network
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:
- Non-blocking: A non-blocking network can connect any idle input to any idle output, regardless of the connections already established across the network. Crossbar is an example of this type of network.
- Rearrangeable non-blocking: This type of network can establish all possible connections between inputs and outputs by rearranging its existing connections.
- Blocking: This type of network cannot realize all possible connections between inputs and outputs. This is because a connection between one free input to another free output is blocked by an existing connection in network.
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.
There are many types of MINs designed. Following are some of the most famous types of MINs:
- Solihin, Yan (2009). Fundamentals of Parallel Computer Architecture. USA: OmniPress. ISBN 978-0-9841630-0-7.
- Blake, J. T.; Trivedi, K. S. (1989-11-01). "Multistage interconnection network reliability". IEEE Transactions on Computers. 38 (11): 1600–1604. doi:10.1109/12.42134. ISSN 0018-9340.
- "Interconnection networks in multiprocessor systems".
- "Multistage interconnection networks" (PDF).