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. Scan
12 #ifndef BOOST_MPI_SCAN_HPP
13 #define BOOST_MPI_SCAN_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>
33 namespace boost { namespace mpi {
36 /************************************************************************
37 * Implementation details *
38 ************************************************************************/
40 /**********************************************************************
41 * Simple prefix reduction with MPI_Scan *
42 **********************************************************************/
44 // We are performing prefix reduction for a type that has an
45 // associated MPI datatype and operation, so we'll use MPI_Scan
47 template<typename T, typename Op>
49 scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
50 Op /*op*/, mpl::true_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/)
52 BOOST_MPI_CHECK_RESULT(MPI_Scan,
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()), comm));
58 /**********************************************************************
59 * User-defined prefix reduction with MPI_Scan *
60 **********************************************************************/
62 // We are performing prefix reduction for a type that has an
63 // associated MPI datatype but with a custom operation. We'll use
64 // MPI_Scan directly, but we'll need to create an MPI_Op manually.
65 template<typename T, typename Op>
67 scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
68 Op op, mpl::false_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/)
70 user_op<Op, T> mpi_op(op);
71 BOOST_MPI_CHECK_RESULT(MPI_Scan,
72 (const_cast<T*>(in_values), out_values, n,
73 boost::mpi::get_mpi_datatype<T>(*in_values),
74 mpi_op.get_mpi_op(), comm));
77 /**********************************************************************
78 * User-defined, tree-based reduction for non-MPI data types *
79 **********************************************************************/
81 template<typename T, typename Op>
83 upper_lower_scan(const communicator& comm, const T* in_values, int n,
84 T* out_values, Op& op, int lower, int upper)
86 int tag = environment::collectives_tag();
87 int rank = comm.rank();
89 if (lower + 1 == upper) {
90 std::copy(in_values, in_values + n, out_values);
92 int middle = (lower + upper) / 2;
96 upper_lower_scan(comm, in_values, n, out_values, op, lower, middle);
98 // If we're the last process in the lower half, send our values
99 // to everyone in the upper half.
100 if (rank == middle - 1) {
101 packed_oarchive oa(comm);
102 for (int i = 0; i < n; ++i)
105 for (int p = middle; p < upper; ++p)
106 comm.send(p, tag, oa);
110 upper_lower_scan(comm, in_values, n, out_values, op, middle, upper);
112 // Receive value from the last process in the lower half.
113 packed_iarchive ia(comm);
114 comm.recv(middle - 1, tag, ia);
116 // Combine value that came from the left with our value
118 for (int i = 0; i < n; ++i)
121 out_values[i] = op(left_value, out_values[i]);
127 // We are performing prefix reduction for a type that has no
128 // associated MPI datatype and operation, so we'll use a simple
129 // upper/lower algorithm.
130 template<typename T, typename Op>
132 scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
133 Op op, mpl::false_ /*is_mpi_op*/, mpl::false_/*is_mpi_datatype*/)
135 upper_lower_scan(comm, in_values, n, out_values, op, 0, comm.size());
137 } // end namespace detail
140 template<typename T, typename Op>
142 scan(const communicator& comm, const T& in_value, T& out_value, Op op)
144 detail::scan_impl(comm, &in_value, 1, &out_value, op,
145 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
148 template<typename T, typename Op>
150 scan(const communicator& comm, const T* in_values, int n, T* out_values, Op op)
152 detail::scan_impl(comm, in_values, n, out_values, op,
153 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
156 template<typename T, typename Op>
158 scan(const communicator& comm, const T& in_value, Op op)
161 detail::scan_impl(comm, &in_value, 1, &out_value, op,
162 is_mpi_op<Op, T>(), is_mpi_datatype<T>());
166 } } // end namespace boost::mpi
168 #endif // BOOST_MPI_SCAN_HPP