Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory
William Kuszmaul, Alek Westover · 2020
We present an in-place algorithm for the parallel-partition problem with linear work and polylogarithmic span. The algorithm uses only exclusive read/write shared variables and can be implemented using parallel-for-loops without any additional concurrency considerations (i.e., the algorithm is EREW). A key feature of the algorithm is that it exhibits provably optimal cache behavior up to small-order factors.