The unfortunate lack of a widely used graph benchmark suite forces each research publication to create its own evaluation methodology, and this often results in mistakes or unnecessary differences. Common serious mistakes we have observed include: using trivially small input graphs, using only a single input graph topology, or using low-performance implementations as baselines. These methodological issues make it difficult for good ideas to stand out and cloud the reasoning behind why these ideas are beneficial.
In order for the research community to make progress on accelerating graph processing, it is important to be able to properly and reliably compare results. We created the GAP Benchmark Suite to standardize evaluations in order to alleviate the methodological issues we observed. Through standardization, we hope to not only make results easier to compare, but to also prevent common evaluation mistakes. We provide both a benchmark specification to standardize the methodology and a high-performance reference implementation to be used as a baseline. Our benchmark was co-designed with our workload characterization, and it has undergone multiple revisions guided by community feedback.
View on arXiv
To remove ambiguity, we specify:
- Input Graphs - large (billions of edges), real-world & synthetically-generated
- Graph Kernels - including what constitutes a correct solution
- Evaluation best practices - timing methodologies, allowed optimizations
View on GitHub
- Fast - matches or exceeds performance of other shared-memory frameworks
- Portable - only requires C++11 & OpenMP (tested and supported on: x86/ARM/SPARC/RISC-V and gcc/icc/clang/suncc)
- Correct - verifiers to check kernel outputs
- The GAP Benchmark Suite, Scott Beamer, Krste Asanović, and David Patterson, arXiv:1508.03619 [cs.DC], 2015. arXiv
- "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
- "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
- "Whirlpool: Improving Dynamic Cache Management with Static Data Classification", Anurag Mukkara, Nathan Beckmann, and Daniel Sanchez, Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2016. ACM
- "Energy Efficient Architecture for Graph Analytics Accelerators", Mustafa Ozdal, Serif Yesil, Taemin Kim, Andrey Ayupov, John Greth, Steven M. Burns, Ozcan Ozturk, International Symposium on Computer Architecture (ISCA), 2016. ACM
- "Optimizing Indirect Memory References with milk", Vladimir Kiriansky, Yunming Zhang, and Saman Amarasinghe, International Conference on Parallel Architectures and Compilation (PACT), 2016. ACM
- "GoblinCore-64: A Scalable, Open Architecture for Data Intensive High Performance Computing", John D. Leidel, Ph.D. Thesis, Texas Tech University, 2017.
- "Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing", Laxman Dhulipala, Guy Blelloch, and Julian Shun, Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017.