TY - GEN
T1 - An experimental study of parallel biconnected components algorithms on symmetric multiprocessors (SMPs)
AU - Cong, Guojing
AU - Bader, David A.
PY - 2005
Y1 - 2005
N2 - We present an experimental study of parallel biconnected components algorithms employing several fundamental parallel primitives, e.g., prefix sum, list ranking, sorting, connectivity, spanning tree, and tree computations. Previous experimental studies of these primitives demonstrate reasonable parallel speedups. However, when these algorithms are used as subroutines to solve higher-level problems, there are two factors that hinder fast parallel implementations. One is parallel overhead, i.e., the large constant factors hidden in the asymptotic bounds; the other is the discrepancy among the data structures used in the primitives that brings non-negligible conversion cost. We present various optimization techniques and a new parallel algorithm that significantly improve the performance of finding biconnected components of a graph on symmetric multiprocessors (SMPs). Finding biconnected components has application in fault-tolerant network design, and is also used in graph planarity testing. Our parallel implementation achieves speedups up to 4 using 12 processors on a Sun E4500 for large, sparse graphs, and the source code is freely-available at our web site http://www.ece.unm.edu/~dbader.
AB - We present an experimental study of parallel biconnected components algorithms employing several fundamental parallel primitives, e.g., prefix sum, list ranking, sorting, connectivity, spanning tree, and tree computations. Previous experimental studies of these primitives demonstrate reasonable parallel speedups. However, when these algorithms are used as subroutines to solve higher-level problems, there are two factors that hinder fast parallel implementations. One is parallel overhead, i.e., the large constant factors hidden in the asymptotic bounds; the other is the discrepancy among the data structures used in the primitives that brings non-negligible conversion cost. We present various optimization techniques and a new parallel algorithm that significantly improve the performance of finding biconnected components of a graph on symmetric multiprocessors (SMPs). Finding biconnected components has application in fault-tolerant network design, and is also used in graph planarity testing. Our parallel implementation achieves speedups up to 4 using 12 processors on a Sun E4500 for large, sparse graphs, and the source code is freely-available at our web site http://www.ece.unm.edu/~dbader.
UR - http://www.scopus.com/inward/record.url?scp=33746279468&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746279468&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2005.100
DO - 10.1109/IPDPS.2005.100
M3 - Conference contribution
AN - SCOPUS:33746279468
SN - 0769523129
SN - 0769523129
SN - 9780769523125
T3 - Proceedings - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
SP - 45b
BT - Proceedings - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
T2 - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005
Y2 - 4 April 2005 through 8 April 2005
ER -