mpi/collectives/reduce.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. Reduce
0012 #ifndef BOOST_MPI_REDUCE_HPP
0013 #define BOOST_MPI_REDUCE_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 #include <boost/scoped_array.hpp>
0033
0034 namespace boost { namespace mpi {
0035
0036
0037 /************************************************************************
0038  * Implementation details                                               *
0039  ************************************************************************/
0040 namespace detail {
0041   /**********************************************************************
0042    * Simple reduction with MPI_Reduce                                   *
0043    **********************************************************************/
0044   // We are reducing at the root for a type that has an associated MPI
0045   // datatype and operation, so we'll use MPI_Reduce directly.
0046   template<typename T, typename Op>
0047   void
0048   reduce_impl(const communicator& comm, const T* in_values, int n,
0049               T* out_values, Op /*op*/, int root, mpl::true_ /*is_mpi_op*/,
0050               mpl::true_/*is_mpi_datatype*/)
0051   {
0052     BOOST_MPI_CHECK_RESULT(MPI_Reduce,
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()), root, comm));
0056   }
0057
0058   // We are reducing to the root for a type that has an associated MPI
0059   // datatype and operation, so we'll use MPI_Reduce directly.
0060   template<typename T, typename Op>
0061   void
0062   reduce_impl(const communicator& comm, const T* in_values, int n, Op /*op*/,
0063               int root, mpl::true_ /*is_mpi_op*/, mpl::true_/*is_mpi_datatype*/)
0064   {
0065     BOOST_MPI_CHECK_RESULT(MPI_Reduce,
0066                            (const_cast<T*>(in_values), 0, n,
0067                             boost::mpi::get_mpi_datatype<T>(*in_values),
0068                             (is_mpi_op<Op, T>::op()), root, comm));
0069   }
0070
0071   /**********************************************************************
0072    * User-defined reduction with MPI_Reduce                             *
0073    **********************************************************************/
0074
0075   // We are reducing at the root for a type that has an associated MPI
0076   // datatype but with a custom operation. We'll use MPI_Reduce
0077   // directly, but we'll need to create an MPI_Op manually.
0078   template<typename T, typename Op>
0079   void
0080   reduce_impl(const communicator& comm, const T* in_values, int n,
0081               T* out_values, Op op, int root, mpl::false_ /*is_mpi_op*/,
0082               mpl::true_/*is_mpi_datatype*/)
0083   {
0084     user_op<Op, T> mpi_op;
0085     BOOST_MPI_CHECK_RESULT(MPI_Reduce,
0086                            (const_cast<T*>(in_values), out_values, n,
0087                             boost::mpi::get_mpi_datatype<T>(*in_values),
0088                             mpi_op.get_mpi_op(), root, comm));
0089   }
0090
0091   // We are reducing to the root for a type that has an associated MPI
0092   // datatype but with a custom operation. We'll use MPI_Reduce
0093   // directly, but we'll need to create an MPI_Op manually.
0094   template<typename T, typename Op>
0095   void
0096   reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
0097               int root, mpl::false_/*is_mpi_op*/, mpl::true_/*is_mpi_datatype*/)
0098   {
0099     user_op<Op, T> mpi_op;
0100     BOOST_MPI_CHECK_RESULT(MPI_Reduce,
0101                            (const_cast<T*>(in_values), 0, n,
0102                             boost::mpi::get_mpi_datatype<T>(*in_values),
0103                             mpi_op.get_mpi_op(), root, comm));
0104   }
0105
0106   /**********************************************************************
0107    * User-defined, tree-based reduction for non-MPI data types          *
0108    **********************************************************************/
0109
0110   // Commutative reduction
0111   template<typename T, typename Op>
0112   void
0113   tree_reduce_impl(const communicator& comm, const T* in_values, int n,
0114                    T* out_values, Op op, int root,
0115                    mpl::true_ /*is_commutative*/)
0116   {
0117     std::copy(in_values, in_values + n, out_values);
0118
0119     int size = comm.size();
0120     int rank = comm.rank();
0121
0122     // The computation tree we will use.
0123     detail::computation_tree tree(rank, size, root);
0124
0125     int tag = environment::collectives_tag();
0126
0127     MPI_Status status;
0128     int children = 0;
0129     for (int child = tree.child_begin();
0130          children < tree.branching_factor() && child != root;
0131          ++children, child = (child + 1) % size) {
0132       // Receive archive
0133       packed_iarchive ia(comm);
0134       detail::packed_archive_recv(comm, child, tag, ia, status);
0135
0136       T incoming;
0137       for (int i = 0; i < n; ++i) {
0138         ia >> incoming;
0139         out_values[i] = op(out_values[i], incoming);
0140       }
0141     }
0142
0143     // For non-roots, send the result to the parent.
0144     if (tree.parent() != rank) {
0145       packed_oarchive oa(comm);
0146       for (int i = 0; i < n; ++i)
0147         oa << out_values[i];
0148       detail::packed_archive_send(comm, tree.parent(), tag, oa);
0149     }
0150   }
0151
0152   // Commutative reduction from a non-root.
0153   template<typename T, typename Op>
0154   void
0155   tree_reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
0156                    int root, mpl::true_ /*is_commutative*/)
0157   {
0158     scoped_array<T> results(new T[n]);
0159     detail::tree_reduce_impl(comm, in_values, n, results.get(), op, root,
0160                              mpl::true_());
0161   }
0162
0163   // Non-commutative reduction
0164   template<typename T, typename Op>
0165   void
0166   tree_reduce_impl(const communicator& comm, const T* in_values, int n,
0167                    T* out_values, Op op, int root,
0168                    mpl::false_ /*is_commutative*/)
0169   {
0170     int tag = environment::collectives_tag();
0171
0172     int left_child = root / 2;
0173     int right_child = (root + comm.size()) / 2;
0174
0175     MPI_Status status;
0176     if (left_child != root) {
0177       // Receive value from the left child and merge it with the value
0178       // we had incoming.
0179       packed_iarchive ia(comm);
0180       detail::packed_archive_recv(comm, left_child, tag, ia, status);
0181       T incoming;
0182       for (int i = 0; i < n; ++i) {
0183         ia >> incoming;
0184         out_values[i] = op(incoming, in_values[i]);
0185       }
0186     } else {
0187       // There was no left value, so copy our incoming value.
0188       std::copy(in_values, in_values + n, out_values);
0189     }
0190
0191     if (right_child != root) {
0192       // Receive value from the right child and merge it with the
0193       // value we had incoming.
0194       packed_iarchive ia(comm);
0195       detail::packed_archive_recv(comm, right_child, tag, ia, status);
0196       T incoming;
0197       for (int i = 0; i < n; ++i) {
0198         ia >> incoming;
0199         out_values[i] = op(out_values[i], incoming);
0200       }
0201     }
0202   }
0203
0204   // Non-commutative reduction from a non-root.
0205   template<typename T, typename Op>
0206   void
0207   tree_reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
0208                    int root, mpl::false_ /*is_commutative*/)
0209   {
0210     int size = comm.size();
0211     int rank = comm.rank();
0212
0213     int tag = environment::collectives_tag();
0214
0215     // Determine our parents and children in the commutative binary
0216     // computation tree.
0217     int grandparent = root;
0218     int parent = root;
0219     int left_bound = 0;
0220     int right_bound = size;
0221     int left_child, right_child;
0222     do {
0223       left_child = (left_bound + parent) / 2;
0224       right_child = (parent + right_bound) / 2;
0225
0226       if (rank < parent) {
0227         // Go left.
0228         grandparent = parent;
0229         right_bound = parent;
0230         parent = left_child;
0231       } else if (rank > parent) {
0232         // Go right.
0233         grandparent = parent;
0234         left_bound = parent + 1;
0235         parent = right_child;
0236       } else {
0237         // We've found the parent
0238         break;
0239       }
0240     } while (true);
0241
0242     // Our parent is the grandparent of our children. This is a slight
0243     // abuse of notation, but it makes the send-to-parent below make
0244     // more sense.
0245     parent = grandparent;
0246
0247     MPI_Status status;
0248     scoped_array<T> out_values(new T[n]);
0249     if (left_child != rank) {
0250       // Receive value from the left child and merge it with the value
0251       // we had incoming.
0252       packed_iarchive ia(comm);
0253       detail::packed_archive_recv(comm, left_child, tag, ia, status);
0254       T incoming;
0255       for (int i = 0; i < n; ++i) {
0256         ia >> incoming;
0257         out_values[i] = op(incoming, in_values[i]);
0258       }
0259     } else {
0260       // There was no left value, so copy our incoming value.
0261       std::copy(in_values, in_values + n, out_values.get());
0262     }
0263
0264     if (right_child != rank) {
0265       // Receive value from the right child and merge it with the
0266       // value we had incoming.
0267       packed_iarchive ia(comm);
0268       detail::packed_archive_recv(comm, right_child, tag, ia, status);
0269       T incoming;
0270       for (int i = 0; i < n; ++i) {
0271         ia >> incoming;
0272         out_values[i] = op(out_values[i], incoming);
0273       }
0274     }
0275
0276     // Send the combined value to our parent.
0277     packed_oarchive oa(comm);
0278     for (int i = 0; i < n; ++i)
0279       oa << out_values[i];
0280     detail::packed_archive_send(comm, parent, tag, oa);
0281   }
0282
0283   // We are reducing at the root for a type that has no associated MPI
0284   // datatype and operation, so we'll use a simple tree-based
0285   // algorithm.
0286   template<typename T, typename Op>
0287   void
0288   reduce_impl(const communicator& comm, const T* in_values, int n,
0289               T* out_values, Op op, int root, mpl::false_ /*is_mpi_op*/,
0290               mpl::false_ /*is_mpi_datatype*/)
0291   {
0292     detail::tree_reduce_impl(comm, in_values, n, out_values, op, root,
0293                              is_commutative<Op, T>());
0294   }
0295
0296   // We are reducing to the root for a type that has no associated MPI
0297   // datatype and operation, so we'll use a simple tree-based
0298   // algorithm.
0299   template<typename T, typename Op>
0300   void
0301   reduce_impl(const communicator& comm, const T* in_values, int n, Op op,
0302               int root, mpl::false_ /*is_mpi_op*/,
0303               mpl::false_ /*is_mpi_datatype*/)
0304   {
0305     detail::tree_reduce_impl(comm, in_values, n, op, root,
0306                              is_commutative<Op, T>());
0307   }
0308 } // end namespace detail
0309
0310 template<typename T, typename Op>
0311 void
0312 reduce(const communicator& comm, const T* in_values, int n, T* out_values,
0313        Op op, int root)
0314 {
0315   if (comm.rank() == root)
0316     detail::reduce_impl(comm, in_values, n, out_values, op, root,
0317                         is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0318   else
0319     detail::reduce_impl(comm, in_values, n, op, root,
0320                         is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0321 }
0322
0323 template<typename T, typename Op>
0324 void
0325 reduce(const communicator& comm, const T* in_values, int n, Op op, int root)
0326 {
0327   BOOST_ASSERT(comm.rank() != root);
0328
0329   detail::reduce_impl(comm, in_values, n, op, root,
0330                       is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0331 }
0332
0333 template<typename T, typename Op>
0334 void
0335 reduce(const communicator & comm, std::vector<T> const & in_values, Op op,
0336        int root)
0337 {
0338   reduce(comm, detail::c_data(in_values), in_values.size(), op, root);
0339 }
0340
0341 template<typename T, typename Op>
0342 void
0343 reduce(const communicator & comm, std::vector<T> const & in_values,
0344        std::vector<T> & out_values, Op op, int root)
0345 {
0346   if (root == comm.rank()) out_values.resize(in_values.size());
0347   reduce(comm, detail::c_data(in_values), in_values.size(), detail::c_data(out_values), op,
0348          root);
0349 }
0350
0351
0352 template<typename T, typename Op>
0353 void
0354 reduce(const communicator& comm, const T& in_value, T& out_value, Op op,
0355        int root)
0356 {
0357   if (comm.rank() == root)
0358     detail::reduce_impl(comm, &in_value, 1, &out_value, op, root,
0359                         is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0360   else
0361     detail::reduce_impl(comm, &in_value, 1, op, root,
0362                         is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0363 }
0364
0365 template<typename T, typename Op>
0366 void reduce(const communicator& comm, const T& in_value, Op op, int root)
0367 {
0368   BOOST_ASSERT(comm.rank() != root);
0369
0370   detail::reduce_impl(comm, &in_value, 1, op, root,
0371                       is_mpi_op<Op, T>(), is_mpi_datatype<T>());
0372 }
0373
0374 } } // end namespace boost::mpi
0375
0376 #endif // BOOST_MPI_REDUCE_HPP