GAP logo

Graph Processing
Workload Characterization

There has been substantial research interest in graph processing systems. To best guide that research, it is important to understand the workload characteristics of graph processing to understand its corresponding implementation and architectural needs. There is some "conventional wisdom" about the properties of graph algorithms, but it is important to actually profile workloads to confirm or challenge these assumptions.

In this workload characterization study, we use hardware performance counters to identify and quantify bottlenecks of full-size graph processing workloads running on real hardware (dual-socket Intel Ivy Bridge). We use 3 high-performance implementations (GAP, Galois, Ligra) of 5 different graph kernels executing on 5 different input graphs. This site is a summary of the main single-thread results, but we encourage those interested to consult our paper for details.

Main Results

Figure 1: Compute throughput & memory bandwidth utilization for 1 thread.

Figure 2: Memory bandwidth utilization limited by high IPM.


  1. "Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server", Scott Beamer, Krste Asanović, and David Patterson, International Symposium on Workload Characterization (IISWC), Atlanta, October 2015. PDF IEEE
    Best Paper Award
  2. "Understanding and Improving Graph Algorithm Performance", Scott Beamer, Ph.D. Thesis, University of California Berkeley, September 2016. PDF TR
    SPEC Kaivalya Dixit Distinguished Dissertation Award

GAP Project Home