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.
Cited by 256 works. doi:10.1109/tc.1981.6312171
Authors
References
- Sorting networks and their applications
- Parallel Processing with the Perfect Shuffle
- Mathematical Theory of Connecting Networks and Telephone Traffic
- Fast probabilistic algorithms for hamiltonian circuits and matchings
- A Permutation Network
- On Rearrangeable Three-Stage Connecting Networks
- Computing connected components on parallel computers
- On Relating Time and Space to Size and Depth
- New Parallel-Sorting Schemes
- On simultaneous resource bounds