DocumentCode :
3203613
Title :
Multi-packet selection on mesh-connected processor arrays
Author :
Krizanc, Danny ; Narayanan, Lata
Author_Institution :
Dept. of Comput. Sci., Rochester Univ., NY, USA
fYear :
1992
fDate :
23-26 Mar 1992
Firstpage :
602
Lastpage :
605
Abstract :
The authors show efficient, deterministic algorithms for selection on the mesh-connected processor array, in the case when there are several elements at every processor. In particular, on a p-processor mesh, with N⩾p elements, stored N/p at every processor, they show that selection can be performed in O(min{plogN/p, max{N/p2/3, √p¯}}) communication steps. The best previously known results were based on sorting and required O(N/√p¯) communication steps, for N⩾p
Keywords :
parallel algorithms; deterministic algorithms; mesh-connected processor arrays; multipacket selection; sorting; Computer science; Computer vision; Concurrent computing; Data engineering; Databases; Hypercubes; Network topology; Parallel machines; Sorting; Very large scale integration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
Type :
conf
DOI :
10.1109/IPPS.1992.222999
Filename :
222999
Link To Document :
بازگشت