TY - GEN
T1 - Simple parallel biconnectivity algorithms for multicore platforms
AU - Slota, George M.
AU - Madduri, Kamesh
N1 - Publisher Copyright:
© 2014 IEEE.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - We present two new algorithms for finding the biconnected components of a large undirected sparse graph. The first algorithm is based on identifying articulation points and labeling edges using multiple connectivity queries, and the second approach uses the color propagation technique to decompose the graph. Both methods use a breadth-first spanning tree and some auxiliary information computed during Breadth-First Search (BFS). These methods are simpler than the Tarjan-Vishkin PRAM algorithm for biconnectivity and do not require Euler tour computation or any auxiliary graph construction. We identify steps in these algorithms that can be parallelized in a shared-memory environment and develop tuned OpenMP implementations. Using a collection of large-scale real-world graph instances, we show that these methods outperform the state-of-the-art Cong-Bader biconnected components implementation, which is based on the Tarjan-Vishkin algorithm. We achieve up to 7.1× and 4.2× parallel speedup over the serial Hopcroft-Tarjan and parallel Cong-Bader algorithms, respectively, on a 16-core Intel Sandy Bridge system. For some graph instances, due to the fast BFS-based preprocessing step, the single-threaded implementation of our first algorithm is faster than the serial Hopcroft-Tarjan algorithm.
AB - We present two new algorithms for finding the biconnected components of a large undirected sparse graph. The first algorithm is based on identifying articulation points and labeling edges using multiple connectivity queries, and the second approach uses the color propagation technique to decompose the graph. Both methods use a breadth-first spanning tree and some auxiliary information computed during Breadth-First Search (BFS). These methods are simpler than the Tarjan-Vishkin PRAM algorithm for biconnectivity and do not require Euler tour computation or any auxiliary graph construction. We identify steps in these algorithms that can be parallelized in a shared-memory environment and develop tuned OpenMP implementations. Using a collection of large-scale real-world graph instances, we show that these methods outperform the state-of-the-art Cong-Bader biconnected components implementation, which is based on the Tarjan-Vishkin algorithm. We achieve up to 7.1× and 4.2× parallel speedup over the serial Hopcroft-Tarjan and parallel Cong-Bader algorithms, respectively, on a 16-core Intel Sandy Bridge system. For some graph instances, due to the fast BFS-based preprocessing step, the single-threaded implementation of our first algorithm is faster than the serial Hopcroft-Tarjan algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84977958646&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977958646&partnerID=8YFLogxK
U2 - 10.1109/HiPC.2014.7116914
DO - 10.1109/HiPC.2014.7116914
M3 - Conference contribution
AN - SCOPUS:84977958646
T3 - 2014 21st International Conference on High Performance Computing, HiPC 2014
BT - 2014 21st International Conference on High Performance Computing, HiPC 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 21st International Conference on High Performance Computing, HiPC 2014
Y2 - 17 December 2014 through 20 December 2014
ER -