GAIL: The Graph Algorithm Iron Law

As new applications for graph algorithms emerge, there has

been a great deal of research interest in improving graph

processing. However, it is often difficult to understand how

these new contributions improve performance. Execution

time, the most commonly reported metric, distinguishes which

alternative is the fastest but does not give any insight as to

why. A new contribution may have an algorithmic innova-
tion that allows it to examine fewer graph edges. It could

also have an implementation optimization that reduces com-
munication. It could even have optimizations that allow it to

increase its memory bandwidth utilization. More interest-
ingly, a new innovation may simultaneously affect all three

of these factors (algorithmic work, communication volume,

and memory bandwidth utilization). We present the Graph

Algorithm Iron Law (GAIL) to quantify these tradeoffs to

help understand graph algorithm performance.