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