Title

A Fast Parallel Algorithm for Routing in Permutation Networks

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)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.

Rights Information

© 1981 Institute of Electrical and Electronics Engineers

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.