A New Approach to Fast Control of Permutation Networks

Abstract:

Controlling Benes-Clos networks in full generality has proven to be very slow. Many approaches have been taken to speed up the control for certain classes of permutations. In this report, a new approach is developed for 3-stage networks with n x n switches as building blocks (denoted by B(n, 2)). The new approach allows the network to be self-routed for many interesting classes of problems, or more precisely, the permutations they need. The families of permutations that can be self-routed by the new scheme are characterized. Several problems such as FFT, bitonic sorting, simulation of standard fixed interconnection networks on B(n, 2), and others are shown to produce families of permutations that yield to the new scheme. A new control algorithm of O(log2 N) complexity is derived for B(n, 2) where N = n2 is the number of terminals, and possible implementation of the scheme is discussed.