Graph500 Benchmark: Scalable Kronecker Graph GeneratorJeremiah Willcock and Andrew Lumsdaine This directory contains a parallel Kronecker graph generator, as well as arandom permutation generator and code to apply a distributed permutation to theendpoints of the elements of an edge list.  The benefits of this approach aretwo-fold: first, the generated graphs and permutations are consistent for agiven graph size, initiator, and seed, regardless of shared vs. distributedmemory or processor count; and second, the generator detects parallel edges(including those with the endpoints given in the opposite order for anundirected graph) automatically and without needing to store the edgesexplicitly.  Its main disadvantage is that some performance is lost through theuse of a more sophisticated pseudo-random number generator (PRNG); ifreproducibility is not required, a cheaper PRNG can be used for moreperformance while keeping the parallel edge detection property. Four Makefiles are provided: Makefile.seq (sequential), Makefile.xmt (CrayXMT), Makefile.omp (OpenMP), and Makefile.mpi (MPI).  There are threecorresponding generator_test_* programs that demonstrate how to use thegenerator.  The file make_graph.h declares a simplified interface suitable forbenchmark implementations; this interface hides many of the parameters that arefixed in the benchmark specification.  Most compile-time settings are at thetop of graph_generator.h; users should not need to modify most of them, exceptfor possibly data type sizes.  Developers of the benchmark specification itselfmight 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 athttp://www.boost.org/LICENSE_1_0.txt)