854.graph500_s
Graph Analytics
The Graph500 Steering Committee benchmark authors include:
854.graph500_s was submitted to the SPEC CPU v8 Benchmark Search Program by David A. Bader.
Graph500 is an application designed to evaluate the performance of both single node and exascale systems at executing graph algorithms. It was initially developed for the Department of Defense (DOD) to aid in the procurement of computing systems for data intensive tasks that could not be addressed by the existing HPC Top500 floating point benchmarks. As a result, a Steering Committee of over 50 international HPC experts from academia, industry, and national laboratories came together to develop Graph500 for addressing data-intensive search, optimization and edge-oriented operations.
Graph500 is now a widely used application in both the public and private sector for various benchmarking use cases, including sizing systems, because it aligns with the data-intensive workloads on modern CPU's. It was designed with simplicity in mind, allowing users to run the reference implementation or implement it on dedicated and specialized hardware. Graph500 also includes the Kronecker Graph Generator to allow flexibility of inputs when testing out graph networks of various sizes. Per a study published in the Journal of Machine Learning Research, "Kronecker graphs naturally obey common network properties, and can effectively model the structure of real networks".
BFS The 854.graph500_s benchmark runs a set of data-intensive algorithms, with the most notable being Breadth-First Search (BFS). BFS is a fundamental graph traversal algorithm that explores all the vertices at the current depth prior to moving on to vertices at the next depth level. It is commonly used in applications where understanding the relationships and connectivity patterns within a graph is important. The BFS algorithm is traditionally in the Graph500 benchmark that can be downloaded from Graph500 Github Source. It was chosen for inclusion in this benchmark due to its simplicity - currently, it is one of the most simple search operations for computer architects to understand, and it provides insights into how other graph algorithms will run on different architectures. This is because BFS tests several critical aspects of system performance, such as not excessively filling up cache lines or overusing memory bandwidth. Efficiently stepping through adjacency lists (the lists of nodes connected to each node) in BFS is a good indicator that the system can handle other graph operations effectively.
APSP The second algorithm included in the 854.graph500_s benchmark is All Pairs Shortest Path (APSP) developed by Floyd Warshall. APSP is used to find the shortest paths between each pair of vertices in a graph network. It is useful for solving optimization problems, such as finding the shortest paths between two locations or determining the optimal paths between network devices. The algorithm is versatile because it can handle both negative and positive graph weights, which differentiates it from other commonly used shortest path algorithms, such as Dijkstra's algorithm. APSP is not traditionally included in the original Graph500 benchmark but was added to this benchmark version because it is more computationally intensive than Single Source Shortest Path (SSSP).
Dijkstra The third algorithm included in the 854.graph500_s benchmark is Dijkstra algorithm. The Dijkstra's algorithm is not run during the benchmark, but instead is used to validate the output of APSP. It is one of the most efficient algorithms for finding the shortest paths with non-negative edge weights.
The 854.graph500_s BFS implementation is the same as used in the traditional Graph500 benchmark. The implementation starts by generating the graph network input using the Kronecker graph generator outside of the measured runtime. The generator produces edge tuples containing the start vertex and end vertex for each edge, and then constructs a undirected graph that can be traversed by BFS. The graph inputs were chosen to match the expected density of edges to vertices for sparse graphs, mimicking the same properties found in social and cybersercurity networks. The BFS graph inputs are, as follows:
| Workload | Scale Factor (-s) |
# of Vertices [2^scale] |
Edge-factor (-e) |
# of Edges [edgefactor * vertices] |
Prep Graph Data (-P) |
Graph Output (-o) |
Run BFS (-f) |
| Test | 18 | 262,144 | 16 | 4,194,304 | bfs_test.bin | True | True |
| Train | 20 | 1,048,576 | 16 | 16,777,216 | bfs_train.bin | True | True |
| Refspeed | 26 | 67,108,864 | 16 | 1,073,741,824 | bfs_refspeed.bin | True | True |
The 854.graph500_s APSP implementation is an addition to Graph500, showcasing the versitility of the application at running custom algorithms and real-world datasets. The APSP algorithm finds the shortest path between all pairs of vertices in a weighted road network graph. The road network used is the New York City Distance Graph from the 9th DIMACS Implementation Challenge. Since the road network is large, a subset region was used (first 16000 nodes) to ensure the benchmark could meet full runtime requirements. The arguments used to run APSP with the NY road network are, as follows:
| Workload | # of Vertices(-p) | # of Edges (-m) |
APSP Graph Input (-q) |
Run APSP (-g) |
| Test | 100 | 62 | apsp_NYroad_62.bin | True |
| Train | 8000 | 9491 | apsp_NYroad_9491.bin | True |
| Refspeed | 16000 | 19384 | apsp_NYroad_19384.bin | True |
The output of the benchmark illustrates the Success or Failure of each BFS and APSP algorithm. In the case of BFS, the operation is run 64 times from different root points, which is the same number of times as executed in the traditional Graph500 benchmark. After each run, the total number of vertices and edges of the traversed graph is reported. Additionally, the tree generated by the BFS traversal is verified against a variety of rules to ensure correctness. This includes verifying that the tree has a single valid root vertex, each vertex is only visited once, the tree is traversed in the correct order from vertex to parent, connected vertices contain only single level differences, and every edge has been seen in the edge list. If all rules are met and edges match the original graph edge list, 'Success' is printed for each of the 64 BFS operations. This can found in the file bfs_refspeed.bin.out
During the APSP run, the algorithm iterates over the graph's vertices and updates the distance matrix based on the current vertex. After computing the shortest paths for all vertex pairs, it writes the distances from a source node to various other nodes into an output file for validation. These shortest path distances are then compared against the distances from the Dijkstra expected output for the same graph. The verification process loads distance matrices from APSP and Dijkstra algorithm outputs into memory and compares them element-by-element, returning true if all checked pairs match. If all distances match between vertex pairs, "Successful Validation" is printed. Furthermore, we conduct a comparative analysis of the sizes of the two files containing the vertex pair distances. The verification process also confirms that the value of -p (numvert) aligns with expectations and thoroughly examines all vertices. This can be found in the file verify_apsp.out
C
None.
The benchmark uses OpenMP.
The Graph500 application is publicly available for download via the Graph500 Github Source. The author has licensed this benchmark under the same NCSA Open Source license as Graph500, defined in graph500.license.txt, with copyright: Copyright (c) 2011-2017 Graph500 Steering Committee.
The source code used in this benchmark was taken from branch v2-spec, which contains openmp support and the traditional BFS implementation. This code was updated by the author to include the APSP implementation and Dijkstra check. This branch is licensed under the BSD 3-Clause and contains the following copyright information defined in graph500.copying.v2-spec.txt:
The Kronecker graph generator used is licensed under the Boost v1.0 license with copyright: (C) 2009-2010 The Trustees of Indiana University. See kronecker.license.txt for all licensing and copyright verbiage.
The New York road network dataset can be downloaded from the 9th DIMACS Implementation Challenge - Shortest Paths website, and is licensed under the public domain. See NYroad_network.license.txt.
Kim Grasman's getopt_port is used under a BSD-3 license.
Copyright © 2026 Standard Performance Evaluation Corporation (SPEC®)