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 k th 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 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 \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 .

Keywords:

• Computation Time
• Mesh
• Multiselection
• Parallel Algorithm
• Routing
• Selection