LIPIcs.OPODIS.2019.15.pdf
- Filesize: 12.46 MB
- 16 pages
Document
In Search of the Fastest Concurrent Union-Find Algorithm
Authors
-
Part of:
Volume:
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-02-11
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.15
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Concurrent algorithms
- Computing methodologies → Concurrent algorithms
- Theory of computation → Graph algorithms analysis
Keywords
- union-find
- concurrency
- evaluation
- benchmarks
- hardware transactional memory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amazon Web Services (AWS) - Cloud Computing Services. https://aws.amazon.com/, 2019.
- JMH - Java Microbenchmark Harness. https://openjdk.java.net/projects/code-tools/jmh/, 2019.
- Packet Bare Metal - Cloud & Edge Computing Infrastructure Provider. https://www.packet.com/, 2019.
-
Dan Alistarh, Alexander Fedorov, and Nikita Koval. In Search of the Fastest Concurrent Union-Find Algorithm. arXiv preprint arXiv:1911.06347, 2019.
-
Richard J. Anderson and Heather Woll. Wait-free Parallel Algorithms for the Union-Find Problem. In In Proc. 23rd ACM Symposium on Theory of Computing, pages 370-380, 1994.
-
Otakar Boruvka. O jistém problému minimálním. 1926.
-
George Cybenko, T. G. Allen, and J. E. Polito. Practical parallel Union-Find algorithms for transitive closure and clustering. International Journal of Parallel Programming, 17:403-423, 1988.
-
E.W. Dijkstra. A discipline of programming. Prentice-Hall series in automatic computation. Prentice-Hall, 1976.
- Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, and Robert Tarjan. Disjoint Set Union with Randomized Linking. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1005-1017, January 2014. URL: https://doi.org/10.1137/1.9781611973402.75.
- Siddhartha Jayanti and Robert Tarjan. A Randomized Concurrent Algorithm for Disjoint Set Union. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 75-82, July 2016. URL: https://doi.org/10.1145/2933057.2933108.
-
Siddhartha V. Jayanti, Robert E. Tarjan, and Enric Boix-Adserà. Randomized Concurrent Set Union and Generalized Wake-Up. In PODC, 2019.
-
Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-50, 1956.
- Michael L. Fredman and Michael Saks. The Cell Probe Complexity of Dynamic Data Structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 345-354, January 1989. URL: https://doi.org/10.1145/73007.73040.
-
Vitaly Osipov, Peter Sanders, and Johannes Singler. The Filter-Kruskal Minimum Spanning Tree Algorithm. In ALENEX, 2009.
-
Md Mostofa Ali Patwary, Jean Blair, and Fredrik Manne. Experiments on union-find algorithms for the disjoint-set data structure. In International Symposium on Experimental Algorithms, pages 411-423. Springer, 2010.
-
Ravi Rajwar and James R Goodman. Speculative lock elision: Enabling highly concurrent multithreaded execution. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 294-305. IEEE Computer Society, 2001.
-
Robert E. Tarjan and Jan van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, 31:245-281, 1984.
- Robert Endre Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM, 22(2):215-225, April 1975. URL: https://doi.org/10.1145/321879.321884.
-
Robert Endre Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of computer and system sciences, 18(2):110-127, 1979.