Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/36756
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Optimal parallel algorithms for multiselection on mesh-connected computers |
Author: | Shen, H. Han, Y. Pan, Y. Evans, D. |
Citation: | International Journal of Computer Mathematics, 2003; 80(2):165-179 |
Publisher: | Taylor & Francis Ltd. |
Issue Date: | 2003 |
ISSN: | 1029-0265 1029-0265 |
Statement of Responsibility: | Hong Shen, Yijie Han, Yi Pan & David Evans |
Abstract: | 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. |
Keywords: | Computation time Mesh Multiselection Parallel algorithm Routing Selection |
Rights: | © Taylor & Francis |
DOI: | 10.1080/00207160304673 |
Published version: | http://dx.doi.org/10.1080/00207160304673 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.