Options
Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures
Author(s)
Date Issued
2013-09-04
Date Available
2019-07-10T10:22:51Z
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.
Type of Material
Conference Publication
Publisher
Springer
Volume
8125 LNCS
Start Page
25
End Page
36
Series
Lecture Notes in Computer Science book series (LNCS)
Volume 8125
Copyright (Published Version)
2013 Springer
Language
English
Status of Item
Not peer reviewed
Part of
Bodlaender, H.L., Italiano, G.F. (eds.). Algorithms – ESA 2013 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013 Proceedings
Conference Details
ESA 2013: 21st Annual European Symposium Sophia Antipolis, France, 2-4 September 2013
ISBN
9783642404498
ISSN
0302-9743
This item is made available under a Creative Commons License
File(s)
Owning collection
Scopus© citations
2
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Views
689
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Downloads
289
Last Week
1
1
Last Month
5
5
Acquisition Date
Mar 28, 2024
Mar 28, 2024