Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a Synchronous PIP (Parallel In-Place) model that addresses the limitations of previous asynchronous models by ensuring in-place guarantees for intermediate processor counts in parallel and distributed computations. The authors develop efficient algorithms that utilize constant private memory per processor while avoiding auxiliary shared memory, making them suitable for embedded systems and IoT applications. Key results demonstrate the effectiveness of a novel parallel-augmented sweep technique, which maintains efficiency and in-place properties across varying processor counts.
Synchronous PIP algorithms can achieve efficient parallel computation without auxiliary memory, even at intermediate 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.