In search of the fastest concurrent union-find algorithm

D.-A. Alistarh, A. Fedorov, N. Koval, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

Download
OA 2019_LIPIcs_Alistarh.pdf 13.07 MB

Conference Paper | Published | English
Department
Series Title
LIPIcs
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.
Publishing Year
Date Published
2020-02-01
Volume
153
Article Number
15
Conference
OPODIS: International Conference on Principles of Distributed Systems
Conference Location
Neuchatal, Switzerland
Conference Date
2019-12-17 – 2019-12-19
ISSN
IST-REx-ID

Cite this

Alistarh D-A, Fedorov A, Koval N. In search of the fastest concurrent union-find algorithm. In: Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.OPODIS.2019.15
Alistarh, D.-A., Fedorov, A., & Koval, N. (2020). In search of the fastest concurrent union-find algorithm (Vol. 153). Presented at the OPODIS: International Conference on Principles of Distributed Systems, Neuchatal, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15
Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of the Fastest Concurrent Union-Find Algorithm,” Vol. 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.15.
D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent union-find algorithm,” presented at the OPODIS: International Conference on Principles of Distributed Systems, Neuchatal, Switzerland, 2020, vol. 153.
Alistarh D-A, Fedorov A, Koval N. 2020. In search of the fastest concurrent union-find algorithm. OPODIS: International Conference on Principles of Distributed Systems, LIPIcs, vol. 153.
Alistarh, Dan-Adrian, et al. In Search of the Fastest Concurrent Union-Find Algorithm. Vol. 153, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.OPODIS.2019.15.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2020-03-23
MD5 Checksum
d66f07ecb609d9f02433e39f80a447e9


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1911.06347

Search this title in

Google Scholar
ISBN Search