ceph/src/boost/boost/mpi/collectives/scan.hpp

   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