SP10077 ROUTING - Routing

You work as an engineer for the _Inane Collaboration for Performance Computing_, where you are in charge of designing an intercommunication network for their computers. The network is arranged as a rectangular array of 2_n_−1 rows, each having 2 $ ^{n − 1} $ switches. A switch is a device with two input wires, _X_ and _Y_, and two output wires, _X_′ and _Y_′. If the switch is off, data from input _X_ will be relayed to output _X_′, and data from _Y_ to _Y_′. If it is on, _X_ will be connected to _Y_′ and _Y_ to _X_′. Additionally, there are 2 $ ^{n} $ computers in the topmost and bottommost rows, and messages need to be sent between pairs of them. Notice that data from two different sources cannot share a wire but, of course, both pieces of data can be routed through the same switch on different inputs. You have come to the conclusion that the network that best suits your purposes has the Beneš topology. A 1-Beneš network is just a switch. For _n_ > 1, a _n_-Beneš network can be constructed recursively as follows: - In the first (top) row there are 2 $ ^{n − 1} $ switches such that switch _j_ (0 j < 2 $ ^{n−1} $ ) has data inputs from computers 2_j_ and 2_j_ + 1 (we label the computers in the topmost and bottommost rows with integers between 0 and 2 $ ^{n} $ − 1, inclusive, from left to right). - Then a _perfect shuffle_ permutation is applied to the output wires between the first and the second rows of switches, meaning that output number _j_ in a row is connected to input number _j_′ in the next row, where _j_′ is obtained by rotating the n-bit pattern representing _j_ in binary one bit to the right (again, inputs and outputs are numbered from left to right). - If _n_ > 2, the next rows of switches, up to (and including) the last-but-one, form two (_n_−1)-Beneš subnetworks, one on the left side and the other on the right side. - Finally, the _inverse_ shuffle permutation is applied to the outputs and a last row of switches is added. > - - - - - -

N/A

N/A