A Fast Parallel Algorithm for Routing in Permutation Networks

Authors

Gavriela Freund Lev, University of Edinburgh
Nicholas Pippenger, Harvey Mudd CollegeFollow
Leslie G. Valiant, Harvard University

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1981

Abstract

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)²) (for one processor with random access to a memory of O(n) words) or parallel time O((log n)³) (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.

Rights Information

© 1981 Institute of Electrical and Electronics Engineers

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1109/TC.1981.6312171

Recommended Citation

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