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.
