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