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(sqrt{p} +(n/p) log p log (kp/n)) time for selecting the kth smallest element from n elements on a sqrt{p} times sqrt{p} mesh-connected computer of p leq 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 geq nˆ{1/2 + varepsilon} for any 0 lt varepsilon lt 1/2. Combining our result for p = Omega (sqrt{n}) with the existing result for p = O(sqrt{n}) yields an improved computation time complexity for the selection problem on mesh t_{rm comp}ˆ{rm sel} = O(min {(n/p) log plog (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 sqrt{p} times sqrt{p} mesh, p, r leq n, our first algorithm runs in time O(pˆ{1/2} + t_{rm comp}ˆ{rm sel} min {r log r, log p}) with processors operating in the SIMD mode, which is time-optimal when p le r. Allowing processors to operate in the MIMD mode, our second algorithm runs in O(pˆ{1/2} + t_{rm comp}ˆ{rm sel} log r) time and is time-optimal for any r and p.Hong Shen, Yijie Han, Yi Pan & David Evan