A Kind of Multistage Interconnection Networks with Multiple Paths

1ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina,GralltNo.69473024.1IntroductionMultiprocessorsystemsoftenuseinterconnectionnetworkstoconnectproces-sorsormemorymodules-Atime-sharedbusisthesimplestformofinterconnectionnetworks,butitcannotprovidetheperformancerequiredinmultiprocessorsystemstoday.Acrossbarswitchnetworkisanalternativeusedintheearliersystemstoimplementinterconnection.Theonlydelaytoconnectinputstooutputsisthatofasingleswitchinggate,butacrossbarswitchnetworkisver…

A Kind of Multistage Interconnection Networks with Multiple Paths

Multistage Interconnection Networks (MINs) are often used to provide interconnections in multiprocessor systems. A unique path MIN usually has lower hardware complekity and a simple control algorithm, but it lacks fault tolerance.This paper proposes a kind of multipath MINs, which are obtained by adding auxiliary links at the final stage in Quad nee (QT) networks so that they canprovide more paths between each source-destination pair, and presents theirrouting algorithm which is both destination tag based and adaptive. Starting with the routing tag for the minimum path between a given source-destinationpair, the routing algorithm uses a set of rules to select switches and modifyrouting tag. In addition to trying the andliary link when linko and link1 areunavailable, link1 will be tried when link0 is unavailable. This feattire dis-tinguishing the proposed routing algorithm from that for QT networks makesbetter use of all the possible paths between the given source-destination pair.In the end, this paper introduces a performance index, which is called capacity,to compare different kinds of MINs. Comparison shows that the proposed MINshave better capacity than QT networks.