ISSN:
1572-9125
Keywords:
C.1.2
;
E.1
;
F.1.2
;
F.2.2
;
mesh-connected computers
;
broadcasting
;
multiple buses
;
selection
;
parallel algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract One of the fundamental algorithmic problems in computer science involves selecting thekth smallest element in a setS ofn elements. In this paper we present a fast selection algorithm which runs inO(n 1/8 logn) time on a mesh with multiple broadcasting of sizen 3/8 ×n 5/8. Our result shows that, just like semigroup computations, selection can be done much faster on a suitably chosen rectangular mesh than on square meshes. We also show that if every processor can storen 1/9 items, then our selection algorithm runs inO(n 1/9 logn) time on a mesh with multiple broadcasting of sizen 1/3 ×n 5/9.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01990339
Permalink
