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