1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 #include <atomic> 18 19 #include "common/parallel_reduce_common.h" 20 #include "common/cpu_usertime.h" 21 #include "common/exception_handling.h" 22 #include "common/concepts_common.h" 23 24 //! \file test_parallel_reduce.cpp 25 //! \brief Test for [algorithms.parallel_reduce algorithms.parallel_deterministic_reduce] specification 26 27 #if _MSC_VER 28 #pragma warning (push) 29 // Suppress conditional expression is constant 30 #pragma warning (disable: 4127) 31 #endif //#if _MSC_VER 32 33 using ValueType = uint64_t; 34 35 struct Sum { 36 template<typename T> 37 T operator() ( const T& v1, const T& v2 ) const { 38 return v1 + v2; 39 } 40 }; 41 42 struct Accumulator { 43 ValueType operator() ( const tbb::blocked_range<ValueType*>& r, ValueType value ) const { 44 for ( ValueType* pv = r.begin(); pv != r.end(); ++pv ) 45 value += *pv; 46 return value; 47 } 48 }; 49 50 class ParallelSumTester { 51 public: 52 ParallelSumTester( const ParallelSumTester& ) = default; 53 void operator=( const ParallelSumTester& ) = delete; 54 55 ParallelSumTester() : m_range(nullptr, nullptr) { 56 m_array = new ValueType[unsigned(count)]; 57 for ( ValueType i = 0; i < count; ++i ) 58 m_array[i] = i + 1; 59 m_range = tbb::blocked_range<ValueType*>( m_array, m_array + count ); 60 } 61 ~ParallelSumTester() { delete[] m_array; } 62 63 template<typename Partitioner> 64 void CheckParallelReduce() { 65 Partitioner partitioner; 66 ValueType result1 = reduce_invoker<ValueType>( m_range, Accumulator(), Sum(), partitioner ); 67 REQUIRE_MESSAGE( result1 == expected, "Wrong parallel summation result" ); 68 ValueType result2 = reduce_invoker<ValueType>( m_range, 69 [](const tbb::blocked_range<ValueType*>& r, ValueType value) -> ValueType { 70 for ( const ValueType* pv = r.begin(); pv != r.end(); ++pv ) 71 value += *pv; 72 return value; 73 }, 74 Sum(), 75 partitioner 76 ); 77 REQUIRE_MESSAGE( result2 == expected, "Wrong parallel summation result" ); 78 } 79 private: 80 ValueType* m_array; 81 tbb::blocked_range<ValueType*> m_range; 82 static const ValueType count, expected; 83 }; 84 85 const ValueType ParallelSumTester::count = 1000000; 86 const ValueType ParallelSumTester::expected = count * (count + 1) / 2; 87 88 namespace test_cancellation { 89 90 struct ReduceToCancel { 91 std::size_t operator()( const tbb::blocked_range<std::size_t>&, std::size_t ) const { 92 ++g_CurExecuted; 93 Cancellator::WaitUntilReady(); 94 return 1; 95 } 96 }; // struct ReduceToCancel 97 98 struct JoinToCancel { 99 std::size_t operator()( std::size_t, std::size_t ) const { 100 ++g_CurExecuted; 101 Cancellator::WaitUntilReady(); 102 return 1; 103 } 104 }; // struct Join 105 106 struct ReduceFunctorToCancel { 107 std::size_t result; 108 109 ReduceFunctorToCancel() : result(0) {} 110 ReduceFunctorToCancel( ReduceFunctorToCancel&, tbb::split ) : result(0) {} 111 112 void operator()( const tbb::blocked_range<std::size_t>& br ) { 113 result = ReduceToCancel{}(br, result); 114 } 115 116 void join( ReduceFunctorToCancel& rhs ) { 117 result = JoinToCancel{}(result, rhs.result); 118 } 119 }; // struct ReduceFunctorToCancel 120 121 static constexpr std::size_t buffer_test_size = 1024; 122 static constexpr std::size_t maxParallelReduceRunnerMode = 9; 123 124 template <std::size_t Mode> 125 class ParallelReduceRunner { 126 tbb::task_group_context& my_ctx; 127 128 static_assert(Mode >= 0 && Mode <= maxParallelReduceRunnerMode, "Incorrect mode for ParallelReduceTask"); 129 130 template <typename... Args> 131 void run_parallel_reduce( Args&&... args ) const { 132 switch(Mode % 5) { 133 case 0 : { 134 tbb::parallel_reduce(std::forward<Args>(args)..., my_ctx); 135 break; 136 } 137 case 1 : { 138 tbb::parallel_reduce(std::forward<Args>(args)..., tbb::simple_partitioner{}, my_ctx); 139 break; 140 } 141 case 2 : { 142 tbb::parallel_reduce(std::forward<Args>(args)..., tbb::auto_partitioner{}, my_ctx); 143 break; 144 } 145 case 3 : { 146 tbb::parallel_reduce(std::forward<Args>(args)..., tbb::static_partitioner{}, my_ctx); 147 break; 148 } 149 case 4 : { 150 tbb::affinity_partitioner aff; 151 tbb::parallel_reduce(std::forward<Args>(args)..., aff, my_ctx); 152 break; 153 } 154 } 155 } 156 157 public: 158 ParallelReduceRunner( tbb::task_group_context& ctx ) 159 : my_ctx(ctx) {} 160 161 void operator()() const { 162 tbb::blocked_range<std::size_t> br(0, buffer_test_size); 163 if (Mode < 5) { 164 ReduceFunctorToCancel functor; 165 run_parallel_reduce(br, functor); 166 } else { 167 run_parallel_reduce(br, std::size_t(0), ReduceToCancel{}, JoinToCancel{}); 168 } 169 } 170 }; // class ParallelReduceRunner 171 172 static constexpr std::size_t maxParallelDeterministicReduceRunnerMode = 5; 173 174 // TODO: unify with ParallelReduceRunner 175 template <std::size_t Mode> 176 class ParallelDeterministicReduceRunner { 177 tbb::task_group_context& my_ctx; 178 179 static_assert(Mode >= 0 && Mode <= maxParallelDeterministicReduceRunnerMode, "Incorrect Mode for deterministic_reduce task"); 180 181 template <typename... Args> 182 void run_parallel_deterministic_reduce( Args&&... args ) const { 183 switch(Mode % 3) { 184 case 0 : { 185 tbb::parallel_deterministic_reduce(std::forward<Args>(args)..., my_ctx); 186 break; 187 } 188 case 1 : { 189 tbb::parallel_deterministic_reduce(std::forward<Args>(args)..., tbb::simple_partitioner{}, my_ctx); 190 break; 191 } 192 case 2 : { 193 tbb::parallel_deterministic_reduce(std::forward<Args>(args)..., tbb::static_partitioner{}, my_ctx); 194 break; 195 } 196 } 197 } 198 199 public: 200 ParallelDeterministicReduceRunner( tbb::task_group_context& ctx ) 201 : my_ctx(ctx) {} 202 203 void operator()() const { 204 tbb::blocked_range<std::size_t> br(0, buffer_test_size); 205 if (Mode < 3) { 206 ReduceFunctorToCancel functor; 207 run_parallel_deterministic_reduce(br, functor); 208 } else { 209 run_parallel_deterministic_reduce(br, std::size_t(0), ReduceToCancel{}, JoinToCancel{}); 210 } 211 } 212 }; // class ParallelDeterministicReduceRunner 213 214 template <std::size_t Mode> 215 void run_parallel_reduce_cancellation_test() { 216 for ( auto concurrency_level : utils::concurrency_range() ) { 217 if (concurrency_level < 2) continue; 218 219 tbb::global_control gc(tbb::global_control::max_allowed_parallelism, concurrency_level); 220 ResetEhGlobals(); 221 RunCancellationTest<ParallelReduceRunner<Mode>, Cancellator>(); 222 } 223 } 224 225 template <std::size_t Mode> 226 void run_parallel_deterministic_reduce_cancellation_test() { 227 for ( auto concurrency_level : utils::concurrency_range() ) { 228 if (concurrency_level < 2) continue; 229 230 tbb::global_control gc(tbb::global_control::max_allowed_parallelism, concurrency_level); 231 ResetEhGlobals(); 232 RunCancellationTest<ParallelDeterministicReduceRunner<Mode>, Cancellator>(); 233 } 234 } 235 236 template <std::size_t Mode> 237 struct ParallelReduceTestRunner { 238 static void run() { 239 run_parallel_reduce_cancellation_test<Mode>(); 240 ParallelReduceTestRunner<Mode + 1>::run(); 241 } 242 }; // struct ParallelReduceTestRunner 243 244 template <> 245 struct ParallelReduceTestRunner<maxParallelReduceRunnerMode> { 246 static void run() { 247 run_parallel_reduce_cancellation_test<maxParallelReduceRunnerMode>(); 248 } 249 }; // struct ParallelReduceTestRunner<maxParallelReduceRunnerMode> 250 251 template <std::size_t Mode> 252 struct ParallelDeterministicReduceTestRunner { 253 static void run() { 254 run_parallel_deterministic_reduce_cancellation_test<Mode>(); 255 ParallelDeterministicReduceTestRunner<Mode + 1>::run(); 256 } 257 }; // struct ParallelDeterministicReduceTestRunner 258 259 template <> 260 struct ParallelDeterministicReduceTestRunner<maxParallelDeterministicReduceRunnerMode> { 261 static void run() { 262 run_parallel_deterministic_reduce_cancellation_test<maxParallelDeterministicReduceRunnerMode>(); 263 } 264 }; // struct ParallelDeterministicReduceTestRunner<maxParallelDeterministicReduceRunnerMode> 265 266 } // namespace test_cancellation 267 268 #if __TBB_CPP20_CONCEPTS_PRESENT 269 template <typename... Args> 270 concept can_call_parallel_reduce_basic = requires( Args&&... args ) { 271 tbb::parallel_reduce(std::forward<Args>(args)...); 272 }; 273 274 template <typename... Args> 275 concept can_call_parallel_deterministic_reduce_basic = requires ( Args&&... args ) { 276 tbb::parallel_deterministic_reduce(std::forward<Args>(args)...); 277 }; 278 279 template <typename... Args> 280 concept can_call_preduce_helper = can_call_parallel_reduce_basic<Args...> && 281 can_call_parallel_reduce_basic<Args..., tbb::task_group_context&>; 282 283 template <typename... Args> 284 concept can_call_pdet_reduce_helper = can_call_parallel_deterministic_reduce_basic<Args...> && 285 can_call_parallel_deterministic_reduce_basic<Args..., tbb::task_group_context&>; 286 287 template <typename... Args> 288 concept can_call_preduce_with_partitioner = can_call_preduce_helper<Args...> && 289 can_call_preduce_helper<Args..., const tbb::simple_partitioner&> && 290 can_call_preduce_helper<Args..., const tbb::auto_partitioner&> && 291 can_call_preduce_helper<Args..., const tbb::static_partitioner&> && 292 can_call_preduce_helper<Args..., tbb::affinity_partitioner&>; 293 294 template <typename... Args> 295 concept can_call_pdet_reduce_with_partitioner = can_call_pdet_reduce_helper<Args...> && 296 can_call_pdet_reduce_helper<Args..., const tbb::simple_partitioner&> && 297 can_call_pdet_reduce_helper<Args..., const tbb::static_partitioner&>; 298 299 template <typename Range, typename Body> 300 concept can_call_imperative_preduce = can_call_preduce_with_partitioner<const Range&, Body&>; 301 302 template <typename Range, typename Body> 303 concept can_call_imperative_pdet_reduce = can_call_pdet_reduce_with_partitioner<const Range&, Body&>; 304 305 template <typename Range, typename Value, typename RealBody, typename Reduction> 306 concept can_call_functional_preduce = can_call_preduce_with_partitioner<const Range&, const Value&, 307 const RealBody&, const Reduction&>; 308 309 template <typename Range, typename Value, typename RealBody, typename Reduction> 310 concept can_call_functional_pdet_reduce = can_call_pdet_reduce_with_partitioner<const Range&, const Value&, 311 const RealBody&, const Reduction&>; 312 313 template <typename Range> 314 using CorrectBody = test_concepts::parallel_reduce_body::Correct<Range>; 315 316 template <typename Range> 317 using CorrectFunc = test_concepts::parallel_reduce_function::Correct<Range>; 318 319 using CorrectReduction = test_concepts::parallel_reduce_combine::Correct<int>; 320 using CorrectRange = test_concepts::range::Correct; 321 322 void test_preduce_range_constraints() { 323 using namespace test_concepts::range; 324 static_assert(can_call_imperative_preduce<Correct, CorrectBody<Correct>>); 325 static_assert(!can_call_imperative_preduce<NonCopyable, CorrectBody<NonCopyable>>); 326 static_assert(!can_call_imperative_preduce<NonDestructible, CorrectBody<NonDestructible>>); 327 static_assert(!can_call_imperative_preduce<NonSplittable, CorrectBody<NonSplittable>>); 328 static_assert(!can_call_imperative_preduce<NoEmpty, CorrectBody<NoEmpty>>); 329 static_assert(!can_call_imperative_preduce<EmptyNonConst, CorrectBody<EmptyNonConst>>); 330 static_assert(!can_call_imperative_preduce<WrongReturnEmpty, CorrectBody<WrongReturnEmpty>>); 331 static_assert(!can_call_imperative_preduce<NoIsDivisible, CorrectBody<NoIsDivisible>>); 332 static_assert(!can_call_imperative_preduce<IsDivisibleNonConst, CorrectBody<NoIsDivisible>>); 333 static_assert(!can_call_imperative_preduce<WrongReturnIsDivisible, CorrectBody<WrongReturnIsDivisible>>); 334 335 static_assert(can_call_functional_preduce<Correct, int, CorrectFunc<Correct>, CorrectReduction>); 336 static_assert(!can_call_functional_preduce<NonCopyable, int, CorrectFunc<NonCopyable>, CorrectReduction>); 337 static_assert(!can_call_functional_preduce<NonDestructible, int, CorrectFunc<NonDestructible>, CorrectReduction>); 338 static_assert(!can_call_functional_preduce<NonSplittable, int, CorrectFunc<NonSplittable>, CorrectReduction>); 339 static_assert(!can_call_functional_preduce<NoEmpty, int, CorrectFunc<NoEmpty>, CorrectReduction>); 340 static_assert(!can_call_functional_preduce<EmptyNonConst, int, CorrectFunc<EmptyNonConst>, CorrectReduction>); 341 static_assert(!can_call_functional_preduce<WrongReturnEmpty, int, CorrectFunc<WrongReturnEmpty>, CorrectReduction>); 342 static_assert(!can_call_functional_preduce<NoIsDivisible, int, CorrectFunc<NoIsDivisible>, CorrectReduction>); 343 static_assert(!can_call_functional_preduce<IsDivisibleNonConst, int, CorrectFunc<IsDivisibleNonConst>, CorrectReduction>); 344 static_assert(!can_call_functional_preduce<WrongReturnIsDivisible, int, CorrectFunc<WrongReturnIsDivisible>, CorrectReduction>); 345 } 346 347 void test_preduce_body_constraints() { 348 using namespace test_concepts::parallel_reduce_body; 349 static_assert(can_call_imperative_preduce<CorrectRange, Correct<CorrectRange>>); 350 static_assert(!can_call_imperative_preduce<CorrectRange, NonSplittable<CorrectRange>>); 351 static_assert(!can_call_imperative_preduce<CorrectRange, NonDestructible<CorrectRange>>); 352 static_assert(!can_call_imperative_preduce<CorrectRange, NoOperatorRoundBrackets<CorrectRange>>); 353 static_assert(!can_call_imperative_preduce<CorrectRange, WrongInputOperatorRoundBrackets<CorrectRange>>); 354 static_assert(!can_call_imperative_preduce<CorrectRange, NoJoin<CorrectRange>>); 355 static_assert(!can_call_imperative_preduce<CorrectRange, WrongInputJoin<CorrectRange>>); 356 } 357 358 void test_preduce_func_constraints() { 359 using namespace test_concepts::parallel_reduce_function; 360 static_assert(can_call_functional_preduce<CorrectRange, int, Correct<CorrectRange>, CorrectReduction>); 361 static_assert(!can_call_functional_preduce<CorrectRange, int, NoOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 362 static_assert(!can_call_functional_preduce<CorrectRange, int, OperatorRoundBracketsNonConst<CorrectRange>, CorrectReduction>); 363 static_assert(!can_call_functional_preduce<CorrectRange, int, WrongFirstInputOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 364 static_assert(!can_call_functional_preduce<CorrectRange, int, WrongSecondInputOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 365 static_assert(!can_call_functional_preduce<CorrectRange, int, WrongReturnOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 366 } 367 368 void test_preduce_combine_constraints() { 369 using namespace test_concepts::parallel_reduce_combine; 370 static_assert(can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, Correct<int>>); 371 static_assert(!can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, NoOperatorRoundBrackets<int>>); 372 static_assert(!can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, OperatorRoundBracketsNonConst<int>>); 373 static_assert(!can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongFirstInputOperatorRoundBrackets<int>>); 374 static_assert(!can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongSecondInputOperatorRoundBrackets<int>>); 375 static_assert(!can_call_functional_preduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongReturnOperatorRoundBrackets<int>>); 376 } 377 378 void test_pdet_reduce_range_constraints() { 379 using namespace test_concepts::range; 380 static_assert(can_call_imperative_pdet_reduce<Correct, CorrectBody<Correct>>); 381 static_assert(!can_call_imperative_pdet_reduce<NonCopyable, CorrectBody<NonCopyable>>); 382 static_assert(!can_call_imperative_pdet_reduce<NonDestructible, CorrectBody<NonDestructible>>); 383 static_assert(!can_call_imperative_pdet_reduce<NonSplittable, CorrectBody<NonSplittable>>); 384 static_assert(!can_call_imperative_pdet_reduce<NoEmpty, CorrectBody<NoEmpty>>); 385 static_assert(!can_call_imperative_pdet_reduce<EmptyNonConst, CorrectBody<EmptyNonConst>>); 386 static_assert(!can_call_imperative_pdet_reduce<WrongReturnEmpty, CorrectBody<WrongReturnEmpty>>); 387 static_assert(!can_call_imperative_pdet_reduce<NoIsDivisible, CorrectBody<NoIsDivisible>>); 388 static_assert(!can_call_imperative_pdet_reduce<IsDivisibleNonConst, CorrectBody<NoIsDivisible>>); 389 static_assert(!can_call_imperative_pdet_reduce<WrongReturnIsDivisible, CorrectBody<WrongReturnIsDivisible>>); 390 391 static_assert(can_call_functional_pdet_reduce<Correct, int, CorrectFunc<Correct>, CorrectReduction>); 392 static_assert(!can_call_functional_pdet_reduce<NonCopyable, int, CorrectFunc<NonCopyable>, CorrectReduction>); 393 static_assert(!can_call_functional_pdet_reduce<NonDestructible, int, CorrectFunc<NonDestructible>, CorrectReduction>); 394 static_assert(!can_call_functional_pdet_reduce<NonSplittable, int, CorrectFunc<NonSplittable>, CorrectReduction>); 395 static_assert(!can_call_functional_pdet_reduce<NoEmpty, int, CorrectFunc<NoEmpty>, CorrectReduction>); 396 static_assert(!can_call_functional_pdet_reduce<EmptyNonConst, int, CorrectFunc<EmptyNonConst>, CorrectReduction>); 397 static_assert(!can_call_functional_pdet_reduce<WrongReturnEmpty, int, CorrectFunc<WrongReturnEmpty>, CorrectReduction>); 398 static_assert(!can_call_functional_pdet_reduce<NoIsDivisible, int, CorrectFunc<NoIsDivisible>, CorrectReduction>); 399 static_assert(!can_call_functional_pdet_reduce<IsDivisibleNonConst, int, CorrectFunc<IsDivisibleNonConst>, CorrectReduction>); 400 static_assert(!can_call_functional_pdet_reduce<WrongReturnIsDivisible, int, CorrectFunc<WrongReturnIsDivisible>, CorrectReduction>); 401 } 402 403 void test_pdet_reduce_body_constraints() { 404 using namespace test_concepts::parallel_reduce_body; 405 static_assert(can_call_imperative_pdet_reduce<CorrectRange, Correct<CorrectRange>>); 406 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, NonSplittable<CorrectRange>>); 407 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, NonDestructible<CorrectRange>>); 408 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, NoOperatorRoundBrackets<CorrectRange>>); 409 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, WrongInputOperatorRoundBrackets<CorrectRange>>); 410 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, NoJoin<CorrectRange>>); 411 static_assert(!can_call_imperative_pdet_reduce<CorrectRange, WrongInputJoin<CorrectRange>>); 412 } 413 414 void test_pdet_reduce_func_constraints() { 415 using namespace test_concepts::parallel_reduce_function; 416 static_assert(can_call_functional_pdet_reduce<CorrectRange, int, Correct<CorrectRange>, CorrectReduction>); 417 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, NoOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 418 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, OperatorRoundBracketsNonConst<CorrectRange>, CorrectReduction>); 419 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, WrongFirstInputOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 420 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, WrongSecondInputOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 421 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, WrongReturnOperatorRoundBrackets<CorrectRange>, CorrectReduction>); 422 } 423 424 void test_pdet_reduce_combine_constraints() { 425 using namespace test_concepts::parallel_reduce_combine; 426 static_assert(can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, Correct<int>>); 427 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, NoOperatorRoundBrackets<int>>); 428 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, OperatorRoundBracketsNonConst<int>>); 429 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongFirstInputOperatorRoundBrackets<int>>); 430 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongSecondInputOperatorRoundBrackets<int>>); 431 static_assert(!can_call_functional_pdet_reduce<CorrectRange, int, CorrectFunc<CorrectRange>, WrongReturnOperatorRoundBrackets<int>>); 432 } 433 #endif // __TBB_CPP20_CONCEPTS_PRESENT 434 435 //! Test parallel summation correctness 436 //! \brief \ref stress 437 TEST_CASE("Test parallel summation correctness") { 438 ParallelSumTester pst; 439 pst.CheckParallelReduce<utils_default_partitioner>(); 440 pst.CheckParallelReduce<tbb::simple_partitioner>(); 441 pst.CheckParallelReduce<tbb::auto_partitioner>(); 442 pst.CheckParallelReduce<tbb::affinity_partitioner>(); 443 pst.CheckParallelReduce<tbb::static_partitioner>(); 444 } 445 446 static std::atomic<long> ForkCount; 447 static std::atomic<long> FooBodyCount; 448 449 //! Class with public interface that is exactly minimal requirements for Range concept 450 class MinimalRange { 451 size_t begin, end; 452 friend class FooBody; 453 explicit MinimalRange( size_t i ) : begin(0), end(i) {} 454 template <typename Partitioner_> friend void TestSplitting( std::size_t nthread ); 455 public: 456 MinimalRange( MinimalRange& r, tbb::split ) : end(r.end) { 457 begin = r.end = (r.begin+r.end)/2; 458 } 459 bool is_divisible() const {return end-begin>=2;} 460 bool empty() const {return begin==end;} 461 }; 462 463 //! Class with public interface that is exactly minimal requirements for Body of a parallel_reduce 464 class FooBody { 465 private: 466 FooBody( const FooBody& ); // Deny access 467 void operator=( const FooBody& ); // Deny access 468 template <typename Partitioner_> friend void TestSplitting( std::size_t nthread ); 469 //! Parent that created this body via split operation. NULL if original body. 470 FooBody* parent; 471 //! Total number of index values processed by body and its children. 472 size_t sum; 473 //! Range that has been processed so far by this body and its children. 474 size_t begin, end; 475 //! True if body has not yet been processed at least once by operator(). 476 bool is_new; 477 //! 1 if body was created by split; 0 if original body. 478 int forked; 479 FooBody() {++FooBodyCount;} 480 public: 481 ~FooBody() { 482 forked = 0xDEADBEEF; 483 sum=0xDEADBEEF; 484 --FooBodyCount; 485 } 486 FooBody( FooBody& other, tbb::split ) { 487 ++FooBodyCount; 488 ++ForkCount; 489 sum = 0; 490 parent = &other; 491 is_new = true; 492 forked = 1; 493 } 494 495 void init() { 496 sum = 0; 497 parent = nullptr; 498 is_new = true; 499 forked = 0; 500 begin = ~size_t(0); 501 end = ~size_t(0); 502 } 503 504 void join( FooBody& s ) { 505 REQUIRE( s.forked==1 ); 506 REQUIRE( this!=&s ); 507 REQUIRE( this==s.parent ); 508 REQUIRE( end==s.begin ); 509 end = s.end; 510 sum += s.sum; 511 s.forked = 2; 512 } 513 void operator()( const MinimalRange& r ) { 514 for( size_t k=r.begin; k<r.end; ++k ) 515 ++sum; 516 if( is_new ) { 517 is_new = false; 518 begin = r.begin; 519 } else 520 REQUIRE( end==r.begin ); 521 end = r.end; 522 } 523 }; 524 525 template<typename Partitioner> 526 void TestSplitting( std::size_t nthread ) { 527 ForkCount = 0; 528 Partitioner partitioner; 529 for( size_t i=0; i<=1000; ++i ) { 530 FooBody f; 531 f.init(); 532 REQUIRE_MESSAGE( FooBodyCount==1, "Wrong initial BodyCount value" ); 533 reduce_invoker(MinimalRange(i), f, partitioner); 534 535 if (nthread == 1) REQUIRE_MESSAGE(ForkCount==0, "Body was split during 1 thread execution"); 536 537 REQUIRE_MESSAGE( FooBodyCount==1, "Some copies of FooBody was not removed after reduction"); 538 REQUIRE_MESSAGE( f.sum==i, "Incorrect reduction" ); 539 REQUIRE_MESSAGE( f.begin==(i==0 ? ~size_t(0) : 0), "Incorrect range borders" ); 540 REQUIRE_MESSAGE( f.end==(i==0 ? ~size_t(0) : i), "Incorrect range borders" ); 541 } 542 } 543 544 //! Test splitting range and body during reduction, test that all workers sleep when no work 545 //! \brief \ref resource_usage \ref error_guessing 546 TEST_CASE("Test splitting range and body during reduction, test that all workers sleep when no work") { 547 for ( auto concurrency_level : utils::concurrency_range() ) { 548 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 549 550 TestSplitting<tbb::simple_partitioner>(concurrency_level); 551 TestSplitting<tbb::static_partitioner>(concurrency_level); 552 TestSplitting<tbb::auto_partitioner>(concurrency_level); 553 TestSplitting<tbb::affinity_partitioner>(concurrency_level); 554 TestSplitting<utils_default_partitioner>(concurrency_level); 555 556 // Test that all workers sleep when no work 557 TestCPUUserTime(concurrency_level); 558 } 559 } 560 561 //! Define overloads of parallel_deterministic_reduce that accept "undesired" types of partitioners 562 namespace unsupported { 563 template<typename Range, typename Body> 564 void parallel_deterministic_reduce(const Range&, Body&, const tbb::auto_partitioner&) { } 565 template<typename Range, typename Body> 566 void parallel_deterministic_reduce(const Range&, Body&, tbb::affinity_partitioner&) { } 567 568 template<typename Range, typename Value, typename RealBody, typename Reduction> 569 Value parallel_deterministic_reduce(const Range& , const Value& identity, const RealBody& , const Reduction& , const tbb::auto_partitioner&) { 570 return identity; 571 } 572 template<typename Range, typename Value, typename RealBody, typename Reduction> 573 Value parallel_deterministic_reduce(const Range& , const Value& identity, const RealBody& , const Reduction& , tbb::affinity_partitioner&) { 574 return identity; 575 } 576 } 577 578 struct Body { 579 float value; 580 Body() : value(0) {} 581 Body(Body&, tbb::split) { value = 0; } 582 void operator()(const tbb::blocked_range<int>&) {} 583 void join(Body&) {} 584 }; 585 586 //! Check that other types of partitioners are not supported (auto, affinity) 587 //! In the case of "unsupported" API unexpectedly sneaking into namespace tbb, 588 //! this test should result in a compilation error due to overload resolution ambiguity 589 //! \brief \ref negative \ref error_guessing 590 TEST_CASE("Test Unsupported Partitioners") { 591 using namespace tbb; 592 using namespace unsupported; 593 Body body; 594 parallel_deterministic_reduce(blocked_range<int>(0, 10), body, tbb::auto_partitioner()); 595 596 tbb::affinity_partitioner ap; 597 parallel_deterministic_reduce(blocked_range<int>(0, 10), body, ap); 598 599 parallel_deterministic_reduce( 600 blocked_range<int>(0, 10), 601 0, 602 [](const blocked_range<int>&, int init)->int { 603 return init; 604 }, 605 [](int x, int y)->int { 606 return x + y; 607 }, 608 tbb::auto_partitioner() 609 ); 610 parallel_deterministic_reduce( 611 blocked_range<int>(0, 10), 612 0, 613 [](const blocked_range<int>&, int init)->int { 614 return init; 615 }, 616 [](int x, int y)->int { 617 return x + y; 618 }, 619 ap 620 ); 621 } 622 623 //! Testing tbb::parallel_reduce with tbb::task_group_context 624 //! \brief \ref interface \ref error_guessing 625 TEST_CASE("cancellation test for tbb::parallel_reduce") { 626 test_cancellation::ParallelReduceTestRunner</*First mode = */0>::run(); 627 } 628 629 //! Testing tbb::parallel_deterministic_reduce with tbb::task_group_context 630 //! \brief \ref interface \ref error_guessing 631 TEST_CASE("cancellation test for tbb::parallel_deterministic_reduce") { 632 test_cancellation::ParallelDeterministicReduceTestRunner</*First mode = */0>::run(); 633 } 634 635 #if __TBB_CPP20_CONCEPTS_PRESENT 636 //! \brief \ref error_guessing 637 TEST_CASE("parallel_reduce constraints") { 638 test_preduce_range_constraints(); 639 test_preduce_body_constraints(); 640 test_preduce_func_constraints(); 641 test_preduce_combine_constraints(); 642 } 643 644 //! \brief \ref error_guessing 645 TEST_CASE("parallel_deterministic_reduce constraints") { 646 test_pdet_reduce_range_constraints(); 647 test_pdet_reduce_body_constraints(); 648 test_pdet_reduce_func_constraints(); 649 test_pdet_reduce_combine_constraints(); 650 } 651 #endif 652 653 #if _MSC_VER 654 #pragma warning (pop) 655 #endif 656