Author: Shilpa Gupta

Multistage Interconnection Network Design for Engineers

eBook: US $39 Special Offer (PDF + Printed Copy): US $74
Printed Copy: US $54
Library License: US $156
ISBN: 978-981-5165-35-7 (Print)
ISBN: 978-981-5165-34-0 (Online)
Year of Publication: 2023
DOI: 10.2174/97898151653401230101


This textbook provides a quick and easy understanding of multistage interconnection networks (MINs) for engineers. The book contents focus on the design, performance metrics, and evaluation of these networks which are crucial in modern computer architecture. The contents equip engineering students, apprentices and professionals with in-depth knowledge and analysis of MINS, enabling them to build complex computer architectures for efficient data communications and cost effective solutions for circuit design. The book starts with an introduction to MINS and subsequently progresses to the evaluation of a range of MINS (SEN, Gamma-Minus, FTSN, FTGN, SEGIN).

Key highlights of the book include:

  • - Easy to understand notes on design, reliability and fault tolerance
  • - Covers a wide range of MIN types with notes on design variants
  • - Supplementary information aiding comprehension of the main content.
  • - A curated list of references for further exploration and deeper understanding.


Graduate-level students, engineers and researchers working on embedded systems design and network design.


In order to meet the demanding needs of ever-increasingly computationally intensive applications, such as SCADA, power distribution and management with prior load prediction, plasma dynamics for fusion energy applications, electronic structure calculations for the design of new materials and their characterization, fluid dynamics, the study of turbine behavior for electricity generator, weather prediction, and global climate change, military surveillance, symbolic computations, data mining for modeling business and financial processes, ocean sciences, enhanced oil and gas recovery, airbus design, nuclear weapon detonation, etc., Big Data Analysis must be conducted for these applications from several nodes dispersed across various locations. Fast calculation and communication are needed for this big data, which are made possible by the numerous processors connected to supercomputers.

The implementation of the switching fabric of high-capacity communication processors, such as ATM switches, gigabit Ethernet switches, and terabit routers, is also becoming more commonplace. MINs are frequently used in the context of SIMD (single-instruction multiple-data) and MIMD (multiple-instruction multiple-data) parallel machines. For instance, the nodes of the CARY X-MP and IBMSP series are typically connected using MINs. Real-world examples of practical applications that use MINs for communication include ATM Switches, the Butterfly parallel processor, the IBM SP series, the IBM research prototype RP3, AMD64, SPARC, MIPS, PA-RISC, Alpha, STARAN by Goodyear Aerospace Corporation, Ethernet switches and routers, IBM Power microprocessors, and the NYU ultra-computer.

The interconnection of these supercomputers' component parts, such as the processor and their memory modules, is crucial for the reliable operation of the system. Multistage Interconnection Networks (MIN) are typically used as interconnection systems for these frameworks due to the growing number of processors in supercomputer systems. MINs consist of multiple stages of a small interconnection network known as SE connected in a predefined connection pattern. MIN provides a compromise between a highly efficient and expensive crossbar network and a bus network, which is very cost-effective but at the same time, it provides data communication at very slow rates. MIN not only provides efficient communication at low cost but it also offers high fault tolerance capability, availability of multiple paths, high bandwidth, throughput, etc. Therefore, since MIN's development, researchers have been quite interested in finding ways to improve its reliability.

A lot of designs based on regular (uniform connection pattern between stages and a number of Switching Elements (SE) are also the same in each stage) and irregular (non-uniform connection pattern between stages and number of SE are also not same in each stage) MIN topologies have been proposed in the last five decades. During the last three decades, regular rectangular (number of input and output nodes are same) MIN, primarily the Gamma Interconnection Network (GIN) and the Shuffle Exchange Network (SEN), by offering numerous routes between each Source-Destination (SD) node pair, have been investigated and improved. The majority of the improvements were made by adding more hardware (either by expanding the size or quantity of SE per stage or by expanding the number of stages). Despite the fact that SEN and GIN have received a lot of attention, there are following points that need to be highlighted. (i) Literature on these topics lacks organization and classification; (ii) certain aspects, such as complexity, cost, the number of disjoint pathways under the assumption that the source and destination are fault-free, low latency, high bandwidth and throughput, CPU usage, etc., remain to be investigated; (iii) hardware reduction (number of SE/Stages); (iv) less research has been done on all three reliability evaluation metrics, including fault tolerance, network reliability (NR), broadcast reliability (BR), and terminal reliability (TR), for networks larger than 8×8.

In this book, these issues have been discussed and resolved by presenting the (i) Classification of SEN and GIN, (ii) A method based on using MUX and DEMUX of various sizes such as 2×1/1×2, 4×1/1×4 etc. at input and output stages respectively; (iii) Suggestions on connection patterns for MUX and DEMUX at input and output stages, respectively and (iv) design of MIN with fewer stages and more entirely isolated pathways.

Shilpa Gupta
Electrical and Electronics Engineering Department
Maharaja Agrasen University