AN OPTIMAL ALGORITHM FOR PERMUTATION ADMISSIBILITY TO MULTISTAGE INTERCONNECTION NETWORKS

Authors
SHEN XJ XU M WANG XZ
Citation
Xj. Shen et al., AN OPTIMAL ALGORITHM FOR PERMUTATION ADMISSIBILITY TO MULTISTAGE INTERCONNECTION NETWORKS, I.E.E.E. transactions on computers, 44(4), 1995, pp. 604-608
Citations number
15
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
44
Issue
4
Year of publication
1995
Pages
604 - 608
Database
ISI
SICI code
0018-9340(1995)44:4<604:AOAFPA>2.0.ZU;2-K
Abstract
This paper introduces a simple O(NlogN) sequential algorithm that dete rmines the admissibility of an arbitrary permutation to an N x N Multi stage Cube-Type Network (MCTN) implemented by 2 X 2 switching elements (SEs) in contrast to previous O(Nlog(2)N) algorithms. It is proven th at 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 a mong the total NlogN bits in the binary representations of the destina tions numbered from 0 through N - 1.