A fast parallel algorithm for routing in permutation networks

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 time O ( n (log N ) 2 ) (for one processor with random access to a memory of O ( n ) words) or parallel time O ((log n ) 3 ) (for n synchronous processors with conflict-free random access to a common memory of O ( n ) words). These time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two.