1 Search Results for "Koval, Nikita"

Document

DOI: 10.4230/LIPIcs.OPODIS.2019.15

In Search of the Fastest Concurrent Union-Find Algorithm

Authors: Dan Alistarh, Alexander Fedorov, and Nikita Koval

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract

Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequential case. Recently, there has been mounting interest in analyzing this problem in the concurrent scenario, and several asymptotically-efficient algorithms have been proposed. Yet, to date, there is very little known about the practical performance of concurrent Union-Find. This work addresses this gap. We evaluate and analyze the performance of several concurrent Union-Find algorithms and optimization strategies across a wide range of platforms (Intel, AMD, and ARM) and workloads (social, random, and road networks, as well as integrations into more complex algorithms). We first observe that, due to the limited computational cost, the number of induced cache misses is the critical determining factor for the performance of existing algorithms. We introduce new techniques to reduce this cost by storing node priorities implicitly and by using plain reads and writes in a way that does not affect the correctness of the algorithms. Finally, we show that Union-Find implementations are an interesting application for Transactional Memory (TM): one of the fastest algorithm variants we discovered is a sequential one that uses coarse-grained locking with the lock elision optimization to reduce synchronization cost and increase scalability.

Cite as

Dan Alistarh, Alexander Fedorov, and Nikita Koval. In Search of the Fastest Concurrent Union-Find Algorithm. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alistarh_et_al:LIPIcs.OPODIS.2019.15,
  author =	{Alistarh, Dan and Fedorov, Alexander and Koval, Nikita},
  title =	{{In Search of the Fastest Concurrent Union-Find Algorithm}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.15},
  URN =		{urn:nbn:de:0030-drops-118012},
  doi =		{10.4230/LIPIcs.OPODIS.2019.15},
  annote =	{Keywords: union-find, concurrency, evaluation, benchmarks, hardware transactional memory}
}

Refine by Author
1 Alistarh, Dan
1 Fedorov, Alexander
1 Koval, Nikita

Refine by Classification
1 Computing methodologies → Concurrent algorithms
1 Theory of computation → Concurrent algorithms
1 Theory of computation → Graph algorithms analysis

Refine by Keyword
1 benchmarks
1 concurrency
1 evaluation
1 hardware transactional memory
1 union-find

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Koval, Nikita"

In Search of the Fastest Concurrent Union-Find Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message