Optimal parallel algorithms for multiselection on mesh-connected computers

Multiselection is the problem of selecting multiple elements at specified ranks from a set of arbitrary elements. In this paper, we first present an efficient algorithm for single-element selection that runs in O(rootp +(n/p) \log p \log (kp/n)) time for selecting the k th smallest element from n elements on a rootp x rootp mesh-connected computer of p less than or equal to n processors, where the first component is for communication and second is for computation (data comparisons). Our algorithm is more computationally efficient than the existing result when p greater than or equal to n(1/2 + epsilon) for any 0 < epsilon < 1/2 . Combining our result for p = Omega(rootn) with the existing result for p = O(rootn) yields an improved computation time complexity for the selection problem on mesh t(comp)(sel) = O(min{(n/p) log p log (kp/n),\ (n/p + p) \log(n/p)\}) . Using this algorithm as a building block, we then present two efficient parallel algorithms for multiselection on the mesh-connected computers. For selecting r elements from a set of n elements on a rootp x rootp mesh, p, r less than or equal to n , our first algorithm runs in time O(p(1/2) + t(comp)(sel) min {r log r, log p}) with processors operating in the SIMD mode, which is time-optimal when p less than or equal to r . Allowing processors to operate in the MIMD mode, our second algorithm runs in O(p(1/2) + t(comp)(sel) log r) time and is time-optimal for any r and p .