A Work-Efficient Parallel Algorithm for Longest Increasing Subsequence
share
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 textbook problem that can be solved using dynamic programming (DP) in O(nlog n) work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal O(nlog n) work and non-trivial parallelism (i.e., Õ(k) or o(n) span). Here, the work of a parallel algorithm is the total number of operations, and the span is the longest dependent instructions. This paper proposes a parallel LIS algorithm that costs O(nlog 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. Our weighted LIS algorithm has O(nlog^2 n) work and Õ(k) span. We also implemented our parallel LIS algorithms. Due to simplicity, our implementation is light-weighted, efficient, and scalable. On input size 10^9, our LIS algorithm outperforms a highly-optimized sequential algorithm (with O(nlog k) cost) on inputs with k≤ 3× 10^5. Our algorithm is also much faster than the best existing parallel implementation by Shen et al. on all input instances.
READ FULL TEXT