1 Search Results for "Lim, Wei Quan"


Document
Parallel Finger Search Structures

Authors: Seth Gilbert and Wei Quan Lim

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


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.

Cite as

Seth Gilbert and Wei Quan Lim. Parallel Finger Search Structures. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gilbert_et_al:LIPIcs.DISC.2019.20,
  author =	{Gilbert, Seth and Lim, Wei Quan},
  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 =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.20},
  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}
}
  • Refine by Author
  • 1 Gilbert, Seth
  • 1 Lim, Wei Quan

  • Refine by Classification
  • 1 Theory of computation → Parallel algorithms
  • 1 Theory of computation → Parallel computing models
  • 1 Theory of computation → Shared memory algorithms

  • Refine by Keyword
  • 1 Comparison-based Search
  • 1 Dictionaries
  • 1 Distribution-sensitive algorithms
  • 1 Multithreading
  • 1 Parallel data structures

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail