GAP Benchmark Suite

The GAP Benchmark Suite (Graph Algorithm Platform), developed at UC Berkeley, standardizes how graph-processing performance is measured on shared-memory systems. It was created to fix a reproducibility problem: graph research often compared against weak baselines, making speedups misleading. GAP provides high-quality reference implementations and a fixed set of input graphs so comparisons are fair and meaningful.

The suite defines six representative graph kernels: breadth-first search (BFS), single-source shortest paths (SSSP), PageRank (PR), connected components (CC), betweenness centrality (BC), and triangle counting (TC). These cover traversal, ranking, clustering, and counting patterns common in analytics. It also specifies five input graphs spanning social, web, road, and synthetic structures.

What It Measures

GAP measures runtime for each kernel on each graph, often expressed as edges processed per second or as speedup relative to the optimized reference. Because the reference implementations are themselves highly tuned for multi-core CPUs with good cache behavior, GAP sets a demanding baseline: a new framework must beat genuinely fast code, not a naive implementation, to claim improvement.

Methodology

Each kernel runs multiple trials on the specified graphs, reporting median runtime to reduce noise. Source vertices for traversal kernels are chosen consistently. The reference code uses techniques like direction-optimizing BFS and cache-aware data layouts. Researchers run their own framework against the same graphs and kernels, then report relative performance, enabling apples-to-apples comparison across systems and software.

How to Interpret Results

Read GAP results per kernel and per graph, since performance varies sharply with graph structure — road networks have high diameter and behave very differently from social graphs. Speedup over the GAP reference is the credible claim; speedup over a naive baseline is not. Use the suite to evaluate graph frameworks, CPU memory hierarchies, and the effect of data layout and threading on irregular workloads.

Limitations

GAP targets single-node shared-memory systems, so it does not measure distributed graph processing across a cluster, where Graph500 is more relevant. The six kernels and five graphs, while well chosen, do not cover every algorithm or dataset. Results depend on compiler and NUMA tuning, and the suite measures in-memory computation only, excluding graph loading, updates, and storage that dominate some production systems.