make_graph.c

/* 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)                                   */
/*                                                                         */
/*  Authors: Jeremiah Willcock                                             */
/*           Andrew Lumsdaine                                              */

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#ifdef __MTA__
#include <sys/mta_task.h>
#endif
#ifdef GRAPH_GENERATOR_MPI
#include <mpi.h>
#endif
#ifdef GRAPH_GENERATOR_OMP
#include <omp.h>
#endif
#ifdef GRAPH_GENERATOR_GRAPPA
#define _GRAPPA
#endif

/* Simplified interface to build graphs with scrambled vertices. */

#include "graph_generator.h"
#include "utils.h"

#ifdef GRAPH_GENERATOR_MPI
static void compute_edge_range(int rank, int size, int64_t M, int64_t* start_idx, int64_t* end_idx) {
	int64_t rankc = (int64_t)(rank);
	int64_t sizec = (int64_t)(size);
	*start_idx = rankc * (M / sizec) + (rankc < (M % sizec) ? rankc : (M % sizec));
	*end_idx = (rankc + 1) * (M / sizec) + (rankc + 1 < (M % sizec) ? rankc + 1 : (M % sizec));
}
#endif

#ifndef GRAPH_GENERATOR_MPI

#ifdef _GRAPPA
#include <gflags/gflags.h>
#include <GlobalAllocator.hpp> // Grappa::global_alloc
#include <iostream>
#include <string>
#include <boost/algorithm/string/predicate.hpp>
#include <FileIO.hpp>
#include <mpi.h>

DEFINE_string( path, "", "Path to input" );
DEFINE_string( format, "bintsv4", "Input format" );

void make_graph(int log_numverts, int64_t M, uint64_t userseed1, uint64_t userseed2, int64_t* nedges_ptr_in, GlobalAddress<packed_edge> * result_ptr_in) {
	/* Add restrict to input pointers. */
	int64_t* /*restrict*/ nedges_ptr = nedges_ptr_in;   // XXX: restrict keyword causing 'unexpected initilizer'
  /*no restrict support for GlobalAddress*/
	GlobalAddress<packed_edge> * /*restrict*/ result_ptr = result_ptr_in;
	
	/* Spread the two 64-bit numbers into five nonzero values in the correct
	 * range. */
	uint_fast32_t seed[5];
	make_mrg_seed(userseed1, userseed2, seed);
	
	*nedges_ptr = M;
  GlobalAddress<packed_edge> edges = Grappa::global_alloc<packed_edge>( M );
	*result_ptr = edges;
	
	generate_kronecker_range(seed, log_numverts, 0, M, edges);
}

DECLARE_string( path );
void load_tuplegraph_bintsv4( std::string path, int64_t* nedges_ptr_in, GlobalAddress<packed_edge> * result_ptr_in) {

  // make sure something is there
  CHECK( boost::filesystem::exists( path ) ) << "File not found. Multiple files are not supported for bintsv4 format.";
  CHECK( boost::filesystem::is_regular_file( path ) ) << "File is not a regular file. Multiple files are not supported for bintsv4 format.";

  // get file size
  auto file_size = boost::filesystem::file_size( path );
  auto edge_count = file_size / 8; // in bintsv4, edges are two 4-byte integers
  CHECK_EQ( edge_count * 8, file_size ) << "File appears to contain a partial edge";
  *nedges_ptr_in = edge_count;

  LOG(INFO) << "Loading " << edge_count << " edges from file " << path;

  // allocate array
  auto edges = Grappa::global_alloc<packed_edge>(edge_count);
  *result_ptr_in = edges;

  // load into array
   Grappa::on_all_cores( [edge_count, edges] {
                          int64_t each = edge_count / Grappa::cores();
                          int64_t offset = each * Grappa::mycore();
                          packed_edge * myedges = edges.localize();
                          
                          std::ifstream infile( FLAGS_path,
                                                std::ios_base::in | std::ios_base::binary );
                          infile.seekg(offset * 8);
                          
                          int32_t src, dst;
                          int64_t count = 0;
                          while( count < each && infile.good() ) {
                            infile.read(reinterpret_cast<char*>(&src), 4);
                            infile.read(reinterpret_cast<char*>(&dst), 4);
                            if( infile.fail() ) break;
                            write_edge( myedges, src, dst );
                            ++count;
                            ++myedges;
                          }
                          
                          // make sure all IO is done before continuing.
                          Grappa::barrier();
                          
                        });
}

void load_tuplegraph_tsv( std::string path, int64_t* nedges_ptr_in, GlobalAddress<packed_edge> * result_ptr_in) {
  LOG(ERROR) << "Not supported yet.";
  exit(2);
}

void load_tuple_graph( std::string path, std::string format, int64_t* nedges_ptr_in, GlobalAddress<packed_edge> * result_ptr_in) {
  if( format == "bintsv4" ) {
    load_tuplegraph_bintsv4( path, nedges_ptr_in, result_ptr_in );
  } else if( format == "tsv" ) {
    load_tuplegraph_tsv( path, nedges_ptr_in, result_ptr_in );
  } else {
    LOG(ERROR) << "Unknown file format " << format;
    exit(1);
  }
}

#else
void make_graph(int log_numverts, int64_t M, uint64_t userseed1, uint64_t userseed2, int64_t* nedges_ptr_in, packed_edge** result_ptr_in) {
	/* Add restrict to input pointers. */
	int64_t* restrict nedges_ptr = nedges_ptr_in;
	packed_edge* restrict* restrict result_ptr = result_ptr_in;
	
	/* Spread the two 64-bit numbers into five nonzero values in the correct
	 * range. */
	uint_fast32_t seed[5];
	make_mrg_seed(userseed1, userseed2, seed);
	
	*nedges_ptr = M;
	packed_edge* edges = (packed_edge*)xmalloc(M * sizeof(packed_edge));
	*result_ptr = edges;
	
	/* In OpenMP and XMT versions, the inner loop in generate_kronecker_range is
	 * parallel.  */
	generate_kronecker_range(seed, log_numverts, 0, M, edges);
}
#endif /* _GRAPPA */

#endif /* !GRAPH_GENERATOR_MPI */

#ifdef GRAPH_GENERATOR_MPI
void make_graph(int log_numverts, int64_t M, uint64_t userseed1, uint64_t userseed2, int64_t* nedges_ptr, packed_edge** result_ptr) {
	int rank, size;
	
	/* Spread the two 64-bit numbers into five nonzero values in the correct
	 * range. */
	uint_fast32_t seed[5];
	make_mrg_seed(userseed1, userseed2, seed);
	
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	
	int64_t start_idx, end_idx;
	compute_edge_range(rank, size, M, &start_idx, &end_idx);
	int64_t nedges = end_idx - start_idx;
	
	packed_edge* local_edges = (packed_edge*)xmalloc(nedges * sizeof(packed_edge));
	
	double start = MPI_Wtime();
	generate_kronecker_range(seed, log_numverts, start_idx, end_idx, local_edges);
	double gen_time = MPI_Wtime() - start;
	
	*result_ptr = local_edges;
	*nedges_ptr = nedges;
	
	if (rank == 0) {
		fprintf(stdout, "graph_generation:               %f s\n", gen_time);
	}
}
#endif

/* PRNG interface for implementations; takes seed in same format as given by
 * users, and creates a vector of doubles in a reproducible (and
 * random-access) way. */
void make_random_numbers(
						 /* in */ int64_t nvalues    /* Number of values to generate */,
						 /* in */ uint64_t userseed1 /* Arbitrary 64-bit seed value */,
						 /* in */ uint64_t userseed2 /* Arbitrary 64-bit seed value */,
						 /* in */ int64_t position   /* Start index in random number stream */,
						 /* out */ double* result    /* Returned array of values */
						 ) {
	int64_t i;
	uint_fast32_t seed[5];
	make_mrg_seed(userseed1, userseed2, seed);
	
	mrg_state st;
	mrg_seed(&st, seed);
	
	mrg_skip(&st, 2, 0, 2 * position); /* Each double takes two PRNG outputs */
	
	for (i = 0; i < nvalues; ++i) {
		result[i] = mrg_get_double_orig(&st);
	}
}