TY - GEN
T1 - Histogram sort with sampling
AU - Harsh, Vipul
AU - Kale, Laxmikant
AU - Solomonik, Edgar
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/6/17
Y1 - 2019/6/17
N2 - To minimize data movement, state-of-the-art parallel sorting algorithms use techniques based on sampling and histogramming to partition keys prior to redistribution. Sampling enables partitioning to be done using a representative subset of the keys, while histogramming enables evaluation and iterative improvement of a given partition. We introduce Histogram sort with sampling (HSS), which combines sampling and iterative histogramming to find high-quality partitions with minimal data movement and high practical performance. Compared to the best known (recently introduced) algorithm for finding these partitions, our algorithm requires a factor of Θ(log(p)/ log log(p)) less communication, and substantially less when compared to standard variants of Sample sort and Histogram sort. We provide a distributed-memory implementation of the proposed algorithm, compare its performance to two existing implementations, and provide a brief application study showing benefit of the new algorithm.
AB - To minimize data movement, state-of-the-art parallel sorting algorithms use techniques based on sampling and histogramming to partition keys prior to redistribution. Sampling enables partitioning to be done using a representative subset of the keys, while histogramming enables evaluation and iterative improvement of a given partition. We introduce Histogram sort with sampling (HSS), which combines sampling and iterative histogramming to find high-quality partitions with minimal data movement and high practical performance. Compared to the best known (recently introduced) algorithm for finding these partitions, our algorithm requires a factor of Θ(log(p)/ log log(p)) less communication, and substantially less when compared to standard variants of Sample sort and Histogram sort. We provide a distributed-memory implementation of the proposed algorithm, compare its performance to two existing implementations, and provide a brief application study showing benefit of the new algorithm.
KW - Data partitioning
KW - Histogramming
KW - Parallel sorting
KW - Sampling
UR - http://www.scopus.com/inward/record.url?scp=85068671680&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068671680&partnerID=8YFLogxK
U2 - 10.1145/3323165.3323184
DO - 10.1145/3323165.3323184
M3 - Conference contribution
AN - SCOPUS:85068671680
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 201
EP - 212
BT - SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
Y2 - 22 June 2019 through 24 June 2019
ER -