DCMIN - A NEW INTERCONNECTION NETWORK TOPOLOGY FOR PARALLEL PROCESSING

Abstract

This dissertation addresses the problem of designing a reliable and computationally faster interconnection network with reduced complexity compared to the conventional multistage networks. The importance of 4-shuffle interconnection pattern for the problems requiring concurrent processing has been demonstrated. A 4x4 switch named as Dual Interconnection Modular Switching Element (DIMSE) has been proposed as an alternative to 2x2 switching element for use in Multistage Interconnection Networks (MINs). Design of a new MIN topology, designated as Dual Cube Multistage Interconnection Network (DCMIN), for use in parallel processing environments, has been proposed. The performance and complexity of DCMIN has been evalua ted and compared with the conventional cube type MINs. It has been established that in addition to being less complex and computationally faster, the DCMIN is also cost-effective. Con ventional routing algorithms and relatively simpler faultdiagnosis techniques can be readily made applicable to DCMIN. Fault-tolerance capability of the proposed network is evaluated using multiple-paths through an extended topology of DCMIN called EDCMIN and multiple-passes techniques. Asimple and elegant analytic model of DCMIN,using Kronecker product of matrices of DIMSEs, has been devised. DCMIN topology has the partitioning property, i.e., the network can be implemented in partitionable SIMD/MIMD environments as well.