Optimal parallel algorithms for multiselection on mesh-connected computers

Hong Shen, Yijie Han, Y. I. Pan, David J. Evans

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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(√p + (n/p) logp log(kp/n)) time for selecting the kth smallest element from n elements on a √p × √p mesh-connected computer of p ≤ 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 ≥ n1/2+ε for any 0 < ε < 1/2. Combining our result for p = Ω(√n) with the existing result for p = O(√n) yields an improved computation time complexity for the selection problem on mesh tcompsel = O(min{(n/p)logp 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 √p × √p mesh, p, r ≤ n, our first algorithm runs in time O(p1/2 + tcompsel min{r log r, log p}) with processors operating in the SIMD mode, which is time-optimal when p ≤ r. Allowing processors to operate in the MIMD mode, our second algorithm runs in O(p1/2 + tcompsel log r) time and is time-optimal for any r and p.

Original languageEnglish
Pages (from-to)165-179
Number of pages15
JournalInternational Journal of Computer Mathematics
Issue number2
Publication statusPublished - Feb 2003
Externally publishedYes


  • Computation time
  • Mesh
  • Multiselection
  • Parallel algorithm
  • Routing
  • Selection


Dive into the research topics of 'Optimal parallel algorithms for multiselection on mesh-connected computers'. Together they form a unique fingerprint.

Cite this