A Kind of Multistage Interconnection Networks with Multiple Paths

Mltistage Interconnection Networks(MINs)are orten used to provide interconnections in multiprocessor systems.A unique path MIN usually has lower hardware complexity and a simple control algorithm,but it lacks fault tolerance.This paper proposes a kind of multipat MINs,which are obtained by adding auxiliary links at the final stage in Quad Tree(QT) networks so that they can provide more paths between each source-destination pair,and presents their routing algorithm which is both destination tag based and adaptive.Starting with the routing tag for the minimum path between a given source-destination pair,the routing algorithm uses a set of rules to select switches and modify routing tag.In addition to trying the auxiliary link when link0 an link1 are unavilable,link1 will be tried when link0 ys unavailable.This feature distinguishing the proposed routing algorithm form that for QT networks makes better 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 MINs have better capacity than QT networks.