Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures
|Title:||Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures||Authors:||Ajwani, Deepak; Sitchinava, 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) model; Geometric problems; Parallel distribution sweeping framework; I/O transfers; DRAM; Caches||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
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.