TY - JOUR

T1 - A randomized sorting algorithm on the BSP model

AU - Gerbessiotis, Alexandros V.

AU - Siniolakis, Constantinos J.

N1 - Funding Information:
Early partial support for this work was provided by an EPSRC Grant GR/K16999 (UK), and subsequent work of the first author was supported in part by NSF/EIA-9977508 and NSF/ITR IIS-0324816.

PY - 2014/12/1

Y1 - 2014/12/1

N2 - An oversampling-based randomized algorithm is introduced for sorting n keys of any abstract data type on the p processors of a latency-tolerant parallel system such as a bulk-synchronous parallel computer. The algorithm is asymptotically, for large n, optimal in computation and communication compared to the best available sequential sorting algorithm, even when constant factors are taken into consideration. Its parallel time is within a (1 + o(1))/p multiplicative factor of the corresponding sequential method for sorting, improving upon other approaches for a wider range of values of p relative to n. It also improves upon other randomized sorting algorithms that have been developed for latency-tolerant models of computation on the amount of parallel slack (ratio n over p) required to achieve optimal speedup and also, on the associated failure probability. For values of p closer to n than other latency-tolerant randomized approaches, it can be turned into a PRAM-like algorithm but for such cases a speedup of O(p) rather than p/(1 + o(1)) is then achievable. Although the general framework of the proposed algorithm relies on the well-established prior idea of sample-based sorting, there are some novel features in its design such as the choice of splitter size, the way keys are split, and the handling of the base case of the recursive sorting algorithm that contribute to its performance.

AB - An oversampling-based randomized algorithm is introduced for sorting n keys of any abstract data type on the p processors of a latency-tolerant parallel system such as a bulk-synchronous parallel computer. The algorithm is asymptotically, for large n, optimal in computation and communication compared to the best available sequential sorting algorithm, even when constant factors are taken into consideration. Its parallel time is within a (1 + o(1))/p multiplicative factor of the corresponding sequential method for sorting, improving upon other approaches for a wider range of values of p relative to n. It also improves upon other randomized sorting algorithms that have been developed for latency-tolerant models of computation on the amount of parallel slack (ratio n over p) required to achieve optimal speedup and also, on the associated failure probability. For values of p closer to n than other latency-tolerant randomized approaches, it can be turned into a PRAM-like algorithm but for such cases a speedup of O(p) rather than p/(1 + o(1)) is then achievable. Although the general framework of the proposed algorithm relies on the well-established prior idea of sample-based sorting, there are some novel features in its design such as the choice of splitter size, the way keys are split, and the handling of the base case of the recursive sorting algorithm that contribute to its performance.

KW - BSP model

KW - Randomized sorting

KW - latency-tolerant algorithms

KW - oversampling

KW - random sampling

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

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

U2 - 10.1142/S179383091450061X

DO - 10.1142/S179383091450061X

M3 - Article

AN - SCOPUS:85073249731

VL - 6

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

SN - 1793-8309

IS - 4

M1 - 1450061

ER -