I/O-Optimal Distribution Sweeping on Private-Cache Chip Multiprocessors

Files in This Item:
File Description SizeFormat 
ajwani_ipdps11.pdf190.93 kBAdobe PDFDownload
Title: I/O-Optimal Distribution Sweeping on Private-Cache Chip Multiprocessors
Authors: Ajwani, Deepak
Sitchinava, Nodari
Zeh, Norbert
Permanent link: http://hdl.handle.net/10197/9898
Date: 8-Sep-2011
Online since: 2019-04-10T12:10:34Z
Abstract: The parallel external memory (PEM) model has been used as a basis for the design and analysis of a wide range of algorithms for private-cache multi-core architectures. As a tool for developing geometric algorithms in this model, a parallel version of the I/O-efficient distribution sweeping framework was introduced recently, and a number of algorithms for problems on axis-aligned objects were obtained using this framework. The obtained algorithms were efficient but not optimal. In this paper, we improve the framework to obtain algorithms with the optimal I/O complexity of O(sort P(N) + K/PB) for a number of problems on axis-aligned objects, P denotes the number of cores/processors, B denotes the number of elements that fit in a cache line, N and K denote the sizes of the input and output, respectively, and sort P(N) denotes the I/O complexity of sorting N items using P processors in the PEM model. To obtain the above improvement, we present a new one-dimensional batched range counting algorithm on a sorted list of ranges and points that achieves an I/O complexity of O((N + K)/PB), where K is the sum of the counts of all the ranges. The key to achieving efficient load balancing among the processors in this algorithm is a new method to count the output without enumerating it, which might be of independent interest.
Type of material: Conference Publication
Publisher: IEEE
Copyright (published version): 2011 IEEE
Keywords: Parallel external memoryPEMMulticore algorithmsComputational geometryParallel distribution sweepingComputational modeling
DOI: 10.1109/IPDPS.2011.106
Language: en
Status of Item: Not peer reviewed
Is part of: 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS): 16-20 May 2011, Anchorage, Alaska, USA
Conference Details: The 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS), Anchorage, Alaska, 16-20 May 2011
ISBN: 9780769543857
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 50

checked on Apr 18, 2019

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.