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…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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 2 (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. 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.

A Beneš network is a rearrangeably non-blocking network derived from the clos network by initializing n = m = 2. There are (2log 2 (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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1346198942 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001346198942 · captured 2026-03-30 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Multistage interconnection networks”, snapshot enwiki-001346198942. https://encyclopegia.org/a/multistage-interconnection-networks

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.