Empirical Evaluation of the Parallel Distribution Sweeping Framework in the Parallel External Memory Model

In recent years, various computational models have been proposed to design algorithms on modern multicore and many-core architectures. While these models have been used to design a large number of algorithms, there has been hardly any empirical studies on how well the algorithms designed in these models perform in practice. In this paper, we perform an empirical evaluation of the Parallel External Memory (PEM) model in the context of geometric problems. In particular, we implement parallel distribution sweeping framework of Ajwani, Sitchinava and Zeh to solve the two-dimensional batched orthogonal point location problem. We show that the running times on real multicore architectures matches the theoretical predictions of the PEM model due to fewer cache misses of the PEM algorithms compared to the traditional approaches based on plane sweep and two-way divide and conquer parallel algorithms.