License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.11
URN: urn:nbn:de:0030-drops-100713
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10071/
Go to the corresponding LIPIcs Volume Portal

Aksenov, Vitaly ; Kuznetsov, Petr ; Shalyto, Anatoly

Parallel Combining: Benefits of Explicit Synchronization

pdf-format:
LIPIcs-OPODIS-2018-11.pdf (0.6 MB)

Abstract

A parallel batched data structure is designed to process synchronized batches of operations on the data structure using a parallel program. In this paper, we propose parallel combining, a technique that implements a concurrent data structure from a parallel batched one. The idea is that we explicitly synchronize concurrent operations into batches: one of the processes becomes a combiner which collects concurrent requests and initiates a parallel batched algorithm involving the owners (clients) of the collected requests. Intuitively, the cost of synchronizing the concurrent calls can be compensated by running the parallel batched algorithm.
We validate the intuition via two applications. First, we use parallel combining to design a concurrent data structure optimized for read-dominated workloads, taking a dynamic graph data structure as an example. Second, we use a novel parallel batched priority queue to build a concurrent one. In both cases, we obtain performance gains with respect to the state-of-the-art algorithms.

BibTeX - Entry

@InProceedings{aksenov_et_al:LIPIcs:2018:10071,
  author =	{Vitaly Aksenov and Petr Kuznetsov and Anatoly Shalyto},
  title =	{{Parallel Combining: Benefits of Explicit Synchronization}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10071},
  URN =		{urn:nbn:de:0030-drops-100713},
  doi =		{10.4230/LIPIcs.OPODIS.2018.11},
  annote =	{Keywords: concurrent data structure, parallel batched data structure, combining}
}

Keywords: concurrent data structure, parallel batched data structure, combining
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

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