# does routing work on Perfect Shuffle Benes Network?

For practice I constructed a Perfect Shuffle Benes Network (meaning I applied the Definition from Slide 97 of the chapter on Interconnection networks with Perfect shuffle as the permutation pi)

Then I tried routing via the looping algorithm and it failed. I also couldn't apply iterative Clos routing, as Perfect Shuffle maps the first to addresses 111 and 110 (I did the Benes network with 8 inputs) to 111 and 101 respectively, which are both in the upper of the two recursive Benes network.

So do all our results regarding Benes networks only apply to the Benes Networks constructed via iterative Clos Networks and the Butterfly Benes Network (or even just one of them), and not the generalized Benes Networks from slide 97?

Short answer: Yes, the looping algorithm assumes that your Benes network uses a certain permutation since it is assumed that one output of the 2x2 switches on the left column is sent to the upper middle switch and the other one is sent to the lower middle switch. Moreover, it is assumed that the 2x2 switches on the right hand column take an input from the upper middle switch and the other from the lower middle switch.

Longer answer: The looping algorithm is derived from the iterated Clos routing, and therefore assumes that the Benes network is an iterated Clos network. That in turn implies that the permutation used for the recursive construction is the one used by the Clos network.

Which one is this? Have a look at the following: The iterated Clos network has 2x2 switches in the left and right column and two n/2 x n/2 Benes networks in the middle column. Consider the outgoing addresses (a[p-1],...,a[0]) and (a[p-1],...,¬a[0]) given as binary numbers of a 2x2 switch in the left column (note that they differ in the least significant bit a[0] since one is even and the other one is odd). In a Clos network each switch on the left hand side has a connection to each switch in the middle column. In our case, (a[p-1],...,a[1],1) is connected to address (1,a[p-1],...,a[1]) at the upper switch and (a[p-1],...,a[1],0) is connected to address (0,a[p-1],...,a[1]) of the lower switch. Hence, we have a flip shuffle permutation on the left that maps (a[p-1],...,a[0]) to (a[0],a[p-1],...,a[1]). The permutation between the middle switches and the right hand side switches is a perfect shuffle that is the inverse of the one on the left hand side.

So, the recursive construction for Benes networks based on the Clos networks, implicitly enforces the use of a these permutations. The routing algorithms were designed for these, and there is no reason to believe that they will also work for other permutations.

In general, for the construction of interconnection networks, the used permutations matter! You have seen the same for the Omega-network that uses the perfect shuffle permutation. If you use the butterfly permutation instead, it will loose its power since then not every input can be routed to every output anymore. And clearly, if you would use the identity permutation, most networks become useless. So, the kind of permutation used really matters.

For routing Benes networks with the looping algorithm, the important property is that the addresses (a[p-1],...,a[0]) and (a[p-1],...,¬a[0]) of a 2x2 switch are mapped to addresses of the lower and upper middle switch and the inverse should be done on the right hand side. As explained above flip shuffle on the left and perfect shuffle on the right will do. Butterfly, which is self-inverse, can also be used on both sides: Since it maps (a[p-1],...,a[0]) to (a[0],a[p-2],...,a[1],a[p-1]), it also maps the outputs of each 2x2 switch on the left to the upper and lower switches in the middle. The perfect shuffle does not do that and therefore cannot be used in this setting. This does however not yet imply that a Benes network based on the perfect shuffle would be blocking.
by (166k points)
edited by