Benchmark
Overview
We present a graph theory benchmark representative of computational kernels in computational biology, complex network analysis, and national security. This benchmark is based on the HPCS Scalable Synthetic Compact Applications graph analysis (SSCA#2) benchmark. SSCA#2 is characterized by integer operations, a large memory footprint, and irregular memory access patterns. It has multiple kernels accessing a single data structure representing a weighted, directed multigraph. In addition to a kernel to construct the graph from the input tuple list, there are three additional computational kernels to operate on the graph. Each of the kernels requires irregular access to the graph's data structure, and it is possible that no single data layout will be optimal for all four computational kernels.
References
- HPC Scalable Graph Analysis Benchmark v1.0 (24 February 2009)
- Specification: pdf
- Sequential Matlab code: gabSer-v1.0.zip
- SSCA#2 v2.2 Specification (5 September 2007): pdf doc
- Sequential and Parallel code: C and C/OpenMP
- SSCA#2 v2.1 Specification (1 November 2006): pdf doc
- Sequential code: C
- Parallel code: C/OpenMP
- Matlab version: ssca2v2-061107.tar.gz
- SSCA#2 v2.0 Specification (16 August 2006): pdf doc
Related Publications
The written specification is the primary reference document for the current benchmark version (SSCA#2 v2.1).
The following papers discuss algorithms and implementations of earlier versions:
- D.A. Bader and K. Madduri, "Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors," The 12th International Conference on High Performance Computing (HiPC 2005), D.A. Bader et al., (eds.), Springer-Verlag LNCS 3769, 465-476, Goa, India, December 2005.
- J.R. Gilbert and S. Reinhardt and V. Shah, "High Performance Graph Algorithms from Parallel Sparse Matrices," Workshop on the State-of-the-art in Scientific and Parallel Computing (PARA 2006), Umea, Sweden, June 2006.