The main advantages of Tarjan’s strongly connected component (SCC) algorithm are its linear time complexity and ability to return SCCs on-the-fly, while traversing or even generating the graph. Until now, most parallel SCC algorithms sacrifice both: they run in quadratic worst-case time and/or require the full graph in advance.
The current paper presents a novel parallel, on-the-fly SCC algorithm. It preserves the linear-time property by letting workers explore the graph randomly while carefully communicating partially completed SCCs. We prove that this strategy is correct. For efficiently communicating partial SCCs, we develop a concurrent, iterable disjoint set structure (combining the union-find data structure with a cyclic list).
We demonstrate scalability on a 64-core machine using 75 real-world graphs (from model checking and explicit data graphs), synthetic graphs (combinations of trees, cycles and linear graphs), and random graphs. Previous work did not show speedups for graphs containing a large SCC. We observe that our parallel algorithm is typically 10-30× faster compared to Tarjan’s algorithm for graphs containing a large SCC. Comparable performance (with respect to the current state-of-the-art) is obtained for graphs containing many small SCCs.
Mon 14 MarDisplayed time zone: Belfast change
14:20 - 16:00
|Articulation Point Guided Redundancy Elimination for Betweenness Centrality |
Lei Wang Institute of Computing Technology, Chinese Academy of Science, Fan Yang Institute of Computing Technology, Chinese Academy of Science, Liangji Zhuang Institute of Computing Technology, Chinese Academy of Science, Huimin Cui Institute of Computing Technology, Chinese Academy of Sciences, Fang Lv Institute of Computing Technology, Chinese Academy of Sciences, Xiaobing Feng ICT CASLink to publication DOI
|Multi-Core On-The-Fly SCC Decomposition|
Vincent Bloemen University of Twente, Alfons Laarman Vienna University of Technology, Jaco van de Pol University of TwenteLink to publication DOI
|A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization |
Ramakrishnan Kannan Georgia Institute of Technology, Grey Ballard Sandia National Laboratories, Haesun Park Georgia Institute of TechnologyLink to publication DOI
|Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs|
Rezaul Chowdhury Stony Brook University, Pramod Ganapathi Stony Brook University, Jesmin Jahan Tithi Intel, CA, USA, Charles Bachmeier MIT, Bradley Kuszmaul MIT, Charles E. Leiserson MIT, Armando Solar-Lezama MIT, Yuan Tang Fudan UniversityLink to publication DOI