Parallel Longest Increasing Subsequence and van Emde Boas Trees
Parallel Longest Increasing Subsequence and van Emde Boas Trees
复制标题
并行最长递增子序列和 van Emde Boas 树
DOI：
10.1145/3558481.3591069
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Wan, Zijin
中科院分区：
文献类型：
--
作者：
Gu, Yan;Men, Ziyang;Shen, Zheqi;Sun, Yihan;Wan, Zijin
本文研究最长递增子序列（LIS）问题的并行算法。令 n 为输入大小，k 为输入的 LIS 长度。因此，LIS 是一个简单的问题，可以使用动态规划 (DP) 在 O(n log n) 工作中解决。然而，并行化 LIS 是一个长期存在的挑战。我们不知道有任何并行 LIS 算法具有最佳的 O(n log n) 工作量和非平凡的并行性（即 Õ(k) 或 o(n) 跨度）。本文提出了一种并行 LIS 算法，其成本为 O(n log k) 工作量、Õ(k) 跨度和 O(n) 空间，并且比以前的并行 LIS 算法简单得多。我们还将该算法推广到 LIS 的加权版本，它最大化递增子序列中所有对象的加权和。为了实现加权LIS算法更好的工作范围，我们为van Emde Boas（vEB树）设计了并行算法，它与顺序vEB树具有相同的结构，并支持高效的并行批量插入、删除和范围查询。我们还实现了我们的并行LIS算法。我们的实现是轻量级、高效和可扩展的。在输入大小为109时，我们的LIS算法在输入为k时优于高度优化的顺序算法（具有O(n log k)成本） ≤ 3 x 105。我们的算法在所有输入实例上也比 Shen 等人（2022）现有的最佳并行实现快得多。
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let n be the input size and k be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using dynamic programming (DP) in O(n log n) work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal O(n log n) work and non-trivial parallelism (i.e., Õ(k) or o(n) span).This paper proposes a parallel LIS algorithm that costs O(n log k) work, Õ(k) span, and O(n) space, and is much simpler than the previous parallel LIS algorithms. We also generalize the algorithm to a weighted version of LIS, which maximizes the weighted sum for all objects in an increasing subsequence. To achieve a better work bound for the weighted LIS algorithm, we designed parallel algorithms for the van Emde Boas (vEB tree, which has the same structure as the sequential vEB tree, and supports work-efficient parallel batch insertion, deletion, and range queries.We also implemented our parallel LIS algorithms. Our implementation is light-weighted, efficient, and scalable. On input size 109, our LIS algorithm outperforms a highly-optimized sequential algorithm (with O(n log k)cost) on inputs with k ≤ 3 x 105. Our algorithm is also much faster than the best existing parallel implementation by Shen et al. (2022) on all input instances.
登录
查看更多内容
DOI：
--
发表时间：
1999
期刊：
--
影响因子：
--
作者：
A. Gebremedhin
通讯作者：
A. Gebremedhin
工程多队列：快速宽松的并发优先级队列
DOI：
--
发表时间：
2021
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Marvin Williams;P. Sanders;Roman Dementiev
通讯作者：
Roman Dementiev
DOI：
10.1145/3558481.3591078
发表时间：
2023
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Cao, Nairen;Huang, Shang-En;Su, Hsin-Hao
通讯作者：
Su, Hsin-Hao
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
只需加入并行有序集
DOI：
10.1145/2935764.2935768
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Daniel Ferizovic;Yihan Sun
通讯作者：
Yihan Sun