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


 
 

 

Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors

Graph theoretic problems are representative of fundamental computations in traditional and emerging scientific disciplines like scientific computing and computational biology, as well as applications in national security. We present our design and implementation of a graph theory application that supports the kernels from the Scalable Synthetic Compact Applications (SSCA) benchmark suite, developed under the DARPA High Productivity Computing Systems (HPCS) program. This synthetic benchmark consists of four kernels that require irregular access to a large, directed, weighted multi-graph. We have developed a parallel implementation of this benchmark in C using the POSIX thread library for commodity symmetric multiprocessors (SMPs). In this paper, we primarily discuss the data layout choices and algorithmic design issues for each kernel, and also present execution time and benchmark validation results.

Code: DARPA High Productivity Computing Systems, Scalable Synthetic Compact Application #2
[Also available from Software link]

Publication History

Versions of this paper appeared as:
  1. D.A. Bader, K. Madduri ``Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors,'' Technical Report, Georgia Institute of Technology, May 2005.
  2. D.A. Bader, K. Madduri ``Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors,'' Proc. 12th International Conference on High Performance Computing (HiPC 2005), Goa, India, Lecture Notes in Computer Science, 3769:465-476, December 2005.

Download this report in Adobe PDF


 
 

Last updated: December 23, 2005

 




Computational Biology



Parallel Computing



Combinatorics