GAP logo

Graph Algorithm Iron Law (GAIL)

Simply knowing a new approach is faster is much less useful than knowing why the new approach is faster. In the case of graph processing research, many projects span multiple laters of the computational stack, making it difficult to determine which factors are responsible for a performance improvement. To understand these performance improvements will require metrics more introspective than execution time.

We present the Graph Algorithm Iron Law (GAIL) to weigh the tradeoffs between the three most important graph algorithm performance factors: algorithm, implementation, and hardware platform. To quantify algorithmic work, we annotate the code to count the number of edges traversed. From our characterization work, the interaction between the implementation and the platform is best summarized by examining locality (quantified by memory requests) and memory bandwidth utilization. With GAIL, we factor these terms analogously to the CPU Iron Law:

Graph Algorithm Iron Law (GAIL)

As a simple example of using GAIL, we compare the performance of three breadth-first search (BFS) implementations traversing the same input graph using the same hardware platform. From the execution time, we see the direction-optimizing implementation is the fastest, but there is no indication as to what is driving the speedup. A different implementation is best at each metric (lower is better), but with GAIL, these differences can be quantitatively weighed to asses tradeoffs. In this case, the algorithmic reduction in edges traversed by the direction-optimizing implementation trumps its poor cache locality and memory bandwidth utilization.

GAIL Example with BFS
Three breadth-first search implementations compared by GAIL


  1. "GAIL: The Graph Algorithm Iron Law", Scott Beamer, Krste Asanović, and David Patterson, Workshop on Irregular Applications: Architectures and Algorithms (IA^3), at the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), Austin, November 2015. PDF slides ACM
  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