Benchmark
Suite

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.

References

1. The GAP Benchmark Suite, Scott Beamer, Krste Asanović, and David Patterson, arXiv:1508.03619 [cs.DC], 2015. arXiv
2. "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
3. "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

External-User Publications

1. "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
2. "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
3. "Optimizing Indirect Memory References with milk", Vladimir Kiriansky, Yunming Zhang, and Saman Amarasinghe, International Conference on Parallel Architectures and Compilation (PACT), 2016. ACM
4. "GoblinCore-64: A Scalable, Open Architecture for Data Intensive High Performance Computing", John D. Leidel, Ph.D. Thesis, Texas Tech University, 2017.
5. "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.
6. "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.
7. "Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling", Michael Sutton, Tal Ben-Nun, Amnon Barak, International Parallel & Distributed Processing Symposium (IPDPS), 2018.
8. "Near-data Processing for Dynamic Graph Analytics", Eric Robert Hein, Ph.D. Thesis, Georgia Institute of Technology, 2018.
9. "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.
10. "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.
11. "Maintaining Canonical Form After Edge Deletion", Eric Fritz, Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), 2018.
12. "When is Graph Reordering an Optimization? Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs", Vignesh Balaji, Brandon Lucia, International Symposium on Workload Characterization (IISWC), 2018.
13. "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.
14. "SPF: Selective Pipeline Flush", Vignyan Reddy Kothinti Naresh, Rami Sheikh, Arthur Perais, Harold W. Cain, International Conference on Computer Design (ICCD), 2018.
15. "GoblinCore-64: A RISC-V Based Architecture for Data Intensive Computing", John D. Leidel, Xi Wang, Yong Chen, High Performance extreme Computing Conference (HPEC), 2018.
16. "Morphable Counters: Enabling Compact Integrity Trees For Low-Overhead Secure Memories", Gururaj Saileshwar, Prashant Nair, Prakash Ramrakhyani, Wendy Elsasser, Jose Joao, Moinuddin Qureshi, International Symposium on Microarchitecture (MICRO), 2018.
17. "CEASER: Mitigating Conflict-Based Cache Attacks via Encrypted-Address and Remapping", Moinuddin K. Qureshi, International Symposium on Microarchitecture (MICRO), 2018.
18. "Attaché: Towards Ideal Memory Compression by Mitigating Metadata Bandwidth Overheads", Seokin Hong, Prashant Jayaprakash Nair, Bulent Abali, Alper Buyuktosunoglu, Kyu-Hyoun Kim, Michael Healy, International Symposium on Microarchitecture (MICRO), 2018.
19. "Many-core Graph Workload Analysis", Stijn Eyerman, Wim Heirman, Kristof Du Bois, Joshua B. Fryman, Ibrahim Hur, International Conference for High Performance Computing, Networking, Storage, and Analysis (SC), 2018.
20. "Enabling Transparent Memory-Compression for Commodity Memory Systems", Vinson Young, Sanjay Kariyappa, Moinuddin K. Qureshi, International Symposium on High Performance Computer Architecture (HPCA), 2019.

GAP Project Home