Empirical evaluation of the parallel distribution sweeping framework on multicore architectures

DOI10.1007/978-3-642-40450-4_3zbMATH Open1416.65576arXiv1306.4521OpenAlexW1764185321MaRDI QIDQ2849293FDOQ2849293

Deepak Ajwani, Nodari Sitchinava

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1306.4521

Recommendations

• Geometric algorithms for private-cache chip multiprocessors (extended abstract)
• Multi-core Implementations of Geometric Algorithms
• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep
• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep
• Bulk synchronous parallel algorithms for the external memory model

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical algorithms for specific classes of architectures (65Y10)

Uses Software

• MCSTL
• Pochoir

This page was built for publication: Empirical evaluation of the parallel distribution sweeping framework on multicore architectures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849293)