]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2004-2006 The Trustees of Indiana University. |
2 | // Copyright (C) 2002 Brad King and Douglas Gregor | |
3 | ||
4 | // Use, modification and distribution is subject to the Boost Software | |
5 | // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // Authors: Douglas Gregor | |
9 | // Andrew Lumsdaine | |
10 | // Brian Barrett | |
11 | #ifndef BOOST_PARALLEL_GRAPH_PAGE_RANK_HPP | |
12 | #define BOOST_PARALLEL_GRAPH_PAGE_RANK_HPP | |
13 | ||
14 | #ifndef BOOST_GRAPH_USE_MPI | |
15 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
16 | #endif | |
17 | ||
18 | #include <boost/assert.hpp> | |
19 | #include <boost/graph/overloading.hpp> | |
20 | #include <boost/graph/page_rank.hpp> | |
21 | #include <boost/graph/distributed/concepts.hpp> | |
22 | #include <boost/property_map/parallel/distributed_property_map.hpp> | |
23 | #include <boost/property_map/parallel/caching_property_map.hpp> | |
24 | #include <boost/graph/parallel/algorithm.hpp> | |
25 | #include <boost/graph/parallel/container_traits.hpp> | |
26 | ||
27 | // #define WANT_MPI_ONESIDED 1 | |
28 | ||
29 | namespace boost { namespace graph { namespace distributed { | |
30 | ||
31 | namespace detail { | |
32 | #ifdef WANT_MPI_ONESIDED | |
33 | template<typename Graph, typename RankMap, typename owner_map_t> | |
34 | void page_rank_step(const Graph& g, RankMap from_rank, MPI_Win to_win, | |
35 | typename property_traits<RankMap>::value_type damping, | |
36 | owner_map_t owner) | |
37 | { | |
38 | typedef typename property_traits<RankMap>::value_type rank_type; | |
39 | int me, ret; | |
40 | MPI_Comm_rank(MPI_COMM_WORLD, &me); | |
41 | ||
42 | // MPI_Accumulate is not required to store the value of the data | |
43 | // being sent, only the address. The value of the memory location | |
44 | // must not change until the end of the access epoch, meaning the | |
45 | // call to MPI_Fence. We therefore store the updated value back | |
46 | // into the from_rank map before the accumulate rather than using | |
47 | // a temporary. We're going to reset the values in the from_rank | |
48 | // before the end of page_rank_step() anyway, so this isn't a huge | |
49 | // deal. But MPI-2 One-sided is an abomination. | |
50 | BGL_FORALL_VERTICES_T(u, g, Graph) { | |
51 | put(from_rank, u, (damping * get(from_rank, u) / out_degree(u, g))); | |
52 | BGL_FORALL_ADJ_T(u, v, g, Graph) { | |
53 | ret = MPI_Accumulate(&(from_rank[u]), | |
54 | 1, MPI_DOUBLE, | |
55 | get(owner, v), local(v), | |
56 | 1, MPI_DOUBLE, MPI_SUM, to_win); | |
57 | BOOST_ASSERT(MPI_SUCCESS == ret); | |
58 | } | |
59 | } | |
60 | MPI_Win_fence(0, to_win); | |
61 | ||
62 | // Set new rank maps for the other map. Do this now to get around | |
63 | // the stupid synchronization rules of MPI-2 One-sided | |
64 | BGL_FORALL_VERTICES_T(v, g, Graph) put(from_rank, v, rank_type(1 - damping)); | |
65 | } | |
66 | #endif | |
67 | ||
68 | template<typename T> | |
69 | struct rank_accumulate_reducer { | |
70 | BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); | |
71 | ||
72 | template<typename K> | |
73 | T operator()(const K&) const { return T(0); } | |
74 | ||
75 | template<typename K> | |
76 | T operator()(const K&, const T& x, const T& y) const { return x + y; } | |
77 | }; | |
78 | } // end namespace detail | |
79 | ||
80 | template<typename Graph, typename RankMap, typename Done, typename RankMap2> | |
81 | void | |
82 | page_rank_impl(const Graph& g, RankMap rank_map, Done done, | |
83 | typename property_traits<RankMap>::value_type damping, | |
84 | typename graph_traits<Graph>::vertices_size_type n, | |
85 | RankMap2 rank_map2) | |
86 | { | |
87 | typedef typename property_traits<RankMap>::value_type rank_type; | |
88 | ||
89 | int me; | |
90 | MPI_Comm_rank(MPI_COMM_WORLD, &me); | |
91 | ||
92 | typename property_map<Graph, vertex_owner_t>::const_type | |
93 | owner = get(vertex_owner, g); | |
94 | (void)owner; | |
95 | ||
96 | typedef typename boost::graph::parallel::process_group_type<Graph> | |
97 | ::type process_group_type; | |
98 | typedef typename process_group_type::process_id_type process_id_type; | |
99 | ||
100 | process_group_type pg = process_group(g); | |
101 | process_id_type id = process_id(pg); | |
102 | ||
103 | BOOST_ASSERT(me == id); | |
104 | ||
105 | rank_type initial_rank = rank_type(rank_type(1) / n); | |
106 | BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, initial_rank); | |
107 | ||
108 | #ifdef WANT_MPI_ONESIDED | |
109 | ||
110 | BOOST_ASSERT(sizeof(rank_type) == sizeof(double)); | |
111 | ||
112 | bool to_map_2 = true; | |
113 | MPI_Win win, win2; | |
114 | ||
115 | MPI_Win_create(&(rank_map[*(vertices(g).first)]), | |
116 | sizeof(double) * num_vertices(g), | |
117 | sizeof(double), | |
118 | MPI_INFO_NULL, MPI_COMM_WORLD, &win); | |
119 | MPI_Win_set_name(win, "rank_map_win"); | |
120 | MPI_Win_create(&(rank_map2[*(vertices(g).first)]), | |
121 | sizeof(double) * num_vertices(g), | |
122 | sizeof(double), | |
123 | MPI_INFO_NULL, MPI_COMM_WORLD, &win2); | |
124 | MPI_Win_set_name(win, "rank_map2_win"); | |
125 | ||
126 | // set initial rank maps for the first iteration... | |
127 | BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map2, v, rank_type(1 - damping)); | |
128 | ||
129 | MPI_Win_fence(0, win); | |
130 | MPI_Win_fence(0, win2); | |
131 | ||
132 | while ((to_map_2 && !done(rank_map, g)) || | |
133 | (!to_map_2 && !done(rank_map2, g))) { | |
134 | if (to_map_2) { | |
135 | graph::distributed::detail::page_rank_step(g, rank_map, win2, damping, owner); | |
136 | to_map_2 = false; | |
137 | } else { | |
138 | graph::distributed::detail::page_rank_step(g, rank_map2, win, damping, owner); | |
139 | to_map_2 = true; | |
140 | } | |
141 | } | |
142 | synchronize(boost::graph::parallel::process_group(g)); | |
143 | ||
144 | MPI_Win_free(&win); | |
145 | MPI_Win_free(&win2); | |
146 | ||
147 | #else | |
148 | // The ranks accumulate after each step. | |
149 | rank_map.set_reduce(detail::rank_accumulate_reducer<rank_type>()); | |
150 | rank_map2.set_reduce(detail::rank_accumulate_reducer<rank_type>()); | |
151 | rank_map.set_consistency_model(boost::parallel::cm_flush | boost::parallel::cm_reset); | |
152 | rank_map2.set_consistency_model(boost::parallel::cm_flush | boost::parallel::cm_reset); | |
153 | ||
154 | bool to_map_2 = true; | |
155 | while ((to_map_2 && !done(rank_map, g)) || | |
156 | (!to_map_2 && !done(rank_map2, g))) { | |
157 | /** | |
158 | * PageRank can implemented slightly more efficiently on a | |
159 | * bidirectional graph than on an incidence graph. However, | |
160 | * distributed PageRank requires that we have the rank of the | |
161 | * source vertex available locally, so we force the incidence | |
162 | * graph implementation, which pushes rank from source to | |
163 | * target. | |
164 | */ | |
165 | typedef incidence_graph_tag category; | |
166 | if (to_map_2) { | |
167 | graph::detail::page_rank_step(g, rank_map, rank_map2, damping, | |
168 | category()); | |
169 | to_map_2 = false; | |
170 | } else { | |
171 | graph::detail::page_rank_step(g, rank_map2, rank_map, damping, | |
172 | category()); | |
173 | to_map_2 = true; | |
174 | } | |
175 | using boost::graph::parallel::process_group; | |
176 | synchronize(process_group(g)); | |
177 | } | |
178 | ||
179 | rank_map.reset(); | |
180 | #endif | |
181 | ||
182 | if (!to_map_2) | |
183 | BGL_FORALL_VERTICES_T(v, g, Graph) put(rank_map, v, get(rank_map2, v)); | |
184 | } | |
185 | ||
186 | template<typename Graph, typename RankMap, typename Done, typename RankMap2> | |
187 | void | |
188 | page_rank(const Graph& g, RankMap rank_map, Done done, | |
189 | typename property_traits<RankMap>::value_type damping, | |
190 | typename graph_traits<Graph>::vertices_size_type n, | |
191 | RankMap2 rank_map2 | |
192 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag)) | |
193 | { | |
194 | (page_rank_impl)(g, rank_map, done, damping, n, rank_map2); | |
195 | } | |
196 | ||
197 | template<typename MutableGraph> | |
198 | void | |
199 | remove_dangling_links(MutableGraph& g | |
200 | BOOST_GRAPH_ENABLE_IF_MODELS_PARM(MutableGraph, | |
201 | distributed_graph_tag)) | |
202 | { | |
203 | typename graph_traits<MutableGraph>::vertices_size_type old_n; | |
204 | do { | |
205 | old_n = num_vertices(g); | |
206 | ||
207 | typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end; | |
208 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; /* in loop */) { | |
209 | typename graph_traits<MutableGraph>::vertex_descriptor v = *vi++; | |
210 | if (out_degree(v, g) == 0) { | |
211 | clear_vertex(v, g); | |
212 | remove_vertex(v, g); | |
213 | } | |
214 | } | |
215 | } while (num_vertices(g) < old_n); | |
216 | } | |
217 | ||
218 | } // end namespace distributed | |
219 | ||
220 | using distributed::page_rank; | |
221 | using distributed::remove_dangling_links; | |
222 | ||
223 | } } // end namespace boost::graph | |
224 | ||
225 | #endif // BOOST_PARALLEL_GRAPH_PAGE_RANK_HPP |