Analysis of multistage interconnection networks
A.Y. Al-Hallaq · 1987
In the early 60's, Benes proved the existance of optimal rearrangeable networks. Since that time there are at least three different approaches to prove the rearrangeability of this class of networks. The first proof, is called Benes-Slepian-Duguid Theorem, the second proof, due to Benes (in 1975) and the third proof, due to Lee (in 1985). Benes in his paper in 1975 proved the equivalence of the first two proofs. In this work, we prove that the seemingly different proof due to Lee is in fact another version of Benes' proof based on a system of common representatives. A number of comments and open problems relating to rearrangeable networks are presented. There is a considerable literature on the analysis of the average bandwidth of a wide class of the blocking networks such as the Base-line network. These methods require certain assumptions such as independence, and uniformity of the destination tags across the various memory modules. Once the input to the network is generated, and since the routing algorithm is deterministic in nature, this type of average case does not shed light on what will happen to any specific random input. In this study, we present a generalized passability condition for random inputs and then a deterministic analysis of the behavior of these networks under random inputs. It is shown that the Base-line network is very robust and it can pass a variety of random inputs in much the same way as it can handle the set of passable permutations. Our study also shows that Benes rearrangeable network can indeed realize the average bandwidth of a complete Cross-bar.