1 /* 2 * Copyright (c) 2014-2017, Siemens AG. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * 1. Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * 10 * 2. Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 24 * POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #ifndef EMBB_ALGORITHMS_REDUCE_H_ 28 #define EMBB_ALGORITHMS_REDUCE_H_ 29 30 #include <embb/mtapi/job.h> 31 #include <embb/mtapi/execution_policy.h> 32 #include <embb/algorithms/identity.h> 33 34 namespace embb { 35 namespace algorithms { 36 37 /** 38 * \defgroup CPP_ALGORITHMS_REDUCTION Reduction 39 * Parallel reduction computation 40 * \ingroup CPP_ALGORITHMS 41 * \{ 42 */ 43 44 #ifdef DOXYGEN 45 46 /** 47 * Performs a parallel reduction operation on a range of elements. 48 * 49 * The range consists of the elements from \c first to \c last, excluding the 50 * last element. The type of the result (\c ReturnType) is deduced from the 51 * \c neutral element. 52 * 53 * \return 54 * <tt>reduction(transformation(*first), ..., transformation(*(last-1)))</tt> 55 * where the reduction function is applied pairwise. 56 * \throws embb::base::ErrorException if not enough MTAPI tasks can be created 57 * to satisfy the requirements of the algorithm. 58 * \threadsafe if the elements in the range are not modified by another thread 59 * while the algorithm is executed. 60 * \note No guarantee is given on the order in which the functions \c reduction 61 * and \c transformation are applied to the elements.\n 62 * For all \c x of type \c ReturnType it must hold that 63 * <tt>reduction(x, neutral) == x</tt>. \n 64 * The reduction operation need not be commutative but must be 65 * associative, i.e., <tt>reduction(x, reduction(y, z)) == 66 * reduction(reduction(x, y), z))</tt> for all \c x, \c y, \c z of type 67 * \c ReturnType.<br/> 68 * For nested algorithms, the task limit may be exceeded. In that case, 69 * increase the task limit of the MTAPI node. 70 * \see embb::mtapi::ExecutionPolicy, ZipIterator, Identity 71 * \tparam RAI Random access iterator 72 * \tparam ReturnType Type of result of reduction operation, deduced from 73 * \c neutral 74 * \tparam ReductionFunction Binary reduction function object with signature 75 * <tt>ReturnType ReductionFunction(ReturnType, ReturnType)</tt> or an 76 * embb::mtapi::Job associated with an action function accepting a 77 * struct containing two ReturnType members as its argument buffer 78 * and a struct containing one ReturnType member as its result buffer. 79 * \tparam TransformationFunction Unary transformation function object with 80 * signature <tt>ReturnType TransformationFunction(typename 81 * std::iterator_traits<RAI>::value_type)</tt> or an 82 * embb::mtapi::Job associated with an action function accepting a 83 * struct containing one InputType member as its argument buffer 84 * and a struct containing one ReturnType member as its result buffer. 85 */ 86 template<typename RAI, typename ReturnType, typename ReductionFunction, 87 typename TransformationFunction> 88 ReturnType Reduce( 89 RAI first, 90 /**< [IN] Random access iterator pointing to the first element of the range */ 91 RAI last, 92 /**< [IN] Random access iterator pointing to the last plus one element of the 93 range */ 94 ReturnType neutral, 95 /**< [IN] Neutral element of the reduction operation. */ 96 ReductionFunction reduction, 97 /**< [IN] Reduction operation to be applied to the elements of the range */ 98 TransformationFunction transformation = Identity(), 99 /**< [IN] Transforms the elements of the range before the reduction operation 100 is applied */ 101 const embb::mtapi::ExecutionPolicy& policy = embb::mtapi::ExecutionPolicy(), 102 /**< [IN] embb::mtapi::ExecutionPolicy for the reduction computation */ 103 size_t block_size = 0 104 /**< [IN] Lower bound for partitioning the range of elements into blocks that 105 are treated in parallel. Partitioning of a block stops if its size 106 is less than or equal to \c block_size. The default value 0 means 107 that the minimum block size is determined automatically depending on 108 the number of elements in the range divided by the number of 109 available cores. */ 110 ); 111 112 #else // DOXYGEN 113 114 /** 115 * Overload of above described Doxygen dummy. 116 */ 117 template<typename RAI, typename ReturnType> 118 ReturnType Reduce( 119 RAI first, 120 RAI last, 121 ReturnType neutral, 122 embb::mtapi::Job reduction, 123 embb::mtapi::Job transformation, 124 const embb::mtapi::ExecutionPolicy& policy, 125 size_t block_size 126 ); 127 128 /** 129 * Overload of above described Doxygen dummy. 130 */ 131 template<typename RAI, typename ReturnType, typename ReductionFunction> 132 ReturnType Reduce( 133 RAI first, 134 RAI last, 135 ReturnType neutral, 136 ReductionFunction reduction, 137 embb::mtapi::Job transformation, 138 const embb::mtapi::ExecutionPolicy& policy, 139 size_t block_size 140 ); 141 142 /** 143 * Overload of above described Doxygen dummy. 144 */ 145 template<typename RAI, typename ReturnType, typename TransformationFunction> 146 ReturnType Reduce( 147 RAI first, 148 RAI last, 149 ReturnType neutral, 150 embb::mtapi::Job reduction, 151 TransformationFunction transformation, 152 const embb::mtapi::ExecutionPolicy& policy, 153 size_t block_size 154 ); 155 156 /** 157 * Overload of above described Doxygen dummy. 158 */ 159 template<typename RAI, typename ReturnType, typename ReductionFunction, 160 typename TransformationFunction> 161 ReturnType Reduce( 162 RAI first, 163 RAI last, 164 ReturnType neutral, 165 ReductionFunction reduction, 166 TransformationFunction transformation, 167 const embb::mtapi::ExecutionPolicy& policy, 168 size_t block_size 169 ); 170 171 /** 172 * Overload of above described Doxygen dummy with less arguments. 173 */ 174 template<typename RAI, typename ReturnType, typename ReductionFunction> 175 ReturnType Reduce( 176 RAI first, 177 RAI last, 178 ReturnType neutral, 179 ReductionFunction reduction 180 ) { 181 return Reduce(first, last, neutral, reduction, Identity(), 182 embb::mtapi::ExecutionPolicy(), 0); 183 } 184 185 /** 186 * Overload of above described Doxygen dummy with less arguments. 187 */ 188 template<typename RAI, typename ReturnType, typename ReductionFunction, 189 typename TransformationFunction> 190 ReturnType Reduce( 191 RAI first, 192 RAI last, 193 ReturnType neutral, 194 ReductionFunction reduction, 195 TransformationFunction transformation 196 ) { 197 return Reduce(first, last, neutral, reduction, transformation, 198 embb::mtapi::ExecutionPolicy(), 0); 199 } 200 201 /** 202 * Overload of above described Doxygen dummy with less arguments. 203 */ 204 template<typename RAI, typename ReturnType, typename ReductionFunction, 205 typename TransformationFunction> 206 ReturnType Reduce( 207 RAI first, 208 RAI last, 209 ReturnType neutral, 210 ReductionFunction reduction, 211 TransformationFunction transformation, 212 const embb::mtapi::ExecutionPolicy& policy 213 ) { 214 return Reduce(first, last, neutral, reduction, transformation, policy, 0); 215 } 216 217 #endif // else DOXYGEN 218 219 /** 220 * \} 221 */ 222 223 } // namespace algorithms 224 } // namespace embb 225 226 #include <embb/algorithms/internal/reduce-inl.h> 227 228 #endif // EMBB_ALGORITHMS_REDUCE_H_ 229