A fast parallel algorithm for routing in permutation networks
G. Lev, Nicholas J. Pippenger, Leslie Gabriel Valiant · IEEE Transactions on Computers · 1981
An algorithm is given for routing in permutation networks-that is, for computing the switch settings that implement a given permutation. The algorithm takes serial timeO(n(logN)2) (for one processor with random access to a memory ofO(n) words) or parallel timeO((logn)3) (fornsynchronous processors with conflict-free random access to a common memory ofO(n) words). These time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two.