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


 
 

 

Techniques for Designing Efficient Parallel Graph Algorithms for SMPs and Multicore Processors

Graph problems are finding increasing applications in high performance computing disciplines. Although many regular problems can be solved efficiently in parallel, obtaining efficient implementations for irregular graph problems remains a challenge. We propose techniques for designing and implementing efficient parallel algorithms for graph problems on symmetric multiprocessors and chip multiprocessors with a case study of parallel tree and connectivity algorithms. The problems we study represent a wide range of irregular problems that have fast theoretic parallel algorithms but no known efficient parallel implementations that achieve speedup without serious restricting assumptions about the inputs. We believe our techniques will be of practical impact in solving largescale graph problems.

Publication History

Versions of this paper appeared as:
  1. G. Cong, D.A. Bader, ``Techniques for Designing Efficient Parallel Graph Algorithms for SMPs and Multicore Processors,'' The 5th International Symposium on Parallel and Distributed Processing and Applications (ISPA 2007), Niagara Falls, Ontario, Canada, August 29-31, 2007.

Download this report in Adobe PDF


 
 

Last updated: November 30, 2007

 




Computational Biology



Parallel Computing



Combinatorics