The Selective Extra Stage Butterfly

Abstract

Multistage interconnection networks (MIN's) have been used extensively as communication networks in parallel machines due to their high bandwidth, low diameter and constant degree switches. The fault-tolerance of multistage networks can be improved by simply adding extra stages to the network. In this paper we suggest a novel method of attaching the extra stages in MIN's such that they are used in the absence of faults but not necessarily by all messages. Messages can adaptively select to take the shortest path towards their destination or use one of the longer paths going through the extra stages. We present performance results of our method, obtained through simulation, under various traffic loads both in the presence and absence of faults. © 1993 IEEE