havoqgt::mpi Namespace Reference

Namespaces
	detail

Classes
class	bfs_priority_queue
class	bfs_queue
class	bfs_visitor
class	delegate_partitioned_graph
class	dest_pair_partitioner
class	edge_source_partitioner
class	edge_target_partitioner
class	el_partitioned_t
class	get_local_id
class	get_owner_id
class	high_edge_partitioner
class	local_dest_id
class	local_source_id
class	LogStep
class	mailbox_routed
class	mpi_communicator
class	oned_blocked_partitioned_t
struct	OverflowSendInfo
class	owner_dest_id
class	owner_sort
class	owner_source_id
class	pr_queue
class	pr_visitor
class	source_partitioner
class	sssp_queue
class	sssp_visitor
class	termination_detection
class	triangle_count_visitor
class	triangle_priority_queue
class	visitor_queue

Typedefs
typedef struct havoqgt::mpi::OverflowSendInfo	OverflowSendInfo

Functions
template<typename TGraph , typename LevelData , typename ParentData >
void	breadth_first_search (TGraph *g, LevelData &level_data, ParentData &parent_data, typename TGraph::vertex_locator s)
template<typename EdgeType >
void	gen_preferential_attachment_edge_list (std::vector< EdgeType > &local_edges, uint64_t in_base_seed, uint64_t in_node_scale, uint64_t in_edge_scale, double in_beta, double in_prob_rewire, MPI_Comm in_comm)
template<typename SegmentManager >
bool	operator== (const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &x, const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &y)
template<typename SegmentManager >
bool	operator!= (const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &x, const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &y)
template<typename SegmentManager >
bool	operator== (const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &x, const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &y)
template<typename SegmentManager >
bool	operator!= (const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &x, const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &y)
MPI_Datatype	mpi_typeof (char)
MPI_Datatype	mpi_typeof (signed short)
MPI_Datatype	mpi_typeof (unsigned char)
MPI_Datatype	mpi_typeof (unsigned long long)
MPI_Datatype	mpi_typeof (signed long long)
MPI_Datatype	mpi_typeof (double)
MPI_Datatype	mpi_typeof (long double)
MPI_Datatype	mpi_typeof (std::pair< int, int >)
MPI_Datatype	mpi_typeof (std::pair< float, int >)
MPI_Datatype	mpi_typeof (std::pair< double, int >)
MPI_Datatype	mpi_typeof (std::pair< long double, int >)
MPI_Datatype	mpi_typeof (std::pair< short, int >)
template<typename T >
MPI_Op	mpi_typeof (std::greater< T >)
template<typename T >
MPI_Op	mpi_typeof (std::less< T >)
template<typename T >
MPI_Op	mpi_typeof (std::plus< T >)
template<typename T >
MPI_Op	mpi_typeof (std::multiplies< T >)
template<typename T >
MPI_Op	mpi_typeof (std::logical_and< T >)
template<typename T >
MPI_Op	mpi_typeof (std::logical_or< T >)
void	mpi_yield_barrier (MPI_Comm mpi_comm)
template<typename T , typename Op >
T	mpi_all_reduce (T in_d, Op in_op, MPI_Comm mpi_comm)
template<typename Vec , typename Op >
void	mpi_all_reduce_inplace (Vec &vec, Op in_op, MPI_Comm mpi_comm)
template<typename T , typename Op >
void	mpi_all_reduce (std::vector< T > &in_vec, std::vector< T > &out_vec, Op in_op, MPI_Comm mpi_comm)
template<typename T >
void	mpi_all_to_all (std::vector< T > &in_vec, std::vector< int > &in_sendcnts, std::vector< T > &out_vec, std::vector< int > &out_recvcnts, MPI_Comm mpi_comm)
template<typename T , typename Partitioner >
void	mpi_all_to_all (std::vector< T > &inout_vec, std::vector< T > &temp_vec, Partitioner &owner, MPI_Comm mpi_comm)
template<typename T , typename Partitioner >
void	mpi_all_to_all_better (std::vector< T > &in_vec, std::vector< T > &out_vec, Partitioner &owner, MPI_Comm mpi_comm)
template<typename T >
void	mpi_all_to_all_in_place (std::vector< T > &in_out_vec, size_t count, MPI_Comm mpi_comm)
template<typename T >
void	mpi_all_gather (T _t, std::vector< T > &out_p_vec, MPI_Comm mpi_comm)
	TODO: Add tests. More...
template<typename T >
void	mpi_all_gather (std::vector< T > &in_send, std::vector< T > &out_recv_gather, MPI_Comm mpi_comm)
	TODO: Add tests, especially with non mpi types, POD. More...
template<typename T >
void	mpi_all_to_all (std::vector< std::vector< T > > &in_p_vec, std::vector< std::vector< T > > &out_p_vec, MPI_Comm mpi_comm)
template<typename T >
void	mpi_bcast (T &data, int root, MPI_Comm comm)
std::ostream &	cout_rank0 ()
std::ostream &	cout_rank0_barrier ()
int	mpi_comm_rank ()
int	mpi_comm_size ()
template<typename TGraph , typename PRData >
void	page_rank (TGraph &g, PRData &pr_data)
template<typename TGraph , typename PathData , typename EdgeWeight >
void	single_source_shortest_path (TGraph &g, PathData &path_data, EdgeWeight &edge_data, typename TGraph::vertex_locator s)
template<typename TGraph >
uint64_t	triangle_count (TGraph &g, typename TGraph::vertex_locator s)
template<typename Container >
void	free_edge_container (Container &edges)
	Frees the container of edges. More...
template<>
void	free_edge_container< std::vector< std::pair< uint64_t, uint64_t > > > (std::vector< std::pair< uint64_t, uint64_t > > &edges)

Typedef Documentation

typedef struct havoqgt::mpi::OverflowSendInfo havoqgt::mpi::OverflowSendInfo

This class is used to determine where to send a high edge. If the edge's destination is owned by another node, then the edge is sent to that node. Otherwise, it is sent to a node based on the transfer_info.

Transfer_info is a map of delgate ids (not vertex ids) to a dequeue. i.e. delgate_id = m_map_delegate_locator(vertex_id) Each dequeue contains one or more OverflowSendInfo object which contains to_send_id, to_send_count, temp_to_send_count. which determines who will recieve the extra edges.

Function Documentation

template<typename TGraph , typename LevelData , typename ParentData >

void havoqgt::mpi::breadth_first_search	(	TGraph *	g,
		LevelData &	level_data,
		ParentData &	parent_data,
		typename TGraph::vertex_locator	s
	)

Definition at line 251 of file breadth_first_search.hpp.

                                                           {

  typedef  bfs_visitor<TGraph, LevelData, ParentData>    visitor_type;
  visitor_type::set_level_data(&level_data);
  visitor_type::set_parent_data(&parent_data);
  typedef visitor_queue< visitor_type, bfs_priority_queue, TGraph >    visitor_queue_type;

  visitor_queue_type vq(g);
  vq.init_visitor_traversal(s);
}

Here is the caller graph for this function:

std::ostream& havoqgt::mpi::cout_rank0 ( )

inline

Definition at line 565 of file mpi.hpp.

                                {
  int mpi_rank(0);
  CHK_MPI( MPI_Comm_rank( MPI_COMM_WORLD, &mpi_rank) );

  if(mpi_rank == 0) {
    return std::cout;
  }
  return havoqgt::detail::get_null_ostream();
}

Here is the call graph for this function:

std::ostream& havoqgt::mpi::cout_rank0_barrier ( )

inline

Definition at line 575 of file mpi.hpp.

                                        {
  CHK_MPI( MPI_Barrier( MPI_COMM_WORLD ));
  int mpi_rank(0);
  CHK_MPI( MPI_Comm_rank( MPI_COMM_WORLD, &mpi_rank) );

  if(mpi_rank == 0) {
    return std::cout;
  }
  return havoqgt::detail::get_null_ostream();
}

Here is the call graph for this function:

template<typename Container >

void havoqgt::mpi::free_edge_container

(

Container &

edges

)

Frees the container of edges.

Definition at line 60 of file utilities.hpp.

{};

template<>

void havoqgt::mpi::free_edge_container< std::vector< std::pair< uint64_t, uint64_t > > >

(

std::vector< std::pair< uint64_t, uint64_t > > &

edges

)

Definition at line 63 of file utilities.hpp.

                                                                                                                  {
  std::vector< std::pair<uint64_t, uint64_t> >empty(0);
  edges.swap(empty);
};

template<typename EdgeType >

void havoqgt::mpi::gen_preferential_attachment_edge_list	(	std::vector< EdgeType > &	local_edges,
		uint64_t	in_base_seed,
		uint64_t	in_node_scale,
		uint64_t	in_edge_scale,
		double	in_beta,
		double	in_prob_rewire,
		MPI_Comm	in_comm
	)

Definition at line 65 of file gen_preferential_attachment_edge_list.hpp.

{
  namespace ad = havoqgt::detail;
  int mpi_rank, mpi_size;
  CHK_MPI( MPI_Comm_rank(in_comm, &mpi_rank) );
  CHK_MPI( MPI_Comm_size(in_comm, &mpi_size) );

  //
  // Calc global number of nodes and edges
  uint64_t global_num_nodes = uint64_t(1) << in_node_scale;
  uint64_t global_num_edges = uint64_t(1) << in_edge_scale;
  uint64_t k = global_num_edges / global_num_nodes;
  uint64_t edges_per_rank = global_num_edges / mpi_size;

  ad::preferential_attachment_helper<uint64_t> pa(k, global_num_edges, in_beta,
                                             in_base_seed*mpi_rank + mpi_rank);

  //
  // Generate inital pa edges.  Includes unresolved links
  double init_time_start = MPI_Wtime();
  local_edges.resize(edges_per_rank);
  for(uint64_t i=0; i<edges_per_rank; ++i) {
    uint64_t edge_index = uint64_t(mpi_rank) + i*uint64_t(mpi_size);
    local_edges[i] = pa.gen_edge(edge_index);
  }
  double init_time_end = MPI_Wtime();
  if(mpi_rank == 0) {
    std::cout << "Initial rng for edges took " << init_time_end - init_time_start
              << " seconds. " << std::endl;
  }

  //
  // We loop until all edges are resolved
  uint64_t iteration_count(1), count_missing(0), count_total_mising(0);
  do {
    //
    // Count number still missing
    for(uint64_t i=0; i<edges_per_rank; ++i) {
      if(pa.is_pointer(local_edges[i].second)) {
        ++count_total_mising;
      }
    }

    count_missing = 0;
    double time_start = MPI_Wtime();
    //
    // Generate vectors to exchange
    std::vector<std::vector<uint64_t> > tmp_send_to_rank(mpi_size);
    std::vector<std::vector<uint64_t> > tmp_mark_send_to_rank(mpi_size);
    uint64_t count_to_send(0);
    for(uint64_t i=0; i<local_edges.size(); ++i) {
      if(pa.is_pointer(local_edges[i].second)) {
        int owner = pa.value_of_pointer(local_edges[i].second) % mpi_size;
        tmp_mark_send_to_rank[owner].push_back(i);
        tmp_send_to_rank[owner].push_back(pa.value_of_pointer(local_edges[i].second));
        ++count_to_send;
      }
    }
    //
    // Combine send/recv vectors
    std::vector<uint64_t> to_send(count_to_send); to_send.reserve(1);
    std::vector<uint64_t> mark_to_send(count_to_send);
    std::vector<int>      sendcnts(mpi_size,0); sendcnts.reserve(1);
    to_send.clear(); mark_to_send.clear();
    for(int i = 0; i < mpi_size; ++i) {
      for(size_t j = 0; j < tmp_send_to_rank[i].size(); ++j) {
        to_send.push_back(tmp_send_to_rank[i][j]);
        mark_to_send.push_back(tmp_mark_send_to_rank[i][j]);
      }
      sendcnts[i] = tmp_send_to_rank[i].size();
    }
    //
    // Release memory from temp vectors
    {
      std::vector<std::vector<uint64_t> > empty;
      tmp_send_to_rank.swap(empty);
    }
    {
      std::vector<std::vector<uint64_t> > empty;
      tmp_mark_send_to_rank.swap(empty);
    }
    //
    // Exchange vectors
    std::vector<uint64_t> to_recv; // not sized
    std::vector<int>      recvcnts; // not sized
    havoqgt::mpi::mpi_all_to_all(to_send, sendcnts, to_recv, recvcnts, MPI_COMM_WORLD);
    //
    // Look up pointers, pointer jump!
    for(size_t i=0; i<to_recv.size(); ++i) {
      uint64_t local_index = to_recv[i]/mpi_size;
      to_recv[i] = local_edges[local_index].second;
    }
    //
    // Return exchange vectors
    havoqgt::mpi::mpi_all_to_all(to_recv, recvcnts, to_send, sendcnts, MPI_COMM_WORLD);
    //
    // Return new pointers to marked location
    for(size_t i=0; i<to_send.size(); ++i) {
        local_edges[ mark_to_send[i] ].second = to_send[i];;
    }
    //
    // Count number still missing
    for(uint64_t i=0; i<edges_per_rank; ++i) {
      if(pa.is_pointer(local_edges[i].second)) {
        ++count_missing;
      }
    }
    count_missing = havoqgt::mpi::mpi_all_reduce(count_missing, std::plus<uint64_t>(), MPI_COMM_WORLD);

    //
    // Iteration ouput
    double time_end = MPI_Wtime();
    if(mpi_rank == 0) {
      std::cout << "Iteration " << iteration_count << " took "
                << time_end - time_start << " seconds.   "
                << count_missing << " still missing. " << std::endl;
    }
    ++iteration_count;
  } while(count_missing > 0);
  //
  // Output total nuumber of global exchanges
  count_total_mising = havoqgt::mpi::mpi_all_reduce(count_total_mising, std::plus<uint64_t>(), MPI_COMM_WORLD);
  if(mpi_rank == 0) {
    std::cout << "Total missing (how much data globally exchanged) = " << count_total_mising << std::endl;
  }


  //
  // Randomly rewire
  if(in_prob_rewire > double(0)) {
    boost::mt19937 rng(in_base_seed + uint64_t(mpi_rank) * 3ULL);
    boost::random::uniform_int_distribution<> rand_node(0,global_num_nodes-1);
    boost::random::uniform_01<> rand_real;
    for(size_t i=0; i<local_edges.size(); ++i) {
      if(rand_real(rng) < in_prob_rewire) {
        EdgeType rand_edge(rand_node(rng), rand_node(rng));
        local_edges[i] = rand_edge;
      }
    }
  }

  //
  // Scramble edges
  for(size_t i=0; i<local_edges.size(); ++i) {
    //TODO:  This needs a mod because we never exactly make the correct
    //number of vertices.   We need a better solution!
    local_edges[i].first  %= global_num_nodes;
    local_edges[i].second %= global_num_nodes;
    local_edges[i].first  = ad::hash_nbits(local_edges[i].first,  in_node_scale);
    local_edges[i].second = ad::hash_nbits(local_edges[i].second, in_node_scale);
  }

  // //
  // // Symmetrizing b/c PA is always undirected.
  // uint64_t old_size = local_edges.size();
  // local_edges.reserve(old_size * 2);
  // for(uint64_t i=0; i<old_size; ++i) {
  //   EdgeType edge;
  //   edge.first = local_edges[i].second;
  //   edge.second = local_edges[i].first;
  //   local_edges.push_back( edge );
  // }

  // //
  // // Shuffle edges because we need to mix the hubs in for future partitioning
  // std::random_shuffle(local_edges.begin(), local_edges.end());
}

Here is the call graph for this function:

template<typename T >

void havoqgt::mpi::mpi_all_gather	(	T	_t,
		std::vector< T > &	out_p_vec,
		MPI_Comm	mpi_comm
	)

TODO: Add tests.

Definition at line 432 of file mpi.hpp.

                                                                      {
  int mpi_size(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );

  out_p_vec.resize(mpi_size);
  CHK_MPI( MPI_Allgather(&_t, sizeof(_t), MPI_BYTE,
                         &(out_p_vec[0]),  sizeof(_t), MPI_BYTE, mpi_comm) );
}

Here is the caller graph for this function:

template<typename T >

void havoqgt::mpi::mpi_all_gather	(	std::vector< T > &	in_send,
		std::vector< T > &	out_recv_gather,
		MPI_Comm	mpi_comm
	)

TODO: Add tests, especially with non mpi types, POD.

Definition at line 443 of file mpi.hpp.

                                                                      {

  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );

  int my_size = in_send.size();
  std::vector<int> recv_counts(mpi_size,0);
  std::vector<int> recv_disps(mpi_size,0);

  //Gather recv counts for all ranks
  mpi_all_gather(my_size, recv_counts, mpi_comm);

  //Allocate recv vector
  int total_recv = std::accumulate(recv_counts.begin(), recv_counts.end(), 0);
  if(total_recv > 0) {
    out_recv_gather.resize(total_recv);

    //cacl recv disps
    std::partial_sum(recv_counts.begin(), recv_counts.end(), recv_disps.begin());
    for(size_t i=0; i<recv_disps.size(); ++i) {
      recv_disps[i] -= recv_counts[i]; //set to 0 offset
    }

    void* send_buff = in_send.size() == 0 ? NULL : &(in_send[0]);
    CHK_MPI( MPI_Allgatherv( send_buff, my_size, mpi_typeof(T()),
                             &(out_recv_gather[0]), &(recv_counts[0]), &(recv_disps[0]),
                             mpi_typeof(T()), mpi_comm));
  }
}

Here is the call graph for this function:

template<typename T , typename Op >

T havoqgt::mpi::mpi_all_reduce	(	T	in_d,
		Op	in_op,
		MPI_Comm	mpi_comm
	)

Definition at line 176 of file mpi.hpp.

                                                      {
  T to_return;
  CHK_MPI(
    MPI_Allreduce( &in_d, &to_return, 1, mpi_typeof(T()), mpi_typeof(in_op),
      mpi_comm)
  );
  return to_return;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T , typename Op >

void havoqgt::mpi::mpi_all_reduce	(	std::vector< T > &	in_vec,
		std::vector< T > &	out_vec,
		Op	in_op,
		MPI_Comm	mpi_comm
	)

Definition at line 194 of file mpi.hpp.

                       {
  out_vec.resize(in_vec.size());
  CHK_MPI(
    MPI_Allreduce( &(in_vec[0]), &(out_vec[0]), in_vec.size(),
      mpi_typeof(in_vec[0]), mpi_typeof(in_op), mpi_comm)
  );
}

Here is the call graph for this function:

template<typename Vec , typename Op >

void havoqgt::mpi::mpi_all_reduce_inplace	(	Vec &	vec,
		Op	in_op,
		MPI_Comm	mpi_comm
	)

Definition at line 186 of file mpi.hpp.

                                                                   {
  CHK_MPI(
    MPI_Allreduce(MPI_IN_PLACE, &(vec[0]), vec.size(),
      mpi_typeof(typename Vec::value_type()), mpi_typeof(in_op), mpi_comm)
  );
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

void havoqgt::mpi::mpi_all_to_all	(	std::vector< T > &	in_vec,
		std::vector< int > &	in_sendcnts,
		std::vector< T > &	out_vec,
		std::vector< int > &	out_recvcnts,
		MPI_Comm	mpi_comm
	)

Definition at line 218 of file mpi.hpp.

                                       {
  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );

  void* send_vec  =  in_vec.size() > 0 ? (void*) &in_vec[0] : NULL;
  int* send_cnts =  in_sendcnts.size() > 0 ? &in_sendcnts[0] : NULL;

  //
  // Exchange send counts
  out_recvcnts.resize(mpi_size);
  CHK_MPI( MPI_Alltoall( (void*) send_cnts, sizeof(int), MPI_BYTE,
                         (void*) &(out_recvcnts[0]), sizeof(int), MPI_BYTE,
                         mpi_comm ) );

  //
  // Calc send & recv disps
  std::vector<int> sdispls(mpi_size,0), rdispls(mpi_size,0);
  std::partial_sum(in_sendcnts.begin(), in_sendcnts.end(), sdispls.begin());
  for(size_t i=0; i<sdispls.size(); ++i) {
    sdispls[i] -= in_sendcnts[i]; //set to 0 offset
  }
  std::partial_sum(out_recvcnts.begin(), out_recvcnts.end(), rdispls.begin());
  for(size_t i=0; i<rdispls.size(); ++i) {
    rdispls[i] -= out_recvcnts[i]; //set to 0 offset
  }

  out_vec.resize(std::accumulate(out_recvcnts.begin(), out_recvcnts.end(), 0));

  int* send_displs =  sdispls.size() > 0 ? &sdispls[0] : NULL;
  CHK_MPI( MPI_Alltoallv(send_vec, send_cnts, send_displs,
                  mpi_typeof(T()), &(out_vec[0]), &(out_recvcnts[0]),
                  &(rdispls[0]), mpi_typeof(T()), mpi_comm) );

}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T , typename Partitioner >

void havoqgt::mpi::mpi_all_to_all	(	std::vector< T > &	inout_vec,
		std::vector< T > &	temp_vec,
		Partitioner &	owner,
		MPI_Comm	mpi_comm
	)

Definition at line 258 of file mpi.hpp.

                                             {
  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );

  std::vector<int> send_counts(mpi_size,0);
  std::vector<int> send_disps(mpi_size,0);

  std::vector<int> recv_counts(mpi_size,0);
  std::vector<int> recv_disps(mpi_size,0);

  //sort send vector by owner
  //std::sort(inout_vec.begin(), inout_vec.end(), owner_sort<T,Partitioner>(owner));

  //calc send counts
  for(size_t i=0; i<inout_vec.size(); ++i) {
    send_counts[owner(inout_vec[i])] += sizeof(T); //sizeof(t) lets us use PODS
    //if(i>0) {
    //  assert(owner(inout_vec[i-1]) <= owner(inout_vec[i]));
    //}
  }

  //cacl send disps
  std::partial_sum(send_counts.begin(), send_counts.end(), send_disps.begin());
  for(size_t i=0; i<send_disps.size(); ++i) {
    send_disps[i] -= send_counts[i]; //set to 0 offset
  }

  temp_vec.resize(inout_vec.size());
  for(size_t i=0; i<inout_vec.size(); ++i) {
    std::vector<int> temp_arrange(mpi_size,0);
    int dest_rank = owner(inout_vec[i]);
    size_t dest_offset = send_disps[dest_rank] + temp_arrange[dest_rank];
    temp_arrange[dest_rank] += sizeof(T);
    dest_offset /= sizeof(T);
    temp_vec[dest_offset] = inout_vec[i];
  }


  //exchange send counts
  CHK_MPI( MPI_Alltoall( (void*) &(send_counts[0]), sizeof(int), MPI_BYTE,
                         (void*) &(recv_counts[0]), sizeof(int), MPI_BYTE,
                         mpi_comm ) );

  //Allocate recv vector
  int total_recv = std::accumulate(recv_counts.begin(), recv_counts.end(), 0);
  inout_vec.resize(total_recv/sizeof(T));

  //cacl recv disps
  std::partial_sum(recv_counts.begin(), recv_counts.end(), recv_disps.begin());
  for(size_t i=0; i<recv_disps.size(); ++i) {
    recv_disps[i] -= recv_counts[i]; //set to 0 offset
  }

  //perform actual a3lloallv
  CHK_MPI( MPI_Alltoallv( (void*) &(temp_vec[0]), &(send_counts[0]), &(send_disps[0]), MPI_BYTE,
                          (void*) &(inout_vec[0]),&(recv_counts[0]), &(recv_disps[0]), MPI_BYTE,
                          mpi_comm) );
}

template<typename T >

void havoqgt::mpi::mpi_all_to_all	(	std::vector< std::vector< T > > &	in_p_vec,
		std::vector< std::vector< T > > &	out_p_vec,
		MPI_Comm	mpi_comm
	)

All to All exchange of std::vector<T>

Parameters

[in]	in_p_vec	input vector
[out]	out_p_vec	output vector
[in]	mpi_comm	MPI communicator

Todo:

Add ability to optimize for sparse sends. Put MPI_Request objects into a resizing vecor to be skipped for 0 byte send/recvs

Definition at line 487 of file mpi.hpp.

                                       {
  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );
  assert( mpi_size == (int) in_p_vec.size() );

  std::vector<size_t> per_rank_send_counts(mpi_size);
  std::vector<size_t> per_rank_recv_counts(mpi_size);

  for(int i=0; i<mpi_size; ++i) {
    per_rank_send_counts[i] = in_p_vec[i].size();
  }

  CHK_MPI( MPI_Alltoall( &(per_rank_send_counts[0]), 1, mpi_typeof(size_t()),
                         &(per_rank_recv_counts[0]), 1, mpi_typeof(size_t()),
                         mpi_comm ) );
  //Allocate recv memory
  out_p_vec.resize(mpi_size);
  for(int i=0; i<mpi_size; ++i) {
    out_p_vec[i].resize(per_rank_recv_counts[i]);
  }

/*
 *  //Aggregisive method, good for small-med p?
 *  std::vector<MPI_Request> vec_req;
 *  for(int i=0; i<mpi_size; ++i) {
 *    int send_to_rank   = (mpi_rank + i) % mpi_size;
 *    int recv_from_rank = (mpi_rank - i + mpi_size) % mpi_size;
 *    //Post Irecvs
 *    if(out_p_vec[recv_from_rank].size() > 0) {
 *      MPI_Request req;
 *      CHK_MPI( MPI_Irecv( &(out_p_vec[recv_from_rank][0]),
 *                          (out_p_vec[recv_from_rank].size() * sizeof(T)),
 *                          MPI_BYTE,
 *                          recv_from_rank, 0, mpi_comm, &req ) );
 *      vec_req.push_back(req);
 *    }
 *
 *    //Post Isends
 *    if(in_p_vec[send_to_rank].size() > 0) {
 *      MPI_Request req;
 *      CHK_MPI( MPI_Isend( &(in_p_vec[send_to_rank][0]),
 *                          (in_p_vec[send_to_rank].size() * sizeof(T)),
 *                          MPI_BYTE,
 *                          send_to_rank, 0, mpi_comm, &req) );
 *      vec_req.push_back(req);
 *    }
 *  }
 *  CHK_MPI( MPI_Waitall(vec_req.size(), &(vec_req[0]), MPI_STATUSES_IGNORE) );
 */

  //Basic method -- good for large p?
  //For each rank, in parallel do:
  for(int i=0; i<mpi_size; ++i) {
    MPI_Request request[2];
    int send_to_rank   = (mpi_rank + i) % mpi_size;
    int recv_from_rank = (mpi_rank - i + mpi_size) % mpi_size;
    CHK_MPI( MPI_Isend( &(in_p_vec[send_to_rank][0]),
                        (in_p_vec[send_to_rank].size() * sizeof(T)),
                        MPI_BYTE,
                        send_to_rank, 0, mpi_comm, &(request[0]) ) );
    CHK_MPI( MPI_Irecv( &(out_p_vec[recv_from_rank][0]),
                        (out_p_vec[recv_from_rank].size() * sizeof(T)),
                        MPI_BYTE,
                        recv_from_rank, 0, mpi_comm, &(request[1]) ) );
    CHK_MPI( MPI_Waitall(2, request, MPI_STATUSES_IGNORE) );
  }
}

Here is the call graph for this function:

template<typename T , typename Partitioner >

void havoqgt::mpi::mpi_all_to_all_better	(	std::vector< T > &	in_vec,
		std::vector< T > &	out_vec,
		Partitioner &	owner,
		MPI_Comm	mpi_comm
	)

Definition at line 320 of file mpi.hpp.

                                             {
  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );

  std::vector<int> send_counts(mpi_size,0);
  std::vector<int> send_disps(mpi_size,0);
  std::vector<int> recv_counts(mpi_size,0);
  std::vector<int> recv_disps(mpi_size,0);

  //sort send vector by owner
  //std::sort(in_vec.begin(), in_vec.end(), owner_sort<T,Partitioner>(owner));

  //calc send counts
  for(size_t i=0; i<in_vec.size(); ++i) {
    send_counts[owner(in_vec[i], true)] += sizeof(T); //sizeof(t) lets us use PODS
    //if(i>0) {
    //  assert(owner(inout_vec[i-1]) <= owner(inout_vec[i]));
    //
  }


  //cacl send disps
  std::partial_sum(send_counts.begin(), send_counts.end(), send_disps.begin());
  for(size_t i=0; i<send_disps.size(); ++i) {
    send_disps[i] -= send_counts[i]; //set to 0 offset
  }


  { //rearrange instead of sorting
    std::vector<T> order_vec(in_vec.size());
    std::vector<int> temp_arrange(mpi_size,0);
    for(size_t i=0; i<in_vec.size(); ++i) {
      int dest_rank = owner(in_vec[i], false);
      assert (dest_rank >=0 && dest_rank < mpi_size);

      size_t dest_offset = send_disps[dest_rank] + temp_arrange[dest_rank];
      temp_arrange[dest_rank] += sizeof(T);
      dest_offset /= sizeof(T);
      order_vec[dest_offset] = in_vec[i];
    }
    in_vec.swap(order_vec);
  }


  //exchange send counts
  CHK_MPI( MPI_Alltoall( (void*) &(send_counts[0]), sizeof(int), MPI_BYTE,
                         (void*) &(recv_counts[0]), sizeof(int), MPI_BYTE,
                         mpi_comm ) );


  //Allocate recv vector
  int total_recv = std::accumulate(recv_counts.begin(), recv_counts.end(), 0);
  out_vec.resize(total_recv/sizeof(T));

  //cacl recv disps
  std::partial_sum(recv_counts.begin(), recv_counts.end(), recv_disps.begin());
  for(size_t i=0; i<recv_disps.size(); ++i) {
    recv_disps[i] -= recv_counts[i]; //set to 0 offset
  }

  //perform actual alltoallv
  void* send_ptr = in_vec.empty()  ? NULL :(void*) &(in_vec[0]);
  void* recv_ptr = out_vec.empty() ? NULL :(void*) &(out_vec[0]);
  CHK_MPI( MPI_Alltoallv( send_ptr, &(send_counts[0]), &(send_disps[0]), MPI_BYTE,
                          recv_ptr, &(recv_counts[0]), &(recv_disps[0]), MPI_BYTE,
                          mpi_comm) );
}

Here is the caller graph for this function:

template<typename T >

void havoqgt::mpi::mpi_all_to_all_in_place	(	std::vector< T > &	in_out_vec,
		size_t	count,
		MPI_Comm	mpi_comm
	)

Definition at line 397 of file mpi.hpp.

                                                {
  const int HAVOQGT_TAG=42;
  int mpi_size(0), mpi_rank(0);
  CHK_MPI( MPI_Comm_size( mpi_comm, &mpi_size) );
  CHK_MPI( MPI_Comm_rank( mpi_comm, &mpi_rank) );
  assert( in_out_vec.size() == count * mpi_size );

  for(int i=0; i<mpi_size; ++i) {
    //start inner loop at i to avoid re-exchanging data
    for(int j=i; j<mpi_size; ++j) {
      if( mpi_rank == i) {
        MPI_Status status;
        CHK_MPI( MPI_Sendrecv_replace(&(in_out_vec[j*count]), count,
                                      mpi_typeof(T()),
                                      j, HAVOQGT_TAG,
                                      j, HAVOQGT_TAG,
                                      mpi_comm, &status) );

      } else if(mpi_rank == j) {
        MPI_Status status;
        CHK_MPI( MPI_Sendrecv_replace(&(in_out_vec[i*count]), count,
                                      mpi_typeof(T()),
                                      i, HAVOQGT_TAG,
                                      i, HAVOQGT_TAG,
                                      mpi_comm, &status) );


      }
    }
  }
}

Here is the call graph for this function:

template<typename T >

void havoqgt::mpi::mpi_bcast	(	T &	data,
		int	root,
		MPI_Comm	comm
	)

Definition at line 559 of file mpi.hpp.

{
  CHK_MPI( MPI_Bcast(&data, sizeof(data), MPI_BYTE, root, comm));
}

Here is the caller graph for this function:

int havoqgt::mpi::mpi_comm_rank ( )

inline

Definition at line 587 of file mpi.hpp.

                           {
  int rank;
  CHK_MPI( MPI_Comm_rank(MPI_COMM_WORLD, &rank) );
  return rank;
}

int havoqgt::mpi::mpi_comm_size ( )

inline

Definition at line 593 of file mpi.hpp.

                           {
  int size;
  CHK_MPI( MPI_Comm_size(MPI_COMM_WORLD, &size) );
  return size;
}

MPI_Datatype havoqgt::mpi::mpi_typeof ( char  )

inline

Definition at line 80 of file mpi.hpp.

{return MPI_CHAR;}

Here is the caller graph for this function:

MPI_Datatype havoqgt::mpi::mpi_typeof ( signed  short )

inline

Definition at line 81 of file mpi.hpp.

{return MPI_SHORT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( unsigned  char )

inline

Definition at line 84 of file mpi.hpp.

{return MPI_UNSIGNED_CHAR;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( unsigned long long  )

inline

Definition at line 88 of file mpi.hpp.

{return MPI_UNSIGNED_LONG_LONG; }

MPI_Datatype havoqgt::mpi::mpi_typeof ( signed long  long )

inline

Definition at line 89 of file mpi.hpp.

{return MPI_LONG_LONG_INT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( double  )

inline

Definition at line 90 of file mpi.hpp.

{return MPI_DOUBLE;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( long  double )

inline

Definition at line 91 of file mpi.hpp.

{return MPI_LONG_DOUBLE;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( std::pair< int, int >  )

inline

Definition at line 92 of file mpi.hpp.

{return MPI_2INT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( std::pair< float, int >  )

inline

Definition at line 93 of file mpi.hpp.

{return MPI_FLOAT_INT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( std::pair< double, int >  )

inline

Definition at line 94 of file mpi.hpp.

{return MPI_DOUBLE_INT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( std::pair< long double, int >  )

inline

Definition at line 95 of file mpi.hpp.

{return MPI_LONG_DOUBLE_INT;}

MPI_Datatype havoqgt::mpi::mpi_typeof ( std::pair< short, int >  )

inline

Definition at line 96 of file mpi.hpp.

{return MPI_SHORT_INT;}

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::greater< T >

)

Definition at line 99 of file mpi.hpp.

{ return MPI_MAX; }

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::less< T >

)

Definition at line 102 of file mpi.hpp.

{ return MPI_MIN; }

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::plus< T >

)

Definition at line 105 of file mpi.hpp.

{ return MPI_SUM; }

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::multiplies< T >

)

Definition at line 108 of file mpi.hpp.

{ return MPI_PROD; }

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::logical_and< T >

)

Definition at line 111 of file mpi.hpp.

{ return MPI_LAND; }

template<typename T >

MPI_Op havoqgt::mpi::mpi_typeof

(

std::logical_or< T >

)

Definition at line 114 of file mpi.hpp.

{ return MPI_LOR; }

void havoqgt::mpi::mpi_yield_barrier

(

MPI_Comm

mpi_comm

)

Definition at line 156 of file mpi.hpp.

                                          {
  MPI_Request request;
  CHK_MPI(MPI_Ibarrier(mpi_comm, &request));

  for(; ;) {
    MPI_Status status;
    int is_done = false;
    MPI_Test(&request, &is_done, &status);
    if (is_done) {
      return;
    } else {
      sched_yield();
    }
  }
}

Here is the caller graph for this function:

template<typename SegmentManager >

bool havoqgt::mpi::operator!= ( const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &  x, const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &  y  )

inline

Definition at line 146 of file vertex_iterator.hpp.

                                                                                        {
  return !(x.is_equal(y));
}

Here is the call graph for this function:

template<typename SegmentManager >

bool havoqgt::mpi::operator!= ( const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &  x, const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &  y  )

inline

Definition at line 149 of file edge_iterator.hpp.

                                                                                      {
  return !(x.is_equal(y));
}

Here is the call graph for this function:

template<typename SegmentManager >

bool havoqgt::mpi::operator== ( const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &  x, const typename delegate_partitioned_graph< SegmentManager >::vertex_iterator &  y  )

inline

Definition at line 138 of file vertex_iterator.hpp.

                                                                                        {
  return x.is_equal(y);

}

Here is the call graph for this function:

template<typename SegmentManager >

bool havoqgt::mpi::operator== ( const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &  x, const typename delegate_partitioned_graph< SegmentManager >::edge_iterator &  y  )

inline

Definition at line 141 of file edge_iterator.hpp.

                                                                                      {
  return x.is_equal(y);

}

Here is the call graph for this function:

template<typename TGraph , typename PRData >

void havoqgt::mpi::page_rank	(	TGraph &	g,
		PRData &	pr_data
	)

Definition at line 166 of file page_rank.hpp.

                                           {
  typedef  pr_visitor<TGraph, PRData>    visitor_type;
  visitor_type::rank_data(&pr_data);
  typedef visitor_queue< visitor_type, pr_queue, TGraph >    visitor_queue_type;
   
  visitor_queue_type vq(&g);
  vq.init_visitor_traversal();
  pr_data.all_reduce();
}

template<typename TGraph , typename PathData , typename EdgeWeight >

void havoqgt::mpi::single_source_shortest_path	(	TGraph &	g,
		PathData &	path_data,
		EdgeWeight &	edge_data,
		typename TGraph::vertex_locator	s
	)

Definition at line 172 of file single_source_shortest_path.hpp.

                                                                  {
  
  typedef  sssp_visitor<TGraph, PathData, EdgeWeight>    visitor_type;
  visitor_type::set_path_data(&path_data);
  visitor_type::set_edge_weight(&edge_data);
  typedef visitor_queue< visitor_type, sssp_queue, TGraph >    visitor_queue_type;
   
  visitor_queue_type vq(&g);
  vq.init_visitor_traversal(s);
}

template<typename TGraph >

uint64_t havoqgt::mpi::triangle_count	(	TGraph &	g,
		typename TGraph::vertex_locator	s
	)

Definition at line 209 of file triangle_count.hpp.

                                                                    {
  typedef TGraph                                             graph_type;
  typedef typename mpi::triangle_count_visitor<TGraph>             visitor_type;
  visitor_type::m_ptr_graph = &g;
  typedef visitor_queue< visitor_type, triangle_priority_queue, graph_type >    visitor_queue_type;
  
  visitor_queue_type vq(&g);
  
  typename graph_type::template vertex_data<uint64_t, std::allocator<uint64_t> >   tc_data(g);
  visitor_type::set_tc_data(&tc_data);
  
  vq.init_visitor_traversal(s);

  return tc_data.global_accumulate();
}

Here is the caller graph for this function: