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 //! Number of join operations done so far on this body and its children. 474 long join_count; 475 //! Range that has been processed so far by this body and its children. 476 size_t begin, end; 477 //! True if body has not yet been processed at least once by operator(). 478 bool is_new; 479 //! 1 if body was created by split; 0 if original body. 480 int forked; 481 FooBody() {++FooBodyCount;} 482 public: 483 ~FooBody() { 484 forked = 0xDEADBEEF; 485 sum=0xDEADBEEF; 486 join_count=0xDEADBEEF; 487 --FooBodyCount; 488 } 489 FooBody( FooBody& other, tbb::split ) { 490 ++FooBodyCount; 491 ++ForkCount; 492 sum = 0; 493 parent = &other; 494 join_count = 0; 495 is_new = true; 496 forked = 1; 497 } 498 499 void init() { 500 sum = 0; 501 parent = nullptr; 502 join_count = 0; 503 is_new = true; 504 forked = 0; 505 begin = ~size_t(0); 506 end = ~size_t(0); 507 } 508 509 void join( FooBody& s ) { 510 REQUIRE( s.forked==1 ); 511 REQUIRE( this!=&s ); 512 REQUIRE( this==s.parent ); 513 REQUIRE( end==s.begin ); 514 end = s.end; 515 sum += s.sum; 516 join_count += s.join_count + 1; 517 s.forked = 2; 518 } 519 void operator()( const MinimalRange& r ) { 520 for( size_t k=r.begin; k<r.end; ++k ) 521 ++sum; 522 if( is_new ) { 523 is_new = false; 524 begin = r.begin; 525 } else 526 REQUIRE( end==r.begin ); 527 end = r.end; 528 } 529 }; 530 531 template<typename Partitioner> 532 void TestSplitting( std::size_t nthread ) { 533 ForkCount = 0; 534 long join_count = 0; 535 Partitioner partitioner; 536 for( size_t i=0; i<=1000; ++i ) { 537 FooBody f; 538 f.init(); 539 REQUIRE_MESSAGE( FooBodyCount==1, "Wrong initial BodyCount value" ); 540 reduce_invoker(MinimalRange(i), f, partitioner); 541 542 if (nthread == 1) REQUIRE_MESSAGE(ForkCount==0, "Body was split during 1 thread execution"); 543 544 join_count += f.join_count; 545 REQUIRE_MESSAGE( FooBodyCount==1, "Some copies of FooBody was not removed after reduction"); 546 REQUIRE_MESSAGE( f.sum==i, "Incorrect reduction" ); 547 REQUIRE_MESSAGE( f.begin==(i==0 ? ~size_t(0) : 0), "Incorrect range borders" ); 548 REQUIRE_MESSAGE( f.end==(i==0 ? ~size_t(0) : i), "Incorrect range borders" ); 549 } 550 } 551 552 //! Test splitting range and body during reduction, test that all workers sleep when no work 553 //! \brief \ref resource_usage \ref error_guessing 554 TEST_CASE("Test splitting range and body during reduction, test that all workers sleep when no work") { 555 for ( auto concurrency_level : utils::concurrency_range() ) { 556 tbb::global_control control(tbb::global_control::max_allowed_parallelism, concurrency_level); 557 558 TestSplitting<tbb::simple_partitioner>(concurrency_level); 559 TestSplitting<tbb::static_partitioner>(concurrency_level); 560 TestSplitting<tbb::auto_partitioner>(concurrency_level); 561 TestSplitting<tbb::affinity_partitioner>(concurrency_level); 562 TestSplitting<utils_default_partitioner>(concurrency_level); 563 564 // Test that all workers sleep when no work 565 TestCPUUserTime(concurrency_level); 566 } 567 } 568 569 //! Define overloads of parallel_deterministic_reduce that accept "undesired" types of partitioners 570 namespace unsupported { 571 template<typename Range, typename Body> 572 void parallel_deterministic_reduce(const Range&, Body&, const tbb::auto_partitioner&) { } 573 template<typename Range, typename Body> 574 void parallel_deterministic_reduce(const Range&, Body&, tbb::affinity_partitioner&) { } 575 576 template<typename Range, typename Value, typename RealBody, typename Reduction> 577 Value parallel_deterministic_reduce(const Range& , const Value& identity, const RealBody& , const Reduction& , const tbb::auto_partitioner&) { 578 return identity; 579 } 580 template<typename Range, typename Value, typename RealBody, typename Reduction> 581 Value parallel_deterministic_reduce(const Range& , const Value& identity, const RealBody& , const Reduction& , tbb::affinity_partitioner&) { 582 return identity; 583 } 584 } 585 586 struct Body { 587 float value; 588 Body() : value(0) {} 589 Body(Body&, tbb::split) { value = 0; } 590 void operator()(const tbb::blocked_range<int>&) {} 591 void join(Body&) {} 592 }; 593 594 //! Check that other types of partitioners are not supported (auto, affinity) 595 //! In the case of "unsupported" API unexpectedly sneaking into namespace tbb, 596 //! this test should result in a compilation error due to overload resolution ambiguity 597 //! \brief \ref negative \ref error_guessing 598 TEST_CASE("Test Unsupported Partitioners") { 599 using namespace tbb; 600 using namespace unsupported; 601 Body body; 602 parallel_deterministic_reduce(blocked_range<int>(0, 10), body, tbb::auto_partitioner()); 603 604 tbb::affinity_partitioner ap; 605 parallel_deterministic_reduce(blocked_range<int>(0, 10), body, ap); 606 607 parallel_deterministic_reduce( 608 blocked_range<int>(0, 10), 609 0, 610 [](const blocked_range<int>&, int init)->int { 611 return init; 612 }, 613 [](int x, int y)->int { 614 return x + y; 615 }, 616 tbb::auto_partitioner() 617 ); 618 parallel_deterministic_reduce( 619 blocked_range<int>(0, 10), 620 0, 621 [](const blocked_range<int>&, int init)->int { 622 return init; 623 }, 624 [](int x, int y)->int { 625 return x + y; 626 }, 627 ap 628 ); 629 } 630 631 //! Testing tbb::parallel_reduce with tbb::task_group_context 632 //! \brief \ref interface \ref error_guessing 633 TEST_CASE("cancellation test for tbb::parallel_reduce") { 634 test_cancellation::ParallelReduceTestRunner</*First mode = */0>::run(); 635 } 636 637 //! Testing tbb::parallel_deterministic_reduce with tbb::task_group_context 638 //! \brief \ref interface \ref error_guessing 639 TEST_CASE("cancellation test for tbb::parallel_deterministic_reduce") { 640 test_cancellation::ParallelDeterministicReduceTestRunner</*First mode = */0>::run(); 641 } 642 643 #if __TBB_CPP20_CONCEPTS_PRESENT 644 //! \brief \ref error_guessing 645 TEST_CASE("parallel_reduce constraints") { 646 test_preduce_range_constraints(); 647 test_preduce_body_constraints(); 648 test_preduce_func_constraints(); 649 test_preduce_combine_constraints(); 650 } 651 652 //! \brief \ref error_guessing 653 TEST_CASE("parallel_deterministic_reduce constraints") { 654 test_pdet_reduce_range_constraints(); 655 test_pdet_reduce_body_constraints(); 656 test_pdet_reduce_func_constraints(); 657 test_pdet_reduce_combine_constraints(); 658 } 659 #endif 660 661 #if _MSC_VER 662 #pragma warning (pop) 663 #endif 664