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.
- "SYNERGY: Rethinking Secure-Memory Design for Error-Correcting Memories", Gururaj Saileshwar, Prashant Nair, Prakash Ramrakhyani, Wendy Elssaser and Moinuddin K. Qureshi, International Symposium on High Performance Computer Architecture (HPCA), 2018.
- "Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling", Michael Sutton, Tal Ben-Nun, Amnon Barak, International Parallel & Distributed Processing Symposium (IPDPS), 2018.
- "Near-data Processing for Dynamic Graph Analytics", Eric Robert Hein, Ph.D. Thesis, Georgia Institute of Technology, 2018.
- "ACCORD: Enabling Associativity for Gigascale DRAM Caches by Coordinating Way-Install and Way-Prediction", Vinson Young, Chia-Chen Chou, Aamer Jaleel, Moinuddin K. Qureshi, International Symposium on Computer Architecture (ISCA), 2018.
- "Exploring Core and Cache Hierarchy Bottlenecks in Graph Processing Workloads", Abanti Basak, Xing Hu, Shuangchen Li, Sang Min Oh, Yuan Xie, Computer Architecture Letters (CAL), 2018.
- "Maintaining Canonical Form After Edge Deletion", Eric Fritz, Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), 2018.
- "Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs", Vignesh Balaji, Brandon Lucia, International Symposium on Workload Characterization (IISWC), 2018.
- "Log(Graph): A Near-Optimal High-Performance Graph Representation", Maciej Besta†, Dimitri Stanojevic, Tijana Zivic, Jagpreet Singh, Maurice Hoerold, Torsten Hoefler, Parallel Architectures and Compilation Techniques (PACT), 2018.