computer science

Multistage interconnection networks

Multistage interconnection networks is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Multistage interconnection networks rather than just read about it. In short: 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.

Key takeaways

Multistage interconnection networks belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Multistage interconnection networks to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Multistage interconnection networks from memory before moving on to harder problems.

Reference excerpt

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.

Background 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:

Completely connected network In a mesh network, multiple nodes are connected with each other. Each node in the network is connected to every other node in the network. This arrangement allows proper communication of the data between the nodes. But, there are a lot of communication overheads due to the increased number of node connections. Shared busThis network topology involves connection of the nodes with each other over a bus. Every node communicates with every other node using the bus. The bus utility ensures that no data is sent to the wrong node. But, the bus traffic is an important parameter which can affect the system. RingThis is one of the simplest ways of connecting nodes with each other. The nodes are connected with each other to form a ring. For a node to communicate with some other node, it has to send the messages to its neighbor. Therefore, the data message passes through a series of other nodes before reaching the destination. This involves increased latency in the system. TreeThis topology involves connection of the nodes to form a tree. The nodes are connected to form clusters and the clusters are in-turn connected to form the tree. This methodology causes increased complexity in the network. Hypercube This topology consists of connections of the nodes to form cubes. The nodes are also connected to the nodes on the other cubes. ButterflyThis is one of the most complex connections of the nodes. As the figure suggests, there are nodes which are connected and arranged in terms of their ranks. They are arranged in the form of a matrix. 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 the number of outputs increases, the 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. Multiple shuffles are required for all inputs to be connected to all the outputs.

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 be 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 the 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.

Examples Multiple types of multistage interconnection networks exist.

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 log2(N) stages and N/2 switching elements in each stage for a perfect shuffle between stages. Thus the 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 a total permutation of 2^12 = 4096. Thus, it is a blocking network.

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 a mirror of the 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.

Beneš network

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Multistage interconnection networks

Start with the simplest possible case. Write down what Multistage interconnection networks claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Multistage interconnection networks before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Multistage interconnection networks ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Multistage interconnection networks

In research: Multistage interconnection networks appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Multistage interconnection networks in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Multistage interconnection networks is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computer networks, Parallel computing, so understanding it makes those chapters shorter.
In everyday life: Look for Multistage interconnection networks outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Multistage interconnection networks in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Multistage interconnection networks means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Multistage interconnection networks out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Multistage interconnection networks in simple terms?

Why does Multistage interconnection networks matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Multistage interconnection networks?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Multistage interconnection networks.