SELECTION ON RECTANGULAR MESHES WITH MULTIPLE BROADCASTING

One of the fundamental algorithmic problems in computer science involves selecting the kth smallest element in a set S of n elements. In this paper we present a fast selection algorithm which runs in O(n1/8 log n) time on a mesh with multiple broadcasting of size n3/8 x n5/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 store n1/9 items, then our selection algorithm runs in O(n1/8 log n) time on a mesh with multiple broadcasting of size n1/3 x n5/9.