1 /* 2 Copyright (c) 2020-2023 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 #if __INTEL_COMPILER && _MSC_VER 18 #pragma warning(disable : 2586) // decorated name length exceeded, name was truncated 19 #endif 20 21 #define DOCTEST_CONFIG_SUPER_FAST_ASSERTS 22 #include "common/test.h" 23 #include "common/test_invoke.h" 24 25 #include "oneapi/tbb/parallel_scan.h" 26 27 #include <vector> 28 29 //! \file conformance_parallel_scan.cpp 30 //! \brief Test for [algorithms.parallel_scan] specification 31 32 constexpr std::size_t size = 1000; 33 34 template<typename T, typename Op> 35 class Body { 36 const T identity; 37 T sum; 38 std::vector<T>& y; 39 const std::vector<T>& z; 40 public: 41 Body( const std::vector<T>& z_, std::vector<T>& y_, T id ) : identity(id), sum(id), y(y_), z(z_) {} 42 T get_sum() const { return sum; } 43 44 template<typename Tag> 45 void operator()( const oneapi::tbb::blocked_range<std::size_t>& r, Tag ) { 46 T temp = sum; 47 for(std::size_t i=r.begin(); i<r.end(); ++i ) { 48 temp = Op()(temp, z[i]); 49 if( Tag::is_final_scan() ) 50 y[i] = temp; 51 } 52 sum = temp; 53 } 54 Body( Body& b, oneapi::tbb::split ): identity(b.identity), sum(b.identity), y(b.y), z(b.z) {} 55 void reverse_join( Body& a ) { sum = Op()(a.sum, sum); } 56 void assign( Body& b ) { sum = b.sum; } 57 }; 58 59 class default_partitioner_tag{}; 60 61 template<typename Partitioner> 62 struct parallel_scan_wrapper{ 63 template<typename... Args> 64 void operator()(Args&&... args) { 65 oneapi::tbb::parallel_scan(std::forward<Args>(args)..., Partitioner()); 66 } 67 }; 68 69 template<> 70 struct parallel_scan_wrapper<default_partitioner_tag>{ 71 template<typename... Args> 72 void operator()(Args&&... args) { 73 oneapi::tbb::parallel_scan(std::forward<Args>(args)...); 74 } 75 }; 76 77 // Test scan tag 78 //! \brief \ref interface 79 TEST_CASE("scan tags testing") { 80 CHECK(oneapi::tbb::pre_scan_tag::is_final_scan()==false); 81 CHECK(oneapi::tbb::final_scan_tag::is_final_scan()==true); 82 CHECK((bool)oneapi::tbb::pre_scan_tag()==false); 83 CHECK((bool)oneapi::tbb::final_scan_tag()==true); 84 } 85 86 //! Test parallel prefix sum calculation for body-based interface 87 //! \brief \ref requirement \ref interface 88 TEST_CASE_TEMPLATE("Test parallel scan with body", Partitioner, default_partitioner_tag, oneapi::tbb::simple_partitioner, oneapi::tbb::auto_partitioner) { 89 std::vector<int> input(size); 90 std::vector<int> output(size); 91 std::vector<int> control(size); 92 93 for(size_t i = 0; i < size; ++i) { 94 input[i] = int(i / 2); 95 if(i) 96 control[i] = control[i-1] + input[i]; 97 else 98 control[i] = input[i]; 99 } 100 Body<int, std::plus<int>> body(input, output, 0); 101 parallel_scan_wrapper<Partitioner>()(oneapi::tbb::blocked_range<std::size_t>(0U, size, 1U), body); 102 CHECK((control == output)); 103 } 104 105 106 //! Test parallel prefix sum calculation for scan-based interface 107 //! \brief \ref requirement \ref interface 108 TEST_CASE_TEMPLATE("Test parallel scan with body", Partitioner, default_partitioner_tag, oneapi::tbb::simple_partitioner, oneapi::tbb::auto_partitioner) { 109 std::vector<std::size_t> input(size); 110 std::vector<std::size_t> output(size); 111 std::vector<std::size_t> control(size); 112 113 for (std::size_t i = 0; i<size; ++i) { 114 input[i] = i; 115 if (i) 116 control[i] = control[i-1]+input[i]; 117 else 118 control[i] = input[i]; 119 } 120 parallel_scan_wrapper<Partitioner>()(oneapi::tbb::blocked_range<std::size_t>(0U, size, 1U), std::size_t(0), 121 [&](const oneapi::tbb::blocked_range<std::size_t>& r, std::size_t sum, bool is_final) -> std::size_t 122 { 123 std::size_t temp = sum; 124 for (std::size_t i = r.begin(); i<r.end(); ++i) { 125 temp = temp + input[i]; 126 if (is_final) 127 output[i] = temp; 128 } 129 return temp; 130 }, 131 [](std::size_t a, std::size_t b) -> std::size_t 132 { 133 return a + b; 134 }); 135 136 CHECK((control==output)); 137 } 138 139 #if __TBB_CPP17_INVOKE_PRESENT 140 template <typename... Args> 141 void test_pscan_invoke(const std::vector<std::size_t>& desired_vector, 142 std::vector<std::size_t>& result_vector, 143 Args&&... args) { 144 auto result = oneapi::tbb::parallel_scan(std::forward<Args>(args)...); 145 CHECK(desired_vector == result_vector); 146 CHECK(result.get() == result_vector.back()); 147 148 for (std::size_t& item : result_vector) item = 0; 149 } 150 151 //! Test that parallel_scan uses std::invoke to run the body 152 //! \brief \ref requirement 153 TEST_CASE("parallel_scan and std::invoke") { 154 const std::size_t iterations = 1000000; 155 std::vector<std::size_t> desired_vector(iterations); 156 157 for (std::size_t i = 1; i < iterations; ++i) { 158 desired_vector[i] = desired_vector[i - 1] + i; 159 } 160 161 std::vector<std::size_t> change_vector(iterations, 0); 162 test_invoke::SmartRange<test_invoke::SmartValue> range(0, iterations, change_vector); 163 test_invoke::SmartValue identity(0); 164 165 auto scan = &test_invoke::SmartRange<test_invoke::SmartValue>::scan; 166 auto combine = &test_invoke::SmartValue::operator+; 167 168 test_pscan_invoke(desired_vector, change_vector, range, identity, scan, combine); 169 test_pscan_invoke(desired_vector, change_vector, range, identity, scan, combine, oneapi::tbb::auto_partitioner()); 170 test_pscan_invoke(desired_vector, change_vector, range, identity, scan, combine, oneapi::tbb::simple_partitioner()); 171 } 172 173 #endif // __TBB_CPP17_INVOKE_PRESENT 174