Title :
An optimal algorithm for permutation admissibility to multistage interconnection networks
Author :
Shen, Xiaojun ; Xu, Mao ; Wang, Xiangzu
Author_Institution :
Comput. Sci. Telecommun. Program, Missouri Univ., Kansas City, MO, USA
fDate :
4/1/1995 12:00:00 AM
Abstract :
This paper introduces a simple O(NlogN) sequential algorithm that determines the admissibility of an arbitrary permutation to an N×N Multistage Cube-Type Network (MCTN) implemented by 2×2 switching elements (SEs) in contrast to previous O(Nlog2N) 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
Keywords :
multistage interconnection networks; parallel algorithms; O(NlogN) sequential algorithm; arbitrary permutation; bit-operations; multistage cube-type network; multistage interconnection networks; optimal algorithm; permutation admissibility; Algorithm design and analysis; Cities and towns; Computer science; Multiprocessor interconnection networks;
Journal_Title :
Computers, IEEE Transactions on
