// 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 |