An optimal algorithm for permutation admissibility to multistage interconnection networks

Autor:	Xiaojun Shen, Mao Xu, Xiangzu Wang
Rok vydání:	1995
Předmět:	Interconnection Stochastic matrix Multistage interconnection networks Parallel algorithm Binary number Theoretical Computer Science Combinatorics Permutation Computational Theory and Mathematics Hardware and Architecture Simple (abstract algebra) Algorithm Software Sequential algorithm Mathematics
Zdroj:	IEEE Transactions on Computers. 44:604-608
ISSN:	0018-9340
DOI:	10.1109/12.376176
Popis:	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. >
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e8db3345d39260abf278a9bf00f7a142 https://doi.org/10.1109/12.376176 Zobrazit plný text záznamu