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 hidden constant factors buried in the asymptotic notations; 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 upto 4 at 12
processors on SUN E4500 for large, sparse graphs, and the source code is
freely-available at our web site.
