boost/mpi/graph_communicator.hpp
// Copyright (C) 2007 Trustees of Indiana University
// Authors: Douglas Gregor
// Andrew Lumsdaine
// 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)
/** @file graph_communicator.hpp
*
* This header defines facilities to support MPI communicators with
* graph topologies, using the graph interface defined by the Boost
* Graph Library. One can construct a communicator whose topology is
* described by any graph meeting the requirements of the Boost Graph
* Library's graph concepts. Likewise, any communicator that has a
* graph topology can be viewed as a graph by the Boost Graph
* Library, permitting one to use the BGL's graph algorithms on the
* process topology.
*/
#ifndef BOOST_MPI_GRAPH_COMMUNICATOR_HPP
#define BOOST_MPI_GRAPH_COMMUNICATOR_HPP
#include <boost/mpi/communicator.hpp>
#include <vector>
#include <utility>
// Headers required to implement graph topologies
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/shared_array.hpp>
#include <boost/assert.hpp>
namespace boost { namespace mpi {
/**
* @brief An MPI communicator with a graph topology.
*
* A @c graph_communicator is a communicator whose topology is
* expressed as a graph. Graph communicators have the same
* functionality as (intra)communicators, but also allow one to query
* the relationships among processes. Those relationships are
* expressed via a graph, using the interface defined by the Boost
* Graph Library. The @c graph_communicator class meets the
* requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
* Vertex List Graph, and Edge List Graph concepts.
*/
class BOOST_MPI_DECL graph_communicator : public communicator
{
friend class communicator;
/**
* INTERNAL ONLY
*
* Construct a graph communicator given a shared pointer to the
* underlying MPI_Comm. This operation is used for "casting" from a
* communicator to a graph communicator.
*/
explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
{
#ifndef BOOST_DISABLE_ASSERTS
int status;
BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
BOOST_ASSERT(status == MPI_GRAPH);
#endif
this->comm_ptr = comm_ptr;
}
public:
/**
* Build a new Boost.MPI graph communicator based on the MPI
* communicator @p comm with graph topology.
*
* @p comm may be any valid MPI communicator. If @p comm is
* MPI_COMM_NULL, an empty communicator (that cannot be used for
* communication) is created and the @p kind parameter is
* ignored. Otherwise, the @p kind parameter determines how the
* Boost.MPI communicator will be related to @p comm:
*
* - If @p kind is @c comm_duplicate, duplicate @c comm to create
* a new communicator. This new communicator will be freed when
* the Boost.MPI communicator (and all copies of it) is
* destroyed. This option is only permitted if the underlying MPI
* implementation supports MPI 2.0; duplication of
* intercommunicators is not available in MPI 1.x.
*
* - If @p kind is @c comm_take_ownership, take ownership of @c
* comm. It will be freed automatically when all of the Boost.MPI
* communicators go out of scope.
*
* - If @p kind is @c comm_attach, this Boost.MPI communicator
* will reference the existing MPI communicator @p comm but will
* not free @p comm when the Boost.MPI communicator goes out of
* scope. This option should only be used when the communicator is
* managed by the user.
*/
graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
: communicator(comm, kind)
{
#ifndef BOOST_DISABLE_ASSERTS
int status;
BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
BOOST_ASSERT(status == MPI_GRAPH);
#endif
}
/**
* Create a new communicator whose topology is described by the
* given graph. The indices of the vertices in the graph will be
* assumed to be the ranks of the processes within the
* communicator. There may be fewer vertices in the graph than
* there are processes in the communicator; in this case, the
* resulting communicator will be a NULL communicator.
*
* @param comm The communicator that the new, graph communicator
* will be based on.
*
* @param graph Any type that meets the requirements of the
* Incidence Graph and Vertex List Graph concepts from the Boost Graph
* Library. This structure of this graph will become the topology
* of the communicator that is returned.
*
* @param reorder Whether MPI is permitted to re-order the process
* ranks within the returned communicator, to better optimize
* communication. If false, the ranks of each process in the
* returned process will match precisely the rank of that process
* within the original communicator.
*/
template<typename Graph>
explicit
graph_communicator(const communicator& comm, const Graph& graph,
bool reorder = false);
/**
* Create a new communicator whose topology is described by the
* given graph. The rank map (@p rank) gives the mapping from
* vertices in the graph to ranks within the communicator. There
* may be fewer vertices in the graph than there are processes in
* the communicator; in this case, the resulting communicator will
* be a NULL communicator.
*
* @param comm The communicator that the new, graph communicator
* will be based on. The ranks in @c rank refer to the processes in
* this communicator.
*
* @param graph Any type that meets the requirements of the
* Incidence Graph and Vertex List Graph concepts from the Boost Graph
* Library. This structure of this graph will become the topology
* of the communicator that is returned.
*
* @param rank This map translates vertices in the @c graph into
* ranks within the current communicator. It must be a Readable
* Property Map (see the Boost Property Map library) whose key type
* is the vertex type of the @p graph and whose value type is @c
* int.
*
* @param reorder Whether MPI is permitted to re-order the process
* ranks within the returned communicator, to better optimize
* communication. If false, the ranks of each process in the
* returned process will match precisely the rank of that process
* within the original communicator.
*/
template<typename Graph, typename RankMap>
explicit
graph_communicator(const communicator& comm, const Graph& graph,
RankMap rank, bool reorder = false);
protected:
/**
* INTERNAL ONLY
*
* Used by the constructors to create the new communicator with a
* graph topology.
*/
template<typename Graph, typename RankMap>
void
setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
bool reorder);
};
/****************************************************************************
* Implementation Details *
****************************************************************************/
template<typename Graph>
graph_communicator::graph_communicator(const communicator& comm,
const Graph& graph,
bool reorder)
{
this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
}
template<typename Graph, typename RankMap>
graph_communicator::graph_communicator(const communicator& comm,
const Graph& graph,
RankMap rank, bool reorder)
{
this->setup_graph(comm, graph, rank, reorder);
}
template<typename Graph, typename RankMap>
void
graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
RankMap rank, bool reorder)
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
// Build a mapping from ranks to vertices
std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
if (vertex_with_rank.empty())
return;
BGL_FORALL_VERTICES_T(v, graph, Graph)
vertex_with_rank[get(rank, v)] = v;
// Build the representation of the graph required by
// MPI_Graph_create.
std::vector<int> indices(num_vertices(graph));
std::vector<int> edges;
int nvertices = indices.size();
for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
vertex_descriptor v = vertex_with_rank[vertex_index];
BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
edges.push_back(get(rank, target(e, graph)));
indices[vertex_index] = edges.size();
}
// Create the new communicator
MPI_Comm newcomm;
BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
((MPI_Comm)comm,
nvertices,
&indices[0],
edges.empty()? (int*)0 : &edges[0],
reorder,
&newcomm));
this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
}
/****************************************************************************
* Communicator with Graph Topology as BGL Graph *
****************************************************************************/
namespace detail {
/**
* INTERNAL ONLY
*
* The iterator used to access the outgoing edges within a
* communicator's graph topology.
*/
class comm_out_edge_iterator
: public iterator_facade<comm_out_edge_iterator,
std::pair<int, int>,
random_access_traversal_tag,
const std::pair<int, int>&,
int>
{
public:
comm_out_edge_iterator() { }
comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
: edge(source, -1), neighbors(neighbors), index(index) { }
protected:
friend class boost::iterator_core_access;
const std::pair<int, int>& dereference() const
{
edge.second = neighbors[index];
return edge;
}
bool equal(const comm_out_edge_iterator& other) const
{
return (edge.first == other.edge.first
&& index == other.index);
}
void increment() { ++index; }
void decrement() { --index; }
void advance(int n) { index += n; }
int distance_to(const comm_out_edge_iterator& other) const
{
return other.index - index;
}
mutable std::pair<int, int> edge;
shared_array<int> neighbors;
int index;
};
/**
* INTERNAL ONLY
*
* The iterator used to access the adjacent vertices within a
* communicator's graph topology.
*/
class comm_adj_iterator
: public iterator_facade<comm_adj_iterator,
int,
random_access_traversal_tag,
int,
int>
{
public:
comm_adj_iterator() { }
comm_adj_iterator(shared_array<int> neighbors, int index)
: neighbors(neighbors), index(index) { }
protected:
friend class boost::iterator_core_access;
int dereference() const { return neighbors[index]; }
bool equal(const comm_adj_iterator& other) const
{
return (neighbors == other.neighbors
&& index == other.index);
}
void increment() { ++index; }
void decrement() { --index; }
void advance(int n) { index += n; }
int distance_to(const comm_adj_iterator& other) const
{
return other.index - index;
}
shared_array<int> neighbors;
int index;
};
/**
* INTERNAL ONLY
*
* The iterator used to access the edges in a communicator's graph
* topology.
*/
class comm_edge_iterator
: public iterator_facade<comm_edge_iterator,
std::pair<int, int>,
forward_traversal_tag,
const std::pair<int, int>&,
int>
{
public:
comm_edge_iterator() { }
/// Constructor for a past-the-end iterator
comm_edge_iterator(int nedges) : edge_index(nedges) { }
comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
: indices(indices), edges(edges), edge_index(0), edge(0, 0)
{ }
protected:
friend class boost::iterator_core_access;
const std::pair<int, int>& dereference() const
{
while (edge_index == indices[edge.first])
++edge.first;
edge.second = edges[edge_index];
return edge;
}
bool equal(const comm_edge_iterator& other) const
{
return edge_index == other.edge_index;
}
void increment()
{
++edge_index;
}
shared_array<int> indices;
shared_array<int> edges;
int edge_index;
mutable std::pair<int, int> edge;
};
} // end namespace detail
// Incidence Graph requirements
/**
* @brief Returns the source vertex from an edge in the graph topology
* of a communicator.
*/
inline int source(const std::pair<int, int>& edge, const graph_communicator&)
{
return edge.first;
}
/**
* @brief Returns the target vertex from an edge in the graph topology
* of a communicator.
*/
inline int target(const std::pair<int, int>& edge, const graph_communicator&)
{
return edge.second;
}
/**
* @brief Returns an iterator range containing all of the edges
* outgoing from the given vertex in a graph topology of a
* communicator.
*/
std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
out_edges(int vertex, const graph_communicator& comm);
/**
* @brief Returns the out-degree of a vertex in the graph topology of
* a communicator.
*/
int out_degree(int vertex, const graph_communicator& comm);
// Adjacency Graph requirements
/**
* @brief Returns an iterator range containing all of the neighbors of
* the given vertex in the communicator's graph topology.
*/
std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
adjacent_vertices(int vertex, const graph_communicator& comm);
// Vertex List Graph requirements
/**
* @brief Returns an iterator range that contains all of the vertices
* with the communicator's graph topology, i.e., all of the process
* ranks in the communicator.
*/
inline std::pair<counting_iterator<int>, counting_iterator<int> >
vertices(const graph_communicator& comm)
{
return std::make_pair(counting_iterator<int>(0),
counting_iterator<int>(comm.size()));
}
/**
* @brief Returns the number of vertices within the graph topology of
* the communicator, i.e., the number of processes in the
* communicator.
*/
inline int num_vertices(const graph_communicator& comm) { return comm.size(); }
// Edge List Graph requirements
/**
* @brief Returns an iterator range that contains all of the edges
* with the communicator's graph topology.
*/
std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
edges(const graph_communicator& comm);
/**
* @brief Returns the number of edges in the communicator's graph
* topology.
*/
int num_edges(const graph_communicator& comm);
// Property Graph requirements
/**
* @brief Returns a property map that maps from vertices in a
* communicator's graph topology to their index values.
*
* Since the vertices are ranks in the communicator, the returned
* property map is the identity property map.
*/
inline identity_property_map get(vertex_index_t, const graph_communicator&)
{
return identity_property_map();
}
/**
* @brief Returns the index of a vertex in the communicator's graph
* topology.
*
* Since the vertices are ranks in the communicator, this is the
* identity function.
*/
inline int get(vertex_index_t, const graph_communicator&, int vertex)
{
return vertex;
}
} } // end namespace boost::mpi
namespace boost {
/**
* @brief Traits structure that allows a communicator with graph
* topology to be view as a graph by the Boost Graph Library.
*
* The specialization of @c graph_traits for an MPI communicator
* allows a communicator with graph topology to be viewed as a
* graph. An MPI communicator with graph topology meets the
* requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
* List Graph, and Edge List Graph concepts from the Boost Graph
* Library.
*/
template<>
struct graph_traits<mpi::graph_communicator> {
// Graph concept requirements
typedef int vertex_descriptor;
typedef std::pair<int, int> edge_descriptor;
typedef directed_tag directed_category;
typedef disallow_parallel_edge_tag edge_parallel_category;
/**
* INTERNAL ONLY
*/
struct traversal_category
: incidence_graph_tag,
adjacency_graph_tag,
vertex_list_graph_tag,
edge_list_graph_tag
{
};
/**
* @brief Returns a vertex descriptor that can never refer to any
* valid vertex.
*/
static vertex_descriptor null_vertex() { return -1; }
// Incidence Graph requirements
typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
typedef int degree_size_type;
// Adjacency Graph requirements
typedef mpi::detail::comm_adj_iterator adjacency_iterator;
// Vertex List Graph requirements
typedef counting_iterator<int> vertex_iterator;
typedef int vertices_size_type;
// Edge List Graph requirements
typedef mpi::detail::comm_edge_iterator edge_iterator;
typedef int edges_size_type;
};
// Property Graph requirements
/**
* INTERNAL ONLY
*/
template<>
struct property_map<mpi::graph_communicator, vertex_index_t>
{
typedef identity_property_map type;
typedef identity_property_map const_type;
};
} // end namespace boost
#endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP