Empirical evaluation of the parallel distribution sweeping framework on multicore architectures

DOI10.1007/978-3-642-40450-4_3MaRDI QIDQ2849293zbMATH OpenOpenAlexFDO

Authors Deepak Ajwani, Nodari Sitchinava

Publication date 17 September 2013

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

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

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)

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.

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

Cited in

(1)

• Geometric algorithms for private-cache chip multiprocessors (extended abstract)

Describes a project that uses

Uses Software

• Pochoir
• MCSTL

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)