2021/03/01 by Yan Gu, Gu, Yan, Omar Obeya +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Performance (cs.PF) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2103.01216
openalex publication_date 2021/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Many parallel algorithms use at least linear auxiliary space in the size of the input to enable computations to be done independently without conflicts. Unfortunately, this extra space can be prohibitive for memory-limited machines, preventing large inputs from being processed. Therefore, it is desirable to design parallel in-place algorithms that use sublinear (or even polylogarithmic) auxiliary space. In this paper, we bridge the gap between theory and practice for parallel in-place (PIP) algorithms. We first define two computational models based on fork-join parallelism, which reflect modern parallel programming environments. We then introduce a variety of new parallel in-place algorithms that are simple and efficient, both in theory and in practice. Our algorithmic highlight is the Decomposable Property introduced in this paper, which enables existing non-in-place but highly-optimized parallel algorithms to be converted into parallel in-place algorithms. Using this property, we obtain algorithms for random permutation, list contraction, tree contraction, and merging that take linear work, O(n1-ε) auxiliary space, and O(nε\cdotpolylog(n)) span for 0