DocumentCode :
3487078
Title :
Efficient off-line routing of permutations on restricted access expanded delta networks
Author :
Scherson, I.D. ; Subramanian, Raghu
Author_Institution :
Dept. of Inf. & Comput. Sci., California Univ., Irvine, CA, USA
fYear :
1993
fDate :
13-16 Apr 1993
Firstpage :
284
Lastpage :
290
Abstract :
This paper presents an off-line algorithm for routing permutations on expanded delta networks (EDNs) with restricted access. Restricted access means that the number of elements to be permuted may exceed the number of inputs to the EDN. For every N-element permutation on an M-input EDN, the algorithm computes a routing that takes exactly 3N/M passes (assuming M divides N ). On a certain class of EDNs, the number of passes can be reduced to 2N/M. For example, for every 16 K-element permutation on the 1 K-input global network of the MasPar MP-1 and MP-2, the algorithm computes a routing that takes exactly 32 passes. The time complexity of the algorithm is Θ(NlogN) sequentially, and Θ(log2N) on an N-processor PRAM
Keywords :
computational complexity; multiprocessor interconnection networks; 1 K-input global network; 16 K-element permutation; MP-2; MasPar MP-1; N-element permutation; N-processor PRAM; offline routing of permutations; restricted access expanded delta networks; time complexity; Computer networks; Computer science; NASA; Parallel machines; Phase change random access memory; Routing; Switches; Telecommunication traffic; Virtual machining; Wire;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1993., Proceedings of Seventh International
Conference_Location :
Newport, CA
Print_ISBN :
0-8186-3442-1
Type :
conf
DOI :
10.1109/IPPS.1993.262894
Filename :
262894
Link To Document :
بازگشت