Graph500 Benchmark: Scalable Kronecker Graph Generator
Jeremiah Willcock and Andrew Lumsdaine

This directory contains a parallel Kronecker graph generator, as well as a
random permutation generator and code to apply a distributed permutation to the
endpoints of the elements of an edge list.  The benefits of this approach are
two-fold: first, the generated graphs and permutations are consistent for a
given graph size, initiator, and seed, regardless of shared vs. distributed
memory or processor count; and second, the generator detects parallel edges
(including those with the endpoints given in the opposite order for an
undirected graph) automatically and without needing to store the edges
explicitly.  Its main disadvantage is that some performance is lost through the
use of a more sophisticated pseudo-random number generator (PRNG); if
reproducibility is not required, a cheaper PRNG can be used for more
performance while keeping the parallel edge detection property.

Four Makefiles are provided: Makefile.seq (sequential), Makefile.xmt (Cray
XMT), Makefile.omp (OpenMP), and Makefile.mpi (MPI).  There are three
corresponding generator_test_* programs that demonstrate how to use the
generator.  The file make_graph.h declares a simplified interface suitable for
benchmark implementations; this interface hides many of the parameters that are
fixed in the benchmark specification.  Most compile-time settings are at the
top of graph_generator.h; users should not need to modify most of them, except
for possibly data type sizes.  Developers of the benchmark specification itself
might benefit from playing around with different initiators and other settings,
however.

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 at
http://www.boost.org/LICENSE_1_0.txt)