1 // Copyright (C) 2005-2006 Douglas Gregor <doug.gregor@gmail.com>.
2 // Copyright (C) 2004 The Trustees of Indiana University
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)
8 // Authors: Douglas Gregor
11 // Message Passing Interface 1.1 -- Section 4.9.1. Reduce
12 #ifndef BOOST_MPI_REDUCE_HPP
13 #define BOOST_MPI_REDUCE_HPP
15 #include <boost/mpi/exception.hpp>
16 #include <boost/mpi/datatype.hpp>
18 // For (de-)serializing sends and receives
19 #include <boost/mpi/packed_oarchive.hpp>
20 #include <boost/mpi/packed_iarchive.hpp>
22 // For packed_[io]archive sends and receives
23 #include <boost/mpi/detail/point_to_point.hpp>
25 #include <boost/mpi/communicator.hpp>
26 #include <boost/mpi/environment.hpp>
27 #include <boost/mpi/detail/computation_tree.hpp>
28 #include <boost/mpi/operations.hpp>
31 #include <boost/assert.hpp>
32 #include <boost/scoped_array.hpp>
34 namespace boost { namespace mpi {
37 /************************************************************************
38 * Implementation details *
39 ************************************************************************/
41 /**********************************************************************
42 * Simple reduction with MPI_Reduce *
43 **********************************************************************/
44 // We are reducing at the root for a type that has an associated MPI
45 // datatype and operation, so we'll use MPI_Reduce directly.
46 template<typename T, typename Op>
48 reduce_impl(const communicator& comm, const T* in_values, int n,
49 T* out_values, Op op, int root, mpl::true_ /*is_mpi_op*/,
50 mpl::true_/*is_mpi_datatype*/)
52 BOOST_MPI_CHECK_RESULT(MPI_Reduce,
53 (const_cast<T*>(in_values), out_values, n,
54 boost::mpi::get_mpi_datatype<T>(*in_values),
55 (is_mpi_op<Op, T>::op()), root, comm));
58 // We are reducing to the root for a type that has an associated MPI
59 // datatype and operation, so we'll use MPI_Reduce directly.
60 template<typename T, typename Op>
62 reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
63 int root, mpl::true_ /*is_mpi_op*/, mpl::true_/*is_mpi_datatype*/)
65 BOOST_MPI_CHECK_RESULT(MPI_Reduce,
66 (const_cast<T*>(in_values), 0, n,
67 boost::mpi::get_mpi_datatype<T>(*in_values),
68 (is_mpi_op<Op, T>::op()), root, comm));
71 /**********************************************************************
72 * User-defined reduction with MPI_Reduce *
73 **********************************************************************/
75 // We are reducing at the root for a type that has an associated MPI
76 // datatype but with a custom operation. We'll use MPI_Reduce
77 // directly, but we'll need to create an MPI_Op manually.
78 template<typename T, typename Op>
80 reduce_impl(const communicator& comm, const T* in_values, int n,
81 T* out_values, Op op, int root, mpl::false_ /*is_mpi_op*/,
82 mpl::true_/*is_mpi_datatype*/)
84 user_op<Op, T> mpi_op(op);
85 BOOST_MPI_CHECK_RESULT(MPI_Reduce,
86 (const_cast<T*>(in_values), out_values, n,
87 boost::mpi::get_mpi_datatype<T>(*in_values),
88 mpi_op.get_mpi_op(), root, comm));
91 // We are reducing to the root for a type that has an associated MPI
92 // datatype but with a custom operation. We'll use MPI_Reduce
93 // directly, but we'll need to create an MPI_Op manually.
94 template<typename T, typename Op>
96 reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
97 int root, mpl::false_/*is_mpi_op*/, mpl::true_/*is_mpi_datatype*/)
99 user_op<Op, T> mpi_op(op);
100 BOOST_MPI_CHECK_RESULT(MPI_Reduce,
101 (const_cast<T*>(in_values), 0, n,
102 boost::mpi::get_mpi_datatype<T>(*in_values),
103 mpi_op.get_mpi_op(), root, comm));
106 /**********************************************************************
107 * User-defined, tree-based reduction for non-MPI data types *
108 **********************************************************************/
110 // Commutative reduction
111 template<typename T, typename Op>
113 tree_reduce_impl(const communicator& comm, const T* in_values, int n,
114 T* out_values, Op op, int root,
115 mpl::true_ /*is_commutative*/)
117 std::copy(in_values, in_values + n, out_values);
119 int size = comm.size();
120 int rank = comm.rank();
122 // The computation tree we will use.
123 detail::computation_tree tree(rank, size, root);
125 int tag = environment::collectives_tag();
129 for (int child = tree.child_begin();
130 children < tree.branching_factor() && child != root;
131 ++children, child = (child + 1) % size) {
133 packed_iarchive ia(comm);
134 detail::packed_archive_recv(comm, child, tag, ia, status);
137 for (int i = 0; i < n; ++i) {
139 out_values[i] = op(out_values[i], incoming);
143 // For non-roots, send the result to the parent.
144 if (tree.parent() != rank) {
145 packed_oarchive oa(comm);
146 for (int i = 0; i < n; ++i)
148 detail::packed_archive_send(comm, tree.parent(), tag, oa);
152 // Commutative reduction from a non-root.
153 template<typename T, typename Op>
155 tree_reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
156 int root, mpl::true_ /*is_commutative*/)
158 scoped_array<T> results(new T[n]);
159 detail::tree_reduce_impl(comm, in_values, n, results.get(), op, root,
163 // Non-commutative reduction
164 template<typename T, typename Op>
166 tree_reduce_impl(const communicator& comm, const T* in_values, int n,
167 T* out_values, Op op, int root,
168 mpl::false_ /*is_commutative*/)
170 int tag = environment::collectives_tag();
172 int left_child = root / 2;
173 int right_child = (root + comm.size()) / 2;
176 if (left_child != root) {
177 // Receive value from the left child and merge it with the value
179 packed_iarchive ia(comm);
180 detail::packed_archive_recv(comm, left_child, tag, ia, status);
182 for (int i = 0; i < n; ++i) {
184 out_values[i] = op(incoming, in_values[i]);
187 // There was no left value, so copy our incoming value.
188 std::copy(in_values, in_values + n, out_values);
191 if (right_child != root) {
192 // Receive value from the right child and merge it with the
193 // value we had incoming.
194 packed_iarchive ia(comm);
195 detail::packed_archive_recv(comm, right_child, tag, ia, status);
197 for (int i = 0; i < n; ++i) {
199 out_values[i] = op(out_values[i], incoming);
204 // Non-commutative reduction from a non-root.
205 template<typename T, typename Op>
207 tree_reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
208 int root, mpl::false_ /*is_commutative*/)
210 int size = comm.size();
211 int rank = comm.rank();
213 int tag = environment::collectives_tag();
215 // Determine our parents and children in the commutative binary
217 int grandparent = root;
220 int right_bound = size;
221 int left_child, right_child;
223 left_child = (left_bound + parent) / 2;
224 right_child = (parent + right_bound) / 2;
228 grandparent = parent;
229 right_bound = parent;
231 } else if (rank > parent) {
233 grandparent = parent;
234 left_bound = parent + 1;
235 parent = right_child;
237 // We've found the parent
242 // Our parent is the grandparent of our children. This is a slight
243 // abuse of notation, but it makes the send-to-parent below make
245 parent = grandparent;
248 scoped_array<T> out_values(new T[n]);
249 if (left_child != rank) {
250 // Receive value from the left child and merge it with the value
252 packed_iarchive ia(comm);
253 detail::packed_archive_recv(comm, left_child, tag, ia, status);
255 for (int i = 0; i < n; ++i) {
257 out_values[i] = op(incoming, in_values[i]);
260 // There was no left value, so copy our incoming value.
261 std::copy(in_values, in_values + n, out_values.get());
264 if (right_child != rank) {
265 // Receive value from the right child and merge it with the
266 // value we had incoming.
267 packed_iarchive ia(comm);
268 detail::packed_archive_recv(comm, right_child, tag, ia, status);
270 for (int i = 0; i < n; ++i) {
272 out_values[i] = op(out_values[i], incoming);
276 // Send the combined value to our parent.
277 packed_oarchive oa(comm);
278 for (int i = 0; i < n; ++i)
280 detail::packed_archive_send(comm, parent, tag, oa);
283 // We are reducing at the root for a type that has no associated MPI
284 // datatype and operation, so we'll use a simple tree-based
286 template<typename T, typename Op>
288 reduce_impl(const communicator& comm, const T* in_values, int n,
289 T* out_values, Op op, int root, mpl::false_ /*is_mpi_op*/,
290 mpl::false_ /*is_mpi_datatype*/)
292 detail::tree_reduce_impl(comm, in_values, n, out_values, op, root,
293 is_commutative<Op, T>());
296 // We are reducing to the root for a type that has no associated MPI
297 // datatype and operation, so we'll use a simple tree-based
299 template<typename T, typename Op>
301 reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
302 int root, mpl::false_ /*is_mpi_op*/,
303 mpl::false_ /*is_mpi_datatype*/)
305 detail::tree_reduce_impl(comm, in_values, n, op, root,
306 is_commutative<Op, T>());
308 } // end namespace detail
310 template<typename T, typename Op>
312 reduce(const communicator& comm, const T* in_values, int n, T* out_values,
315 if (comm.rank() == root)
316 detail::reduce_impl(comm, in_values, n, out_values, op, root,
317 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
319 detail::reduce_impl(comm, in_values, n, op, root,
320 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
323 template<typename T, typename Op>
325 reduce(const communicator& comm, const T* in_values, int n, Op op, int root)
327 BOOST_ASSERT(comm.rank() != root);
329 detail::reduce_impl(comm, in_values, n, op, root,
330 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
333 template<typename T, typename Op>
335 reduce(const communicator & comm, std::vector<T> const & in_values, Op op,
338 reduce(comm, &in_values.front(), in_values.size(), op, root);
341 template<typename T, typename Op>
343 reduce(const communicator & comm, std::vector<T> const & in_values,
344 std::vector<T> & out_values, Op op, int root)
346 out_values.resize(in_values.size());
347 reduce(comm, &in_values.front(), in_values.size(), &out_values.front(), op,
352 template<typename T, typename Op>
354 reduce(const communicator& comm, const T& in_value, T& out_value, Op op,
357 if (comm.rank() == root)
358 detail::reduce_impl(comm, &in_value, 1, &out_value, op, root,
359 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
361 detail::reduce_impl(comm, &in_value, 1, op, root,
362 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
365 template<typename T, typename Op>
366 void reduce(const communicator& comm, const T& in_value, Op op, int root)
368 BOOST_ASSERT(comm.rank() != root);
370 detail::reduce_impl(comm, &in_value, 1, op, root,
371 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
374 } } // end namespace boost::mpi
376 #endif // BOOST_MPI_REDUCE_HPP