ceph/src/boost/libs/compute/include/boost/compute/algorithm/accumulate.hpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
   3 //
   4 // Distributed under the Boost Software License, Version 1.0
   5 // See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt
   7 //
   8 // See http://boostorg.github.com/compute for more information.
   9 //---------------------------------------------------------------------------//
  10
  11 #ifndef BOOST_COMPUTE_ALGORITHM_ACCUMULATE_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_ACCUMULATE_HPP
  13
  14 #include <boost/preprocessor/seq/for_each.hpp>
  15
  16 #include <boost/compute/system.hpp>
  17 #include <boost/compute/functional.hpp>
  18 #include <boost/compute/command_queue.hpp>
  19 #include <boost/compute/algorithm/reduce.hpp>
  20 #include <boost/compute/algorithm/detail/serial_accumulate.hpp>
  21 #include <boost/compute/container/array.hpp>
  22 #include <boost/compute/container/vector.hpp>
  23 #include <boost/compute/detail/iterator_range_size.hpp>
  24
  25 namespace boost {
  26 namespace compute {
  27 namespace detail {
  28
  29 template<class InputIterator, class T, class BinaryFunction>
  30 inline T generic_accumulate(InputIterator first,
  31                             InputIterator last,
  32                             T init,
  33                             BinaryFunction function,
  34                             command_queue &queue)
  35 {
  36     const context &context = queue.get_context();
  37
  38     size_t size = iterator_range_size(first, last);
  39     if(size == 0){
  40         return init;
  41     }
  42
  43     // accumulate on device
  44     array<T, 1> device_result(context);
  45     detail::serial_accumulate(
  46         first, last, device_result.begin(), init, function, queue
  47     );
  48
  49     // copy result to host
  50     T result;
  51     ::boost::compute::copy_n(device_result.begin(), 1, &result, queue);
  52     return result;
  53 }
  54
  55 // returns true if we can use reduce() instead of accumulate() when
  56 // accumulate() this is true when the function is commutative (such as
  57 // addition of integers) and the initial value is the identity value
  58 // for the operation (zero for addition, one for multiplication).
  59 template<class T, class F>
  60 inline bool can_accumulate_with_reduce(T init, F function)
  61 {
  62     (void) init;
  63     (void) function;
  64
  65     return false;
  66 }
  67
  68 /// \internal_
  69 #define BOOST_COMPUTE_DETAIL_DECLARE_CAN_ACCUMULATE_WITH_REDUCE(r, data, type) \
  70     inline bool can_accumulate_with_reduce(type init, plus<type>) \
  71     { \
  72         return init == type(0); \
  73     } \
  74     inline bool can_accumulate_with_reduce(type init, multiplies<type>) \
  75     { \
  76         return init == type(1); \
  77     }
  78
  79 BOOST_PP_SEQ_FOR_EACH(
  80     BOOST_COMPUTE_DETAIL_DECLARE_CAN_ACCUMULATE_WITH_REDUCE,
  81     _,
  82     (char_)(uchar_)(short_)(ushort_)(int_)(uint_)(long_)(ulong_)
  83 )
  84
  85 template<class T>
  86 inline bool can_accumulate_with_reduce(T init, min<T>)
  87 {
  88     return init == (std::numeric_limits<T>::max)();
  89 }
  90
  91 template<class T>
  92 inline bool can_accumulate_with_reduce(T init, max<T>)
  93 {
  94     return init == (std::numeric_limits<T>::min)();
  95 }
  96
  97 #undef BOOST_COMPUTE_DETAIL_DECLARE_CAN_ACCUMULATE_WITH_REDUCE
  98
  99 template<class InputIterator, class T, class BinaryFunction>
 100 inline T dispatch_accumulate(InputIterator first,
 101                              InputIterator last,
 102                              T init,
 103                              BinaryFunction function,
 104                              command_queue &queue)
 105 {
 106     size_t size = iterator_range_size(first, last);
 107     if(size == 0){
 108         return init;
 109     }
 110
 111     if(can_accumulate_with_reduce(init, function)){
 112         T result;
 113         reduce(first, last, &result, function, queue);
 114         return result;
 115     }
 116     else {
 117         return generic_accumulate(first, last, init, function, queue);
 118     }
 119 }
 120
 121 } // end detail namespace
 122
 123 /// Returns the result of applying \p function to the elements in the
 124 /// range [\p first, \p last) and \p init.
 125 ///
 126 /// If no function is specified, \c plus will be used.
 127 ///
 128 /// \param first first element in the input range
 129 /// \param last last element in the input range
 130 /// \param init initial value
 131 /// \param function binary reduction function
 132 /// \param queue command queue to perform the operation
 133 ///
 134 /// \return the accumulated result value
 135 ///
 136 /// In specific situations the call to \c accumulate() can be automatically
 137 /// optimized to a call to the more efficient \c reduce() algorithm. This
 138 /// occurs when the binary reduction function is recognized as associative
 139 /// (such as the \c plus<int> function).
 140 ///
 141 /// Note that because floating-point addition is not associative, calling
 142 /// \c accumulate() with \c plus<float> results in a less efficient serial
 143 /// reduction algorithm being executed. If a slight loss in precision is
 144 /// acceptable, the more efficient parallel \c reduce() algorithm should be
 145 /// used instead.
 146 ///
 147 /// For example:
 148 /// \code
 149 /// // with vec = boost::compute::vector<int>
 150 /// accumulate(vec.begin(), vec.end(), 0, plus<int>());   // fast
 151 /// reduce(vec.begin(), vec.end(), &result, plus<int>()); // fast
 152 ///
 153 /// // with vec = boost::compute::vector<float>
 154 /// accumulate(vec.begin(), vec.end(), 0, plus<float>());   // slow
 155 /// reduce(vec.begin(), vec.end(), &result, plus<float>()); // fast
 156 /// \endcode
 157 ///
 158 /// \see reduce()
 159 template<class InputIterator, class T, class BinaryFunction>
 160 inline T accumulate(InputIterator first,
 161                     InputIterator last,
 162                     T init,
 163                     BinaryFunction function,
 164                     command_queue &queue = system::default_queue())
 165 {
 166     return detail::dispatch_accumulate(first, last, init, function, queue);
 167 }
 168
 169 /// \overload
 170 template<class InputIterator, class T>
 171 inline T accumulate(InputIterator first,
 172                     InputIterator last,
 173                     T init,
 174                     command_queue &queue = system::default_queue())
 175 {
 176     typedef typename std::iterator_traits<InputIterator>::value_type IT;
 177
 178     return detail::dispatch_accumulate(first, last, init, plus<IT>(), queue);
 179 }
 180
 181 } // end compute namespace
 182 } // end boost namespace
 183
 184 #endif // BOOST_COMPUTE_ALGORITHM_ACCUMULATE_HPP