]>
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> | |
7c673cae FG |
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 |