]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2005-2006 Douglas Gregor <doug.gregor@gmail.com>. |
2 | // Copyright (C) 2004 The Trustees of Indiana University | |
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 | ||
11 | // Message Passing Interface 1.1 -- Section 4.9.1. Scan | |
12 | #ifndef BOOST_MPI_SCAN_HPP | |
13 | #define BOOST_MPI_SCAN_HPP | |
14 | ||
15 | #include <boost/mpi/exception.hpp> | |
16 | #include <boost/mpi/datatype.hpp> | |
17 | ||
18 | // For (de-)serializing sends and receives | |
19 | #include <boost/mpi/packed_oarchive.hpp> | |
20 | #include <boost/mpi/packed_iarchive.hpp> | |
21 | ||
22 | // For packed_[io]archive sends and receives | |
23 | #include <boost/mpi/detail/point_to_point.hpp> | |
24 | ||
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> | |
29 | #include <algorithm> | |
30 | #include <exception> | |
31 | #include <boost/assert.hpp> | |
32 | ||
33 | namespace boost { namespace mpi { | |
34 | ||
35 | ||
36 | /************************************************************************ | |
37 | * Implementation details * | |
38 | ************************************************************************/ | |
39 | namespace detail { | |
40 | /********************************************************************** | |
41 | * Simple prefix reduction with MPI_Scan * | |
42 | **********************************************************************/ | |
43 | ||
44 | // We are performing prefix reduction for a type that has an | |
45 | // associated MPI datatype and operation, so we'll use MPI_Scan | |
46 | // directly. | |
47 | template<typename T, typename Op> | |
48 | void | |
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*/) | |
51 | { | |
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)); | |
56 | } | |
57 | ||
58 | /********************************************************************** | |
59 | * User-defined prefix reduction with MPI_Scan * | |
60 | **********************************************************************/ | |
61 | ||
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> | |
66 | void | |
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*/) | |
69 | { | |
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)); | |
75 | } | |
76 | ||
77 | /********************************************************************** | |
78 | * User-defined, tree-based reduction for non-MPI data types * | |
79 | **********************************************************************/ | |
80 | ||
81 | template<typename T, typename Op> | |
82 | void | |
83 | upper_lower_scan(const communicator& comm, const T* in_values, int n, | |
84 | T* out_values, Op& op, int lower, int upper) | |
85 | { | |
86 | int tag = environment::collectives_tag(); | |
87 | int rank = comm.rank(); | |
88 | ||
89 | if (lower + 1 == upper) { | |
90 | std::copy(in_values, in_values + n, out_values); | |
91 | } else { | |
92 | int middle = (lower + upper) / 2; | |
93 | ||
94 | if (rank < middle) { | |
95 | // Lower half | |
96 | upper_lower_scan(comm, in_values, n, out_values, op, lower, middle); | |
97 | ||
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) | |
103 | oa << out_values[i]; | |
104 | ||
105 | for (int p = middle; p < upper; ++p) | |
106 | comm.send(p, tag, oa); | |
107 | } | |
108 | } else { | |
109 | // Upper half | |
110 | upper_lower_scan(comm, in_values, n, out_values, op, middle, upper); | |
111 | ||
112 | // Receive value from the last process in the lower half. | |
113 | packed_iarchive ia(comm); | |
114 | comm.recv(middle - 1, tag, ia); | |
115 | ||
116 | // Combine value that came from the left with our value | |
117 | T left_value; | |
118 | for (int i = 0; i < n; ++i) | |
119 | { | |
120 | ia >> left_value; | |
121 | out_values[i] = op(left_value, out_values[i]); | |
122 | } | |
123 | } | |
124 | } | |
125 | } | |
126 | ||
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> | |
131 | inline void | |
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*/) | |
134 | { | |
135 | upper_lower_scan(comm, in_values, n, out_values, op, 0, comm.size()); | |
136 | } | |
137 | } // end namespace detail | |
138 | ||
139 | ||
140 | template<typename T, typename Op> | |
141 | inline void | |
142 | scan(const communicator& comm, const T& in_value, T& out_value, Op op) | |
143 | { | |
144 | detail::scan_impl(comm, &in_value, 1, &out_value, op, | |
145 | is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
146 | } | |
147 | ||
148 | template<typename T, typename Op> | |
149 | inline void | |
150 | scan(const communicator& comm, const T* in_values, int n, T* out_values, Op op) | |
151 | { | |
152 | detail::scan_impl(comm, in_values, n, out_values, op, | |
153 | is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
154 | } | |
155 | ||
156 | template<typename T, typename Op> | |
157 | inline T | |
158 | scan(const communicator& comm, const T& in_value, Op op) | |
159 | { | |
160 | T out_value; | |
161 | detail::scan_impl(comm, &in_value, 1, &out_value, op, | |
162 | is_mpi_op<Op, T>(), is_mpi_datatype<T>()); | |
163 | return out_value; | |
164 | } | |
165 | ||
166 | } } // end namespace boost::mpi | |
167 | ||
168 | #endif // BOOST_MPI_SCAN_HPP |