Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures

Files in This Item:
File Description SizeFormat 
ajwani_esa13.pdf214.6 kBAdobe PDFDownload
Title: Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures
Authors: Ajwani, DeepakSitchinava, Nodari
Permanent link: http://hdl.handle.net/10197/10870
Date: 4-Sep-2013
Online since: 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/Report no.: Lecture Notes in Computer Science book series (LNCS); Volume 8125
Copyright (published version): 2013 Springer
Keywords: Parallel External Memory (PEM) modelGeometric problemsParallel distribution sweeping frameworkI/O transfersDRAMCaches
DOI: 10.1007/978-3-642-40450-4_3
Language: en
Status of Item: Not peer reviewed
Is 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
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 50

Last Week
Last month
checked on Feb 19, 2020

Page view(s)

Last Week
Last month
checked on Feb 25, 2020


checked on Feb 25, 2020

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.