PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Mon 14 Mar 2016 14:45 - 15:10 at Mallorca+Menorca - Algorithms Chair(s): Lawrence Rauchwerger

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 Mar
Times are displayed in time zone: (GMT+01:00) Greenwich Mean Time : Belfast change

14:20 - 16:00: Main conference - Algorithms at Mallorca+Menorca
Chair(s): Lawrence RauchwergerTexas A&M University
PPoPP-2016-papers14:20 - 14:45
Lei WangInstitute of Computing Technology, Chinese Academy of Science, Fan YangInstitute of Computing Technology, Chinese Academy of Science, Liangji ZhuangInstitute of Computing Technology, Chinese Academy of Science, Huimin CuiInstitute of Computing Technology, Chinese Academy of Sciences, Fang LvInstitute of Computing Technology, Chinese Academy of Sciences, Xiaobing FengICT CAS
Link to publication DOI
PPoPP-2016-papers14:45 - 15:10
Vincent BloemenUniversity of Twente, Alfons LaarmanVienna University of Technology, Jaco van de PolUniversity of Twente
Link to publication DOI
PPoPP-2016-papers15:10 - 15:35
Ramakrishnan KannanGeorgia Institute of Technology, Grey BallardSandia National Laboratories, Haesun ParkGeorgia Institute of Technology
Link to publication DOI
PPoPP-2016-papers15:35 - 16:00
Rezaul ChowdhuryStony Brook University, Pramod GanapathiStony Brook University, Jesmin Jahan TithiIntel, CA, USA, Charles BachmeierMIT, Bradley KuszmaulMIT, Charles E. LeisersonMIT, Armando Solar-LezamaMIT, Yuan TangFudan University
Link to publication DOI