poster

Parallel Integer Sort: Theory and Practice (Abstract)

Authors:

Xiaojun Dong,

Laxman Dhulipala,

Yan Gu,

Yihan SunAuthors Info & Claims

HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

Pages 13 - 14

https://doi.org/10.1145/3670684.3673403

Published: 26 July 2024 Publication History

Get Access

Abstract

This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid theoretical foundation for their widespread usage in practice and strong performance. In practice, we design a new integer sorting algorithm, DovetailSort, that is theoretically efficient and has good practical performance.

References

[1]

Susanne Albers and Torben Hagerup. 1997. Improved parallel integer sorting without concurrent writing. Information and Computation, Vol. 136, 1 (1997), 25--51.

Digital Library

Google Scholar

[2]

Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. 2022. Engineering in-place (shared-memory) sorting algorithms. ACM Transactions on Parallel Computing (TOPC), Vol. 9, 1 (2022), 1--62.

Digital Library

Google Scholar

[3]

Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib -- a toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507--509.

Digital Library

Google Scholar

[4]

Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2010. Low depth cache-oblivious algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).

Digital Library

Google Scholar

[5]

Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2024. Parallel Integer Sort: Theory and Practice. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).

Google Scholar

[6]

Marek Kokot, Sebastian Deorowicz, and Maciej Długosz. 2018. Even faster sorting of (not only) integers. In Man-Machine Interactions 5: 5th International Conference on Man-Machine Interactions, ICMMI 2017 Held at Kraków, Poland, October 3--6, 2017. Springer, 481--491.

Google Scholar

[7]

Omar Obeya, Endrias Kahssay, Edward Fan, and Julian Shun. 2019. Theoretically-Efficient and Practical Parallel In-Place Radix Sorting. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 213--224.

Google Scholar

Index Terms

Parallel Integer Sort: Theory and Practice (Abstract)
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
    2. Parallel algorithms
      1. Shared memory algorithms

Recommendations

Parallel Integer Sort: Theory and Practice
PPoPP '24: Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

Integer sorting is a fundamental problem in computer science. This paper studies parallel integer sort both in theory and in practice. In theory, we show tighter bounds for a class of existing practical integer sort algorithms, which provides a solid ...
Partitioned Parallel Radix Sort

Load balanced parallel radix sort solved the load imbalance problem present in parallel radix sort. By redistributing the keys in each round of radix, each processor has exactly the same number of keys, thereby reducing the overall sorting time. Load ...
Cache Efficient Radix Sort for String Sorting

In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

HOPC'24: Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing

June 2024

47 pages

ISBN:9798400707001

DOI:10.1145/3670684

Program Chairs:
Laxman Dhulipala
University of Maryland, USA
,
Yihan Sun
University of California, Riverside, USA

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 July 2024

Check for updates

Author Tags

Qualifiers

Poster

Funding Sources

National Science Foundation
UCR Regents Faculty Development Award
Google Research Scholar Program

Conference

SPAA '24

Sponsor:

SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures

June 17, 2024

Nantes, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
28
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)11

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Parallel Integer Sort: Theory and Practice

Partitioned Parallel Radix Sort

Cache Efficient Radix Sort for String Sorting