Multistage Interconnection Network Design for Engineers

Tremendous advancements have been reported in the computer and communication industries due to the high demands of big data analysis. This led to the use of parallel and distributed processors to play a part. These parallel processors have to be connected to a large number of memory modules. The connection between these processors and memory modules must be highly reliable for efficient big data analysis. Multistage interconnection networks (MIN) provide data communication between processors and memory modules at efficient speed with reasonably high reliability. This chapter provides a detailed introduction to MINs with their evolution and characterization. Further in this chapter, the research trends among researchers about various classes of MINs have also been discussed.

The shuffle exchange network is known to be the simplest MIN with a modest size of switching element in use. It is a unique path MIN with no fault tolerance. Researchers have explored this network to take advantage of its modest size and low cost and tried to improve its reliability by providing redundancy in its basic structure. While improving the fault tolerance of this network, many techniques have been proposed in the literature which are comprised of increasing the hardware complexity of the network. Recently, a new method has been proposed to improve fault tolerance which consists of using multiplexers and demultiplexers at the input and output stages of the network. It has been claimed that it improves the reliability on one hand and reduces the overall cost of the network on the other hand. In this chapter, this technique has been explored and reliability analysis of the network has been presented thoroughly to provide deep insight into the performance of the network. 

Gamma interconnection network is a fault-tolerant MIN with multipath characteristics. Even though the gamma interconnection network has a multipath between every source and every destination, it has the critical flaw of acting as a single path MIN when the source address and destination address are the same. Hence, it is important to modify such a prominent candidate so as to provide multiple paths in every case, several modifications have been suggested by the researchers in the literature. One such modification is fascinating as it provides multiple paths for every case at a reduced cost. At the input and output stages, multiplexers and demultiplexers are used to do this. The system is referred to as Gamma-Minus MIN. This chapter includes further performance characteristics with the reliability assessment of GammaMinus MIN

It has been proved that the use of multiplexers and demultiplexers of the smallest size has improved reliability to an extent but the effect of using bigger-sized MUX and DEMUX on reliability and fault tolerance must also be evaluated. In the recent past, the consequences of using higher-sized MUXs and DEMUXs have been explored and presented in this chapter. The full analysis of the size of MUXs and DEMUXs to be used so as to increase the reliability of the network to the optimum level has been presented. The analysis done on SEN MIN shows that the best size of MUXs and DEMUXs to be used is 4×1 and 1×4 respectively and hence the SEN MIN with 4×1 MUX and 1×4 DEMUX is named Fault Tolerance SEN MIN (FTSM). 

The gamma interconnection network is a reliable network that provides redundancy in its basic topology but fault tolerance is still an issue to be addressed. Although the usage of MUX and DEMUX lessens the issue in gamma MIN's unique path behavior when the tag value is zero, it is still necessary to investigate the ideal size of MUX and DEMUX which may be used with gamma MIN in order to give the highest level of reliability. In order to make an overall generalization about all MINs, it is crucial to determine whether the findings achieved for the SEN MIN apply to other MINs that use switching elements of varying sizes. This chapter evaluates and presents the impact of larger MUX and DEMUX sizes on gamma MIN. The results of the evaluations show that the 4x1 MUX and 1×4 DEMUX provide the maximum level of dependability and that increasing the size of the MUX and DEMUX lowers the reliability to cost ratio.

It has been shown in the previous chapters that SEN and gamma interconnection network are the best-known MIN and are highly explored in the literature. It would be interesting to make a hybrid network comprising combined characteristics of both networks. Few research works are available in the literature which have explored this interesting topic and reliability evaluations have also been presented. These networks are known as SEGIN and SEGIN-Minus MIN. In this chapter, detailed reliability analyses of both networks have been presented and it is shown that SEGIN-Minus MIN has better performance characteristics than the SEGIN network.