Graph500

Richard Murphy from Sandia National Laboratories, says that "The Graph500's goal is to promote awareness of complex data problems", instead of focusing on computer benchmarks like HPL (High Performance Linpack), which TOP500 is based on.

Despite its name, there were several hundreds of systems in the rating, growing up to 174 in June 2014.

The algorithm and implementation that won the championship is published in the paper titled "Extreme scale breadth-first search on supercomputers".

There is also list Green Graph 500, which uses same performance metric, but sorts list according to performance per Watt, like Green 500 works with TOP500 (HPL).

Benchmark

The benchmark used in Graph500 stresses the communication subsystem of the system, instead of counting double precision floating-point. It is based on a breadth-first search in a large undirected graph (a model of Kronecker graph with average degree of 16). There are three computation kernels in the benchmark: the first kernel is to generate the graph and compress it into sparse structures CSR or CSC (Compressed Sparse Row/Column); the second kernel does a parallel BFS search of some random vertices (64 search iterations per run); the third kernel runs a single-source shortest paths (SSSP) computation. Six possible sizes (Scales) of graph are defined: toy (2²⁶ vertices; 17 GB of RAM), mini (2²⁹; 137 GB), small (2³²; 1.1 TB), medium (2³⁶; 17.6 TB), large (2³⁹; 140 TB), and huge (2⁴²; 1.1 PB of RAM).

The reference implementation of the benchmark contains several versions:

• serial high-level in GNU Octave
• serial low-level in C
• parallel C version with usage of OpenMP
• two versions for Cray-XMT
• basic MPI version (with MPI-1 functions)
• optimized MPI version (with MPI-2 one-sided communications)

The implementation strategy that have won the championship on the Japanese K computer is described in.