Tiskin, Alexander (2010) Parallel selection by regular sampling. In: 16th International Euro-Par Conference on Parallel Processing, Ischia, Italy, August 31-September 03, 2010. Published in: Euro-Par 2010 - Parallel Processing, Vol.6272 (No.2). pp. 393-399.

Full text not available from this repository.

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(log log p) 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.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Euro-Par 2010 - Parallel Processing
Publisher:	Springer Verlag
ISBN:	978-3-642-15290-0
ISSN:	0302-9743
Editor:	DAmbra, P and Guarracino, M and Talia, D
Date:	2010
Volume:	Vol.6272
Number:	No.2
Number of Pages:	7
Page Range:	pp. 393-399
Identification Number:	10.1007/978-3-642-15291-7_36
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Title of Event:	16th International Euro-Par Conference on Parallel Processing
Type of Event:	Conference
Location of Event:	Ischia, Italy
Date(s) of Event:	August 31-September 03, 2010
URI:	http://wrap.warwick.ac.uk/id/eprint/5002

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item