A fast parallel algorithm for routing in permutation networks

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.