David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)

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.

Publication History

Versions of this paper appeared as:
  1. G. Cong and D.A. Bader, ``An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs),'' Department of Electrical and Computer Engineering, University of New Mexico, October 2004.
  2. G. Cong and D.A. Bader, ``An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs),'' 19th IEEE Int'l Parallel and Distributed Processing Symp. (IPDPS), Denver, CO, April 4-8, 2005.

Download this report in Adobe PDF


 
 

Last updated: August 5, 2006

 




Computational Biology



Parallel Computing



Combinatorics