mpi/collectives/scan.hpp

0001 // Copyright (C) 2005-2006 Douglas Gregor <doug.gregor@gmail.com>.
0002 // Copyright (C) 2004 The Trustees of Indiana University
0003
0004 // Use, modification and distribution is subject to the Boost Software
0005 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007
0008 //   Authors: Douglas Gregor
0009 //            Andrew Lumsdaine
0010
0011 // Message Passing Interface 1.1 -- Section 4.9.1. Scan
0012 #ifndef BOOST_MPI_SCAN_HPP
0013 #define BOOST_MPI_SCAN_HPP
0014
0015 #include <boost/mpi/exception.hpp>
0016 #include <boost/mpi/datatype.hpp>
0017
0018 // For (de-)serializing sends and receives
0019 #include <boost/mpi/packed_oarchive.hpp>
0020 #include <boost/mpi/packed_iarchive.hpp>
0021
0022 // For packed_[io]archive sends and receives
0023 #include <boost/mpi/detail/point_to_point.hpp>
0024
0025 #include <boost/mpi/communicator.hpp>
0026 #include <boost/mpi/environment.hpp>
0027 #include <boost/mpi/detail/computation_tree.hpp>
0028 #include <boost/mpi/operations.hpp>
0029 #include <algorithm>
0030 #include <exception>
0031 #include <boost/assert.hpp>
0032
0033 namespace boost { namespace mpi {
0034
0035
0036 /************************************************************************
0037  * Implementation details                                               *
0038  ************************************************************************/
0039 namespace detail {
0040   /**********************************************************************
0041    * Simple prefix reduction with MPI_Scan                              *
0042    **********************************************************************/
0043
0044   // We are performing prefix reduction for a type that has an
0045   // associated MPI datatype and operation, so we'll use MPI_Scan
0046   // directly.
0047   template<typename T, typename Op>
0048   void
0049   scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
0050             Op /*op*/, mpl::true_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/)
0051   {
0052     BOOST_MPI_CHECK_RESULT(MPI_Scan,
0053                            (const_cast<T*>(in_values), out_values, n,
0054                             boost::mpi::get_mpi_datatype<T>(*in_values),
0055                             (is_mpi_op<Op, T>::op()), comm));
0056   }
0057
0058   /**********************************************************************
0059    * User-defined prefix reduction with MPI_Scan                        *
0060    **********************************************************************/
0061
0062   // We are performing prefix reduction for a type that has an
0063   // associated MPI datatype but with a custom operation. We'll use
0064   // MPI_Scan directly, but we'll need to create an MPI_Op manually.
0065   template<typename T, typename Op>
0066   void
0067   scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
0068             Op op, mpl::false_ /*is_mpi_op*/, mpl::true_ /*is_mpi_datatype*/)
0069   {
0070     user_op<Op, T> mpi_op;
0071     BOOST_MPI_CHECK_RESULT(MPI_Scan,
0072                            (const_cast<T*>(in_values), out_values, n,
0073                             boost::mpi::get_mpi_datatype<T>(*in_values),
0074                             mpi_op.get_mpi_op(), comm));
0075   }
0076
0077   /**********************************************************************
0078    * User-defined, tree-based reduction for non-MPI data types          *
0079    **********************************************************************/
0080
0081   template<typename T, typename Op>
0082   void
0083   upper_lower_scan(const communicator& comm, const T* in_values, int n,
0084                    T* out_values, Op& op, int lower, int upper)
0085   {
0086     int tag = environment::collectives_tag();
0087     int rank = comm.rank();
0088
0089     if (lower + 1 == upper) {
0090       std::copy(in_values, in_values + n, out_values);
0091     } else {
0092       int middle = (lower + upper) / 2;
0093
0094       if (rank < middle) {
0095         // Lower half
0096         upper_lower_scan(comm, in_values, n, out_values, op, lower, middle);
0097
0098         // If we're the last process in the lower half, send our values
0099         // to everyone in the upper half.
0100         if (rank == middle - 1) {
0101           packed_oarchive oa(comm);
0102           for (int i = 0; i < n; ++i)
0103             oa << out_values[i];
0104
0105           for (int p = middle; p < upper; ++p)
0106             comm.send(p, tag, oa);
0107         }
0108       } else {
0109         // Upper half
0110         upper_lower_scan(comm, in_values, n, out_values, op, middle, upper);
0111
0112         // Receive value from the last process in the lower half.
0113         packed_iarchive ia(comm);
0114         comm.recv(middle - 1, tag, ia);
0115
0116         // Combine value that came from the left with our value
0117         T left_value;
0118         for (int i = 0; i < n; ++i)
0119           {
0120             ia >> left_value;
0121             out_values[i] = op(left_value, out_values[i]);
0122           }
0123       }
0124     }
0125   }
0126
0127   // We are performing prefix reduction for a type that has no
0128   // associated MPI datatype and operation, so we'll use a simple
0129   // upper/lower algorithm.
0130   template<typename T, typename Op>
0131   inline void
0132   scan_impl(const communicator& comm, const T* in_values, int n, T* out_values,
0133             Op op, mpl::false_ /*is_mpi_op*/, mpl::false_/*is_mpi_datatype*/)
0134   {
0135     upper_lower_scan(comm, in_values, n, out_values, op, 0, comm.size());
0136   }
0137 } // end namespace detail
0138
0139
0140 template<typename T, typename Op>
0141 inline void
0142 scan(const communicator& comm, const T& in_value, T& out_value, Op op)
0143 {
0144   detail::scan_impl(comm, &in_value, 1, &out_value, op,
0145                     is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0146 }
0147
0148 template<typename T, typename Op>
0149 inline void
0150 scan(const communicator& comm, const T* in_values, int n, T* out_values, Op op)
0151 {
0152   detail::scan_impl(comm, in_values, n, out_values, op,
0153                     is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0154 }
0155
0156 template<typename T, typename Op>
0157 inline T
0158 scan(const communicator& comm, const T& in_value, Op op)
0159 {
0160   T out_value;
0161   detail::scan_impl(comm, &in_value, 1, &out_value, op,
0162                     is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0163   return out_value;
0164 }
0165
0166 } } // end namespace boost::mpi
0167
0168 #endif // BOOST_MPI_SCAN_HPP