GAIL: The graph algorithm iron law

Copyright 2015 ACM. 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