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.
© 1981 Institute of Electrical and Electronics Engineers
Lev, G.F.; Pippenger, N.; Valiant, L.G., "A fast parallel algorithm for routing in permutation networks," Computers, IEEE Transactions on , vol.C-30, no.2, pp.93,100, Feb. 1981 doi: 10.1109/TC.1981.6312171