Graph500 Benchmark: MPI Reference ImplementationJeremiah Willcock and Andrew Lumsdaine This directory contains an MPI-based reference implementation for the Graph500benchmark.  The Makefile will automatically build the supporting code, alongwith two reference implementations of breadth-first search and a skeletonversion for users to modify.  The Makefile may need to be modified with yourMPI location and compiler flags.  The generated programs, named graph500_mpi_*,take up to two parameters: the scale of the problem and the edge factor.  Theproblem scale is the logarithm, base 2, of the number of vertices in the graph;only graphs with power-of-2 vertex counts are supported without source codemodification.  The edge factor is the ratio of the number of edges to thenumber of vertices; i.e., it is half the average vertex degree in the graph.The scale parameter is mandatory; the edge factor is optional and defaults to16 (the value specified by the benchmark).  Running any of the graph500_mpi_*programs without any arguments will produce a usage message. The code is written in C; the code compiles with GCC's default gnu89 languagesetting, but should be valid C99 and C++ (except for the use of a few C99headers).  The main non-C89 features used are variable declarations afterstatements in a block and the <stdint.h> and <inttypes.h> headers. A template for writing your own BFS using the reference data structures andinfrastructure is in bfs_custom.c.  You can either modify that file in place orcopy it (adjusting the Makefile) to create your own version.  The documentationfor what data structures are available and how to use them is in comments inbfs_custom.c.  The reference implementation also contains code to convert froma distributed list of graph edges into a distributed compressed sparse row datastructure, as well as code for timing the BFS run, validating the correctnessof the results, and printing the timings in the Graph500-required format. Copyright (C) 2009-2010 The Trustees of Indiana University. Use, modification and distribution is subject to the Boost Software License,Version 1.0. (See accompanying file LICENSE_1_0.txt or copy athttp://www.boost.org/LICENSE_1_0.txt)