boost/mpi/graph_communicator.hpp

   1 // Copyright (C) 2007 Trustees of Indiana University
   2
   3 // Authors: Douglas Gregor
   4 //          Andrew Lumsdaine
   5
   6 // Use, modification and distribution is subject to the Boost Software
   7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 /** @file graph_communicator.hpp
  11  *
  12  *  This header defines facilities to support MPI communicators with
  13  *  graph topologies, using the graph interface defined by the Boost
  14  *  Graph Library. One can construct a communicator whose topology is
  15  *  described by any graph meeting the requirements of the Boost Graph
  16  *  Library's graph concepts. Likewise, any communicator that has a
  17  *  graph topology can be viewed as a graph by the Boost Graph
  18  *  Library, permitting one to use the BGL's graph algorithms on the
  19  *  process topology.
  20  */
  21 #ifndef BOOST_MPI_GRAPH_COMMUNICATOR_HPP
  22 #define BOOST_MPI_GRAPH_COMMUNICATOR_HPP
  23
  24 #include <boost/mpi/communicator.hpp>
  25 #include <vector>
  26 #include <utility>
  27
  28 // Headers required to implement graph topologies
  29 #include <boost/graph/graph_traits.hpp>
  30 #include <boost/graph/properties.hpp>
  31 #include <boost/iterator/counting_iterator.hpp>
  32 #include <boost/graph/iteration_macros.hpp>
  33 #include <boost/shared_array.hpp>
  34 #include <boost/assert.hpp>
  35
  36 namespace boost { namespace mpi {
  37
  38 /**
  39  * @brief An MPI communicator with a graph topology.
  40  *
  41  * A @c graph_communicator is a communicator whose topology is
  42  * expressed as a graph. Graph communicators have the same
  43  * functionality as (intra)communicators, but also allow one to query
  44  * the relationships among processes. Those relationships are
  45  * expressed via a graph, using the interface defined by the Boost
  46  * Graph Library. The @c graph_communicator class meets the
  47  * requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
  48  * Vertex List Graph, and Edge List Graph concepts.
  49  */
  50 class BOOST_MPI_DECL graph_communicator : public communicator
  51 {
  52   friend class communicator;
  53
  54   /**
  55    * INTERNAL ONLY
  56    *
  57    * Construct a graph communicator given a shared pointer to the
  58    * underlying MPI_Comm. This operation is used for "casting" from a
  59    * communicator to a graph communicator.
  60    */
  61   explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
  62   {
  63 #ifndef BOOST_DISABLE_ASSERTS
  64     int status;
  65     BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
  66     BOOST_ASSERT(status == MPI_GRAPH);
  67 #endif
  68     this->comm_ptr = comm_ptr;
  69   }
  70
  71 public:
  72   /**
  73    * Build a new Boost.MPI graph communicator based on the MPI
  74    * communicator @p comm with graph topology.
  75    *
  76    * @p comm may be any valid MPI communicator. If @p comm is
  77    * MPI_COMM_NULL, an empty communicator (that cannot be used for
  78    * communication) is created and the @p kind parameter is
  79    * ignored. Otherwise, the @p kind parameter determines how the
  80    * Boost.MPI communicator will be related to @p comm:
  81    *
  82    *   - If @p kind is @c comm_duplicate, duplicate @c comm to create
  83    *   a new communicator. This new communicator will be freed when
  84    *   the Boost.MPI communicator (and all copies of it) is
  85    *   destroyed. This option is only permitted if the underlying MPI
  86    *   implementation supports MPI 2.0; duplication of
  87    *   intercommunicators is not available in MPI 1.x.
  88    *
  89    *   - If @p kind is @c comm_take_ownership, take ownership of @c
  90    *   comm. It will be freed automatically when all of the Boost.MPI
  91    *   communicators go out of scope.
  92    *
  93    *   - If @p kind is @c comm_attach, this Boost.MPI communicator
  94    *   will reference the existing MPI communicator @p comm but will
  95    *   not free @p comm when the Boost.MPI communicator goes out of
  96    *   scope. This option should only be used when the communicator is
  97    *   managed by the user.
  98    */
  99   graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
 100     : communicator(comm, kind)
 101   {
 102 #ifndef BOOST_DISABLE_ASSERTS
 103     int status;
 104     BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
 105     BOOST_ASSERT(status == MPI_GRAPH);
 106 #endif
 107   }
 108
 109   /**
 110    *  Create a new communicator whose topology is described by the
 111    *  given graph. The indices of the vertices in the graph will be
 112    *  assumed to be the ranks of the processes within the
 113    *  communicator. There may be fewer vertices in the graph than
 114    *  there are processes in the communicator; in this case, the
 115    *  resulting communicator will be a NULL communicator.
 116    *
 117    *  @param comm The communicator that the new, graph communicator
 118    *  will be based on.
 119    *
 120    *  @param graph Any type that meets the requirements of the
 121    *  Incidence Graph and Vertex List Graph concepts from the Boost Graph
 122    *  Library. This structure of this graph will become the topology
 123    *  of the communicator that is returned.
 124    *
 125    *  @param reorder Whether MPI is permitted to re-order the process
 126    *  ranks within the returned communicator, to better optimize
 127    *  communication. If false, the ranks of each process in the
 128    *  returned process will match precisely the rank of that process
 129    *  within the original communicator.
 130    */
 131   template<typename Graph>
 132   explicit
 133   graph_communicator(const communicator& comm, const Graph& graph,
 134                      bool reorder = false);
 135
 136   /**
 137    *  Create a new communicator whose topology is described by the
 138    *  given graph. The rank map (@p rank) gives the mapping from
 139    *  vertices in the graph to ranks within the communicator. There
 140    *  may be fewer vertices in the graph than there are processes in
 141    *  the communicator; in this case, the resulting communicator will
 142    *  be a NULL communicator.
 143    *
 144    *  @param comm The communicator that the new, graph communicator
 145    *  will be based on. The ranks in @c rank refer to the processes in
 146    *  this communicator.
 147    *
 148    *  @param graph Any type that meets the requirements of the
 149    *  Incidence Graph and Vertex List Graph concepts from the Boost Graph
 150    *  Library. This structure of this graph will become the topology
 151    *  of the communicator that is returned.
 152    *
 153    *  @param rank This map translates vertices in the @c graph into
 154    *  ranks within the current communicator. It must be a Readable
 155    *  Property Map (see the Boost Property Map library) whose key type
 156    *  is the vertex type of the @p graph and whose value type is @c
 157    *  int.
 158    *
 159    *  @param reorder Whether MPI is permitted to re-order the process
 160    *  ranks within the returned communicator, to better optimize
 161    *  communication. If false, the ranks of each process in the
 162    *  returned process will match precisely the rank of that process
 163    *  within the original communicator.
 164    */
 165   template<typename Graph, typename RankMap>
 166   explicit
 167   graph_communicator(const communicator& comm, const Graph& graph,
 168                      RankMap rank, bool reorder = false);
 169
 170 protected:
 171   /**
 172    * INTERNAL ONLY
 173    *
 174    * Used by the constructors to create the new communicator with a
 175    * graph topology.
 176    */
 177   template<typename Graph, typename RankMap>
 178   void
 179   setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
 180               bool reorder);
 181 };
 182
 183 /****************************************************************************
 184  *  Implementation Details                                                  *
 185  ****************************************************************************/
 186
 187 template<typename Graph>
 188 graph_communicator::graph_communicator(const communicator& comm,
 189                                        const Graph& graph,
 190                                        bool reorder)
 191 {
 192   this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
 193 }
 194
 195 template<typename Graph, typename RankMap>
 196 graph_communicator::graph_communicator(const communicator& comm,
 197                                        const Graph& graph,
 198                                        RankMap rank, bool reorder)
 199 {
 200   this->setup_graph(comm, graph, rank, reorder);
 201 }
 202
 203
 204 template<typename Graph, typename RankMap>
 205 void
 206 graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
 207                                 RankMap rank, bool reorder)
 208 {
 209   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 210
 211   // Build a mapping from ranks to vertices
 212   std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
 213   if (vertex_with_rank.empty())
 214     return;
 215
 216   BGL_FORALL_VERTICES_T(v, graph, Graph)
 217     vertex_with_rank[get(rank, v)] = v;
 218
 219   // Build the representation of the graph required by
 220   // MPI_Graph_create.
 221   std::vector<int> indices(num_vertices(graph));
 222   std::vector<int> edges;
 223   int nvertices = indices.size();
 224   for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
 225     vertex_descriptor v = vertex_with_rank[vertex_index];
 226
 227     BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
 228       edges.push_back(get(rank, target(e, graph)));
 229
 230     indices[vertex_index] = edges.size();
 231   }
 232
 233   // Create the new communicator
 234   MPI_Comm newcomm;
 235   BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
 236                          ((MPI_Comm)comm,
 237                           nvertices,
 238                           &indices[0],
 239                           edges.empty()? (int*)0 : &edges[0],
 240                           reorder,
 241                           &newcomm));
 242   this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
 243 }
 244
 245 /****************************************************************************
 246  *  Communicator with Graph Topology as BGL Graph                           *
 247  ****************************************************************************/
 248 namespace detail {
 249   /**
 250    *  INTERNAL ONLY
 251    *
 252    *  The iterator used to access the outgoing edges within a
 253    *  communicator's graph topology.
 254    */
 255   class comm_out_edge_iterator
 256     : public iterator_facade<comm_out_edge_iterator,
 257                              std::pair<int, int>,
 258                              random_access_traversal_tag,
 259                              const std::pair<int, int>&,
 260                              int>
 261   {
 262   public:
 263     comm_out_edge_iterator() { }
 264
 265     comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
 266       : edge(source, -1), neighbors(neighbors), index(index) { }
 267
 268   protected:
 269     friend class boost::iterator_core_access;
 270
 271     const std::pair<int, int>& dereference() const
 272     {
 273       edge.second = neighbors[index];
 274       return edge;
 275     }
 276
 277     bool equal(const comm_out_edge_iterator& other) const
 278     {
 279       return (edge.first == other.edge.first
 280               && index == other.index);
 281     }
 282
 283     void increment() { ++index; }
 284
 285     void decrement() { --index; }
 286
 287     void advance(int n) { index += n; }
 288
 289     int distance_to(const comm_out_edge_iterator& other) const
 290     {
 291       return other.index - index;
 292     }
 293
 294     mutable std::pair<int, int> edge;
 295     shared_array<int> neighbors;
 296     int index;
 297   };
 298
 299   /**
 300    *  INTERNAL ONLY
 301    *
 302    *  The iterator used to access the adjacent vertices within a
 303    *  communicator's graph topology.
 304    */
 305   class comm_adj_iterator
 306     : public iterator_facade<comm_adj_iterator,
 307                              int,
 308                              random_access_traversal_tag,
 309                              int,
 310                              int>
 311   {
 312   public:
 313     comm_adj_iterator() { }
 314
 315     comm_adj_iterator(shared_array<int> neighbors, int index)
 316       : neighbors(neighbors), index(index) { }
 317
 318   protected:
 319     friend class boost::iterator_core_access;
 320
 321     int dereference() const { return neighbors[index]; }
 322
 323     bool equal(const comm_adj_iterator& other) const
 324     {
 325       return (neighbors == other.neighbors
 326               && index == other.index);
 327     }
 328
 329     void increment() { ++index; }
 330
 331     void decrement() { --index; }
 332
 333     void advance(int n) { index += n; }
 334
 335     int distance_to(const comm_adj_iterator& other) const
 336     {
 337       return other.index - index;
 338     }
 339
 340     shared_array<int> neighbors;
 341     int index;
 342   };
 343
 344   /**
 345    *  INTERNAL ONLY
 346    *
 347    *  The iterator used to access the edges in a communicator's graph
 348    *  topology.
 349    */
 350   class comm_edge_iterator
 351     : public iterator_facade<comm_edge_iterator,
 352                              std::pair<int, int>,
 353                              forward_traversal_tag,
 354                              const std::pair<int, int>&,
 355                              int>
 356   {
 357   public:
 358     comm_edge_iterator() { }
 359
 360     /// Constructor for a past-the-end iterator
 361     comm_edge_iterator(int nedges) : edge_index(nedges) { }
 362
 363     comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
 364       : indices(indices), edges(edges), edge_index(0), edge(0, 0)
 365     { }
 366
 367   protected:
 368     friend class boost::iterator_core_access;
 369
 370     const std::pair<int, int>& dereference() const
 371     {
 372       while (edge_index == indices[edge.first])
 373         ++edge.first;
 374       edge.second = edges[edge_index];
 375       return edge;
 376     }
 377
 378     bool equal(const comm_edge_iterator& other) const
 379     {
 380       return edge_index == other.edge_index;
 381     }
 382
 383     void increment()
 384     {
 385       ++edge_index;
 386     }
 387
 388     shared_array<int> indices;
 389     shared_array<int> edges;
 390     int edge_index;
 391     mutable std::pair<int, int> edge;
 392   };
 393
 394 } // end namespace detail
 395
 396 // Incidence Graph requirements
 397
 398 /**
 399  * @brief Returns the source vertex from an edge in the graph topology
 400  * of a communicator.
 401  */
 402 inline int source(const std::pair<int, int>& edge, const graph_communicator&)
 403 {
 404   return edge.first;
 405 }
 406
 407 /**
 408  * @brief Returns the target vertex from an edge in the graph topology
 409  * of a communicator.
 410  */
 411 inline int target(const std::pair<int, int>& edge, const graph_communicator&)
 412 {
 413   return edge.second;
 414 }
 415
 416 /**
 417  * @brief Returns an iterator range containing all of the edges
 418  * outgoing from the given vertex in a graph topology of a
 419  * communicator.
 420  */
 421 std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
 422 out_edges(int vertex, const graph_communicator& comm);
 423
 424
 425 /**
 426  * @brief Returns the out-degree of a vertex in the graph topology of
 427  * a communicator.
 428  */
 429 int out_degree(int vertex, const graph_communicator& comm);
 430
 431 // Adjacency Graph requirements
 432
 433 /**
 434  * @brief Returns an iterator range containing all of the neighbors of
 435  * the given vertex in the communicator's graph topology.
 436  */
 437 std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
 438 adjacent_vertices(int vertex, const graph_communicator& comm);
 439
 440 // Vertex List Graph requirements
 441
 442 /**
 443  * @brief Returns an iterator range that contains all of the vertices
 444  * with the communicator's graph topology, i.e., all of the process
 445  * ranks in the communicator.
 446  */
 447 inline std::pair<counting_iterator<int>, counting_iterator<int> >
 448 vertices(const graph_communicator& comm)
 449 {
 450   return std::make_pair(counting_iterator<int>(0),
 451                         counting_iterator<int>(comm.size()));
 452 }
 453
 454 /**
 455  *  @brief Returns the number of vertices within the graph topology of
 456  *  the communicator, i.e., the number of processes in the
 457  *  communicator.
 458  */
 459 inline int num_vertices(const graph_communicator& comm) { return comm.size(); }
 460
 461 // Edge List Graph requirements
 462
 463 /**
 464  * @brief Returns an iterator range that contains all of the edges
 465  * with the communicator's graph topology.
 466  */
 467 std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
 468 edges(const graph_communicator& comm);
 469
 470 /**
 471  * @brief Returns the number of edges in the communicator's graph
 472  * topology.
 473  */
 474 int num_edges(const graph_communicator& comm);
 475
 476 // Property Graph requirements
 477
 478 /**
 479  *  @brief Returns a property map that maps from vertices in a
 480  *  communicator's graph topology to their index values.
 481  *
 482  *  Since the vertices are ranks in the communicator, the returned
 483  *  property map is the identity property map.
 484  */
 485 inline identity_property_map get(vertex_index_t, const graph_communicator&)
 486 {
 487   return identity_property_map();
 488 }
 489
 490 /**
 491  * @brief Returns the index of a vertex in the communicator's graph
 492  * topology.
 493  *
 494  * Since the vertices are ranks in the communicator, this is the
 495  *  identity function.
 496  */
 497 inline int get(vertex_index_t, const graph_communicator&, int vertex)
 498 {
 499   return vertex;
 500 }
 501
 502 } } // end namespace boost::mpi
 503
 504 namespace boost {
 505
 506 /**
 507  * @brief Traits structure that allows a communicator with graph
 508  * topology to be view as a graph by the Boost Graph Library.
 509  *
 510  * The specialization of @c graph_traits for an MPI communicator
 511  * allows a communicator with graph topology to be viewed as a
 512  * graph. An MPI communicator with graph topology meets the
 513  * requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
 514  * List Graph, and Edge List Graph concepts from the Boost Graph
 515  * Library.
 516  */
 517 template<>
 518 struct graph_traits<mpi::graph_communicator> {
 519   // Graph concept requirements
 520   typedef int                        vertex_descriptor;
 521   typedef std::pair<int, int>        edge_descriptor;
 522   typedef directed_tag               directed_category;
 523   typedef disallow_parallel_edge_tag edge_parallel_category;
 524
 525   /**
 526    * INTERNAL ONLY
 527    */
 528   struct traversal_category
 529     : incidence_graph_tag,
 530       adjacency_graph_tag,
 531       vertex_list_graph_tag,
 532       edge_list_graph_tag
 533   {
 534   };
 535
 536   /**
 537    * @brief Returns a vertex descriptor that can never refer to any
 538    * valid vertex.
 539    */
 540   static vertex_descriptor null_vertex() { return -1; }
 541
 542   // Incidence Graph requirements
 543   typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
 544   typedef int degree_size_type;
 545
 546   // Adjacency Graph requirements
 547   typedef mpi::detail::comm_adj_iterator adjacency_iterator;
 548
 549   // Vertex List Graph requirements
 550   typedef counting_iterator<int> vertex_iterator;
 551   typedef int                    vertices_size_type;
 552
 553   // Edge List Graph requirements
 554   typedef mpi::detail::comm_edge_iterator edge_iterator;
 555   typedef int                             edges_size_type;
 556 };
 557
 558 // Property Graph requirements
 559
 560 /**
 561  * INTERNAL ONLY
 562  */
 563 template<>
 564 struct property_map<mpi::graph_communicator, vertex_index_t>
 565 {
 566   typedef identity_property_map type;
 567   typedef identity_property_map const_type;
 568 };
 569
 570 } // end namespace boost
 571
 572
 573
 574 #endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP