Raiders of the Lost Log: Synchronous Parallel In-Place Models and Algorithms
This work provides a theoretical foundation for synchronous in-place parallel algorithms, benefiting embedded systems and IoT applications where memory is constrained.
The paper proposes a Synchronous PIP family of models for in-place parallel and distributed computation, addressing the gap in asynchronous models that lack in-place guarantees for intermediate processor counts. It presents efficient synchronous parallel algorithms requiring no auxiliary shared memory and only constant private memory per processor, leveraging a parallel-augmented sweep technique to ensure strict in-place behavior at all processor counts.
Embedded systems and Internet of Things (IoT) applications motivate in-place parallel algorithms, which avoid allocating additional shared memory past the input. Work by Gu, Obeya, and Shun [APOCS '21] defines a family of PIP (parallel in-place) models and parallel algorithms that eschew auxiliary memory at high processor counts while remaining in-situ when run sequentially. However, their models assume asynchronous processing and have no in-place guarantees for intermediate processor counts. We address this gap in the literature by proposing a Synchronous PIP family of models for in-place parallel and distributed computation. We demonstrate the effectiveness of our new model by giving efficient and synchronous parallel algorithms in this model that require no auxiliary shared memory and only constant private memory per processor. Importantly, we show how to leverage a new parallel-augmented sweep technique to ensure that Synchronous PIP algorithms remain efficient and strictly in-place at all processor counts.