2013/06/19 by Deepak Ajwani, Ajwani, Deepak, Nodari Sitchinava +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #D.1.3 #D.4.8 #Data Structures and Algorithms (cs.DS) #Distributed #F.2.2 #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1306.4521
openalex publication_date 2013/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 the parallel distribution sweeping framework of Ajwani, Sitchinava and Zeh to solve batched 1-dimensional stabbing max problem. While modern processors consist of sophisticated memory systems (multiple levels of caches, set associativity, TLB, prefetching), we empirically show that algorithms designed in simple models, that focus on minimizing the I/O transfers between shared memory and single level cache, can lead to efficient software on current multicore architectures. Our implementation exhibits significantly fewer accesses to slow DRAM and, therefore, outperforms traditional approaches based on plane sweep and two-way divide and conquer.