An optimal algorithm for permutation admissibility to multistage interconnection networks

Abstract

This paper introduces a simple O(NlogN) sequential algorithm that determines the admissibility of an arbitrary permutation to an N/spl times/N Multistage Cube-Type Network (MCTN) implemented by 2/spl times/2 switching elements (SEs) in contrast to previous O(Nlog/sup 2/N) algorithms. It is proven that the new algorithm is optimal in the sense that any algorithm, based on bit-operations, has to examine at least (N/4)logN different bits among the total NlogN bits in the binary representations of the destinations numbered from 0 through N-1.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>