License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.20
URN: urn:nbn:de:0030-drops-113275
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11327/
Go to the corresponding LIPIcs Volume Portal


Gilbert, Seth ; Lim, Wei Quan

Parallel Finger Search Structures

pdf-format:
LIPIcs-DISC-2019-20.pdf (0.6 MB)


Abstract

In this paper we present two versions of a parallel finger structure FS on p processors that supports searches, insertions and deletions, and has a finger at each end. This is to our knowledge the first implementation of a parallel search structure that is work-optimal with respect to the finger bound and yet has very good parallelism (within a factor of O(log p)^2) of optimal). We utilize an extended implicit batching framework that transparently facilitates the use of FS by any parallel program P that is modelled by a dynamically generated DAG D where each node is either a unit-time instruction or a call to FS. The work done by FS is bounded by the finger bound F_L (for some linearization L of D), i.e. each operation on an item with distance r from a finger takes O(log r+1) amortized work. Running P using the simpler version takes O((T_1+F_L)/p + T_infty + d * ((log p)^2 + log n)) time on a greedy scheduler, where T_1, T_infty are the size and span of D respectively, and n is the maximum number of items in FS, and d is the maximum number of calls to FS along any path in D. Using the faster version, this is reduced to O((T_1+F_L)/p + T_infty + d *(log p)^2 + s_L) time, where s_L is the weighted span of D where each call to FS is weighted by its cost according to F_L. FS can be extended to a fixed number of movable fingers. The data structures in our paper fit into the dynamic multithreading paradigm, and their performance bounds are directly composable with other data structures given in the same paradigm. Also, the results can be translated to practical implementations using work-stealing schedulers.

BibTeX - Entry

@InProceedings{gilbert_et_al:LIPIcs:2019:11327,
  author =	{Seth Gilbert and Wei Quan Lim},
  title =	{{Parallel Finger Search Structures}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11327},
  URN =		{urn:nbn:de:0030-drops-113275},
  doi =		{10.4230/LIPIcs.DISC.2019.20},
  annote =	{Keywords: Parallel data structures, Multithreading, Dictionaries, Comparison-based Search, Distribution-sensitive algorithms}
}

Keywords: Parallel data structures, Multithreading, Dictionaries, Comparison-based Search, Distribution-sensitive algorithms
Seminar: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 11.10.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI