Source-linked AI summary
The GAP Benchmark Suite
Scott Beamer, Krste Asanović, David Patterson
TL;DR
Graph-processing research lacks standardized evaluations, making comparisons vulnerable to differences in methodology, inputs, and algorithm variants. The GAP Benchmark Suite standardizes kernels, graphs, methodologies, and reference performance, enabling comparisons across conforming platforms and supporting multiple graph-processing stakeholders.
Problem
Graph-processing evaluations lack a standard, so differences in methodologies, input graphs, and algorithm variants can cloud comparisons among research results.
Method
The paper defines a benchmark suite with graph kernels, input graphs, measurement methodologies, and an optimized reference implementation, including diverse workloads.
Results
The suite provides explicit specifications and separable artifacts that allow benchmark-compliant implementations on any platform to be compared without requiring the reference implementation.
Takeaways & Limitations
The suite supports framework, algorithm, hardware, and performance evaluation by providing common workloads and state-of-the-art reference baselines.
Takeaways & Limitations
The benchmark selects a 10^-4 tolerance as a pragmatic tradeoff between score convergence and execution time, allowing some numerical noise.
Abstract
from arXiv · showhide
We present a graph processing benchmark suite with the goal of helping to standardize graph processing evaluations. Fewer differences between graph processing evaluations will make it easier to compare different research efforts and quantify improvements. The benchmark not only specifies graph kernels, input graphs, and evaluation methodologies, but it also provides optimized baseline implementations. These baseline implementations are representative of state-of-the-art performance, and thus new contributions should outperform them to demonstrate an improvement. The input graphs are sized appropriately for shared memory platforms, but any implementation on any platform that conforms to the benchmark's specifications could be compared. This benchmark suite can be used in a variety of settings. Graph framework developers can demonstrate the generality of their programming model by implementing all of the benchmark's kernels and delivering competitive performance on all of the benchmark's graphs. Algorithm designers can use the input graphs and the baseline implementations to demonstrate their contribution. Platform designers and performance analysts can use the suite as a workload representative of graph processing.
1 Introduction
The GAP Benchmark Suite addresses inconsistent graph-processing evaluations by specifying kernels, input graphs, methodologies, and an optimized reference implementation. Its artifacts support comparable studies across platforms and use cases, while diverse workloads address limitations of narrower benchmarks.
- Motivation: Graph-processing evaluations lack a standard, making published results difficult to compare and allowing methodology, graph, and algorithm-variant differences to affect outcomes.Differences such as directed versus undirected edges can impact performance by more than a claimed improvement.
- Contribution: The GAP Benchmark Suite specifies graph kernels, input graphs, measurement methodologies, and an optimized reference implementation representative of state-of-the-art performance.The suite was informed by community best practices and workload characterization emphasizing diverse kernels and input graphs.
- Contribution: Its explicit benchmark specification complements released code by defining a common workload and evaluation methodology rather than leaving evaluators to construct them independently.Independent frameworks may compute different things or use different timing practices without such specification.
- Use: The benchmark specification and reference implementation are separate artifacts, so conforming implementations on any platform can be compared without using the reference implementation.The reference implementation can also execute workloads outside the benchmark.
- Use: Framework developers, algorithm designers, hardware designers, and performance analysts can use the suite for generality, contribution baselines, or representative graph-processing workloads.The reference implementation targets shared-memory multiprocessors, but that platform is not required for benchmark use.
2 Benchmark Specification
The GAP Benchmark Suite standardizes graph-processing evaluations through explicit kernels, input graphs, methodologies, and a high-quality reference implementation. Its diverse workload and precise correctness requirements support comparable evaluations across implementations and platforms.
- Benchmark goals: The benchmark addresses evaluation shortcomings by explicitly specifying kernels, input graphs, methodologies, and rationale for its design choices.Its goals include improving comparability, providing a diverse representative workload, and grounding evaluations with strong baseline performance.
- Graph kernels: Six computationally diverse kernels cover traversal-centric and compute-centric graph processing while varying in their treatment of weights and directions.The suite includes PageRank, Connected Components, Betweenness Centrality, Breadth-First Search, Triangle Counting, and Single-Source Shortest Paths.
- Graph kernels: BFS correctness requires a parent array whose reachable vertices have an incoming parent edge and are one level deeper than their parents.The benchmark tracks parents because they enable verification of breadth-first traversal properties beyond reachability alone.
- Graph kernels: SSSP returns distances from one source to every reachable vertex, with unreachable vertices assigned infinity or a known sentinel and all benchmark edge weights positive.A correct reachable distance must correspond to a path of that combined weight and have no lower-weight path.
- Graph kernels: PageRank correctness uses a 10^-4 stopping tolerance, balancing score convergence, execution time, and numerical noise across implementations.The authors report that this tolerance produces roughly 5–20 iterations for most graphs while allowing some accumulation-order noise.
- Inputs and measurement: The suite uses five diverse real-world and synthetic graphs sized to fit server memory while exceeding processor-cache capacity, and times every trial’s complete kernel execution.Single-source kernels run 64 trials from different non-zero-degree source vertices; auxiliary data-structure construction and solution allocation are included in trial time.
3 Reference Code
The reference code implements all six benchmark kernels as a compliant, high-performance baseline while also supporting education, reuse, testing, verification, and automated execution. Its kernels use state-of-the-art or deliberately comparable algorithms with implementation optimizations and correctness checks.
- Reference implementation: The reference implementation includes all six benchmark kernels and serves as a compliant, high-performance baseline.It uses state-of-the-art algorithms and achieves competitive performance, best for some kernels.
- Reference implementation: Code quality, portability, and modifiability are supported through C++ practices, Google’s C++ style guide, and C++11 features.
- Infrastructure: The infrastructure loads, generates, builds, and serializes graphs while supporting METIS, Matrix Market, and plain-text formats.
- Verification: Testing includes graph-infrastructure tests, property-based verification for BFS, PageRank, and connected components, and serial-output comparisons for other kernels.
- Infrastructure: Automation scripts download real-world graphs, build benchmark inputs, run kernels with correct parameters, and demonstrate benchmark-compliant execution.
- Kernel implementations: Kernel implementations combine established algorithms with targeted optimizations, including direction-optimizing BFS, Δ-stepping SSSP, and thread-local bins.Thread-local bins reduce contention through bulk aggregation into a shared minimum-distance bin.
- Kernel implementations: PageRank deliberately uses a naive iterative pull approach for comparability, while checking tolerance bounds before termination.
A Change Log
The change log records revisions to the introduction, benchmark specification, reference code, and document wording. Updates include clearer use cases and correctness requirements, newer code versions, execution automation, more file formats, testing descriptions, and editorial fixes.
- Introduction: The introduction was clarified to describe possible use cases for the suite.
- Benchmark Specification: The benchmark specification was revised to clarify correct-solution requirements and convert trials and output into tables.
- Reference Code: The repository was re-uploaded after the build omitted spec.tex.
- Reference Code: The reference code was updated to versions v0.7 and v1.0, with automation for benchmark execution and support for additional input formats.
- Editorial changes: The document added acknowledgements, expanded testing and verifier descriptions, incorporated dissertation content, and received wording and grammar fixes.