High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems
复制标题
半排序及相关问题的高性能灵活并行算法
DOI：
10.1145/3558481.3591071
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Sun, Yihan
中科院分区：
文献类型：
--
作者：
Dong, Xiaojun;Wu, Yunshu;Wang, Zhongqi;Dhulipala, Laxman;Gu, Yan;Sun, Yihan
半排序是一种基本算法原语，广泛应用于高效并行算法的设计和分析。它将输入作为记录数组和每个记录提取一个键的函数，并对它们重新排序，以便具有相同键的记录是连续的。由于许多应用程序只需要收集相等的值，而不需要对输入进行完全排序，因此半排序是广泛适用的，例如，在字符串算法、图形分析和几何处理以及许多其他领域中。然而，尽管最近有几十篇论文在理论分析中使用了半排序，并且存在渐近最优并行半排序算法，但由于现有半排序实现中存在潜在的性能问题，这些并行算法的大多数实现在实践中选择通过使用比较或整数排序来实现半排序。在本文中，我们重新审视半排序问题，目标是实现具有灵活接口的高性能并行半排序实现。我们的方法可以很容易地扩展到两个相关的问题，直方图和收集-减少。我们的算法在实践中实现了强大的加速，重要的是，在我们测试的几乎所有设置（不同的输入大小、分布和键类型）中，我们的算法都优于最先进的并行排序和半排序方法。平均而言（几何平均值），我们的半排序实现比测试的最佳基线至少快1.27倍。我们还用真实世界的数据测试了两个重要的应用程序，并表明我们的算法比现有方法提高了性能（高达2.13倍）。我们相信使用我们的结果可以加速许多其他并行算法的实现。
Semisort is a fundamental algorithmic primitive widely used in the design and analysis of efficient parallel algorithms. It takes input as an array of records and a function extracting a key per record, and reorders them so that records with equal keys are contiguous. Since many applications only require collecting equal values, but not fully sorting the input, semisort is broadly applicable, e.g., in string algorithms, graph analytics, and geometry processing, among many other domains. However, despite dozens of recent papers that use semisort in their theoretical analysis and the existence of an asymptotically optimal parallel semisort algorithm, most implementations of these parallel algorithms choose to implement semisort by using comparison or integer sorting in practice, due to potential performance issues in existing semisort implementations.In this paper, we revisit the semisort problem, with the goal of achieving a high-performance parallel semisort implementation with a flexible interface. Our approach can easily be extended to two related problems, histogram and collect-reduce. Our algorithms achieve strong speedups in practice, and importantly, outperform state-of-the-art parallel sorting and semisorting methods for almost all settings we tested, with varying input sizes, distribution, and key types. On average (geometric means), our semisort implementation is at least 1.27x faster the best of the tested baselines. We also test two important applications with real-world data, and show that our algorithms improve the performance (up to 2.13x) over existing approaches. We believe that many other parallel algorithm implementations can be accelerated using our results.
登录
查看更多内容
DOI：
10.1145/3409964.3461816
发表时间：
2021
期刊：
SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Kang, Hongbo;Gibbons, Phillip B.;Blelloch, Guy E.;Dhulipala, Laxman;Gu, Yan;McGuffey, Charles
通讯作者：
McGuffey, Charles
DOI：
10.1109/ipdps.2018.00081
发表时间：
2017-10
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
用于种族检测的高效访问历史记录
DOI：
10.1145/3409964.3461825
发表时间：
2022
期刊：
022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX
影响因子：
--
作者：
Xu, Yifan;Zhou, Anchengcheng;Yin, Grace Q.;Agrawal, Kunal;Lee, I-Ting Angelina;Schardl, Tao B.
通讯作者：
Schardl, Tao B.
DOI：
10.1145/3210377.3210380
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
通讯作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
影响因子：
1.6
作者：
Axtmann, Michael;Witt, Sascha;Sanders, Peter
通讯作者：
Sanders, Peter