Standard

Parallel selection by regular sampling. / Tiskin, Alexander.

Euro-Par 2010 - Parallel Processing (Euro-Par 2010). Vol. PART 2 2010. p. 393-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6272).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Tiskin, A 2010, Parallel selection by regular sampling. in Euro-Par 2010 - Parallel Processing (Euro-Par 2010). vol. PART 2, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6272, pp. 393-399. https://doi.org/10.1007/978-3-642-15291-7_36

APA

Tiskin, A. (2010). Parallel selection by regular sampling. In Euro-Par 2010 - Parallel Processing (Euro-Par 2010) (Vol. PART 2, pp. 393-399). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6272). https://doi.org/10.1007/978-3-642-15291-7_36

Vancouver

Tiskin A. Parallel selection by regular sampling. In Euro-Par 2010 - Parallel Processing (Euro-Par 2010). Vol. PART 2. 2010. p. 393-399. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-15291-7_36

Author

Tiskin, Alexander. / Parallel selection by regular sampling. Euro-Par 2010 - Parallel Processing (Euro-Par 2010). Vol. PART 2 2010. pp. 393-399 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{77a183b90f084a508d90e643c540a22e,
title = "Parallel selection by regular sampling",
abstract = "Bulk-synchronous parallelism (BSP) is a simple and efficient paradigm for parallel algorithm design and analysis. In this paper, we present a new simple deterministic BSP algorithm for the classical problem of selecting the k-th smallest element from an array of size n, for a given k, on a parallel computer with p processors. Our algorithm is based on the technique of regular sampling. It runs in optimal O(n/p) local computation and communication, and near-optimal O(loglogp) synchronisation. The algorithm is of theoretical interest, as it gives an improvement in the asymptotic synchronisation cost over its predecessors. It is also simple enough to be implementable. {\textcopyright} 2010 Springer-Verlag.",
author = "Alexander Tiskin",
year = "2010",
month = nov,
day = "19",
doi = "10.1007/978-3-642-15291-7_36",
language = "English",
volume = "PART 2",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "393--399",
booktitle = "Euro-Par 2010 - Parallel Processing (Euro-Par 2010)",

}

RIS

TY - GEN

T1 - Parallel selection by regular sampling

AU - Tiskin, Alexander

PY - 2010/11/19

Y1 - 2010/11/19

N2 - Bulk-synchronous parallelism (BSP) is a simple and efficient paradigm for parallel algorithm design and analysis. In this paper, we present a new simple deterministic BSP algorithm for the classical problem of selecting the k-th smallest element from an array of size n, for a given k, on a parallel computer with p processors. Our algorithm is based on the technique of regular sampling. It runs in optimal O(n/p) local computation and communication, and near-optimal O(loglogp) synchronisation. The algorithm is of theoretical interest, as it gives an improvement in the asymptotic synchronisation cost over its predecessors. It is also simple enough to be implementable. © 2010 Springer-Verlag.

AB - Bulk-synchronous parallelism (BSP) is a simple and efficient paradigm for parallel algorithm design and analysis. In this paper, we present a new simple deterministic BSP algorithm for the classical problem of selecting the k-th smallest element from an array of size n, for a given k, on a parallel computer with p processors. Our algorithm is based on the technique of regular sampling. It runs in optimal O(n/p) local computation and communication, and near-optimal O(loglogp) synchronisation. The algorithm is of theoretical interest, as it gives an improvement in the asymptotic synchronisation cost over its predecessors. It is also simple enough to be implementable. © 2010 Springer-Verlag.

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

U2 - 10.1007/978-3-642-15291-7_36

DO - 10.1007/978-3-642-15291-7_36

M3 - Conference contribution

AN - SCOPUS:78249281967

VL - PART 2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 393

EP - 399

BT - Euro-Par 2010 - Parallel Processing (Euro-Par 2010)

ER -

ID: 127758256