Optimal parallel multiselection on EREW PRAM

Hong Shen

doi:10.1016/S0167-8191(97)00100-2

Optimal parallel multiselection on EREW PRAM

Hong Shen

Griffith University Queensland

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n^∈; log r) time on an EREW PRAM with n^1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.

Original language	English
Pages (from-to)	1987-1992
Number of pages	6
Journal	Parallel Computing
Volume	23
Issue number	13
DOIs	https://doi.org/10.1016/S0167-8191(97)00100-2
Publication status	Published - 15 Dec 1997
Externally published	Yes

Keywords

EREW PRAM
Multiselection
Parallel algorithm
Selection
Sorting

Access to Document

10.1016/S0167-8191(97)00100-2

Cite this

@article{4987a6eb30a94277804aa3d27aa31f0f,

title = "Optimal parallel multiselection on EREW PRAM",

abstract = "Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n∈; log r) time on an EREW PRAM with n1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.",

keywords = "EREW PRAM, Multiselection, Parallel algorithm, Selection, Sorting",

author = "Hong Shen",

note = "Funding Information: l E-mail: [email protected]. {\textquoteright} This work was partially supported by ARC Grant.",

year = "1997",

month = dec,

day = "15",

doi = "10.1016/S0167-8191(97)00100-2",

language = "English",

volume = "23",

pages = "1987--1992",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

number = "13",

}

TY - JOUR

T1 - Optimal parallel multiselection on EREW PRAM

AU - Shen, Hong

N1 - Funding Information: l E-mail: [email protected]. ’ This work was partially supported by ARC Grant.

PY - 1997/12/15

Y1 - 1997/12/15

N2 - Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n∈; log r) time on an EREW PRAM with n1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.

AB - Multiselection requires to select r elements at specified ranks in a given set of n elements, r ≤ n. This paper proposes a paradigm for parallel multiselection to achieve the optimal cost. Following this paradigm and employing a cost-optimal algorithm for single-element selection, a cost-optimal parallel algorithm for multiselection is presented. Our algorithm runs in O(n∈; log r) time on an EREW PRAM with n1-∈ processors for any 0 < ∈ < 1. In the special case when ∈ = log(log n log * n)/log n, our algorithm requires O(log n log * n log r) time and O(n log r) cost.

KW - EREW PRAM

KW - Multiselection

KW - Parallel algorithm

KW - Selection

KW - Sorting

UR - http://www.scopus.com/inward/record.url?scp=0031352362&partnerID=8YFLogxK

U2 - 10.1016/S0167-8191(97)00100-2

DO - 10.1016/S0167-8191(97)00100-2

M3 - Article

AN - SCOPUS:0031352362

SN - 0167-8191

VL - 23

SP - 1987

EP - 1992

JO - Parallel Computing

JF - Parallel Computing

IS - 13

ER -

Optimal parallel multiselection on EREW PRAM

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this