1 /*
2     Copyright (c) 2020-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 #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 
24 #include "oneapi/tbb/parallel_scan.h"
25 
26 #include <vector>
27 
28 //! \file conformance_parallel_scan.cpp
29 //! \brief Test for [algorithms.parallel_scan] specification
30 
31 constexpr std::size_t size = 1000;
32 
33 template<typename T, typename Op>
34 class Body {
35     const T identity;
36     T sum;
37     std::vector<T>& y;
38     const std::vector<T>& z;
39 public:
40     Body( const std::vector<T>& z_, std::vector<T>& y_, T id ) : identity(id), sum(id), y(y_), z(z_) {}
41     T get_sum() const { return sum; }
42 
43     template<typename Tag>
44     void operator()( const oneapi::tbb::blocked_range<std::size_t>& r, Tag ) {
45         T temp = sum;
46         for(std::size_t i=r.begin(); i<r.end(); ++i ) {
47             temp = Op()(temp, z[i]);
48             if( Tag::is_final_scan() )
49                 y[i] = temp;
50         }
51         sum = temp;
52     }
53     Body( Body& b, oneapi::tbb::split ): identity(b.identity), sum(b.identity), y(b.y), z(b.z) {}
54     void reverse_join( Body& a ) { sum = Op()(a.sum, sum); }
55     void assign( Body& b ) { sum = b.sum; }
56 };
57 
58 class default_partitioner_tag{};
59 
60 template<typename Partitioner>
61 struct parallel_scan_wrapper{
62     template<typename... Args>
63     void operator()(Args&&... args) {
64     oneapi::tbb::parallel_scan(std::forward<Args>(args)..., Partitioner());
65     }
66 };
67 
68 template<>
69 struct parallel_scan_wrapper<default_partitioner_tag>{
70     template<typename... Args>
71     void operator()(Args&&... args) {
72     oneapi::tbb::parallel_scan(std::forward<Args>(args)...);
73     }
74 };
75 
76 // Test scan tag
77 //! \brief \ref interface
78 TEST_CASE("scan tags testing") {
79     CHECK(oneapi::tbb::pre_scan_tag::is_final_scan()==false);
80     CHECK(oneapi::tbb::final_scan_tag::is_final_scan()==true);
81     CHECK((bool)oneapi::tbb::pre_scan_tag()==false);
82     CHECK((bool)oneapi::tbb::final_scan_tag()==true);
83 }
84 
85 //! Test parallel prefix sum calculation for body-based interface
86 //! \brief \ref requirement \ref interface
87 TEST_CASE_TEMPLATE("Test parallel scan with body", Partitioner, default_partitioner_tag, oneapi::tbb::simple_partitioner, oneapi::tbb::auto_partitioner) {
88     std::vector<int> input(size);
89     std::vector<int> output(size);
90     std::vector<int> control(size);
91 
92     for(size_t i = 0; i < size; ++i) {
93         input[i] = int(i / 2);
94         if(i)
95             control[i] = control[i-1] + input[i];
96         else
97             control[i] = input[i];
98     }
99     Body<int, std::plus<int>> body(input, output, 0);
100     parallel_scan_wrapper<Partitioner>()(oneapi::tbb::blocked_range<std::size_t>(0U, size, 1U), body);
101     CHECK((control == output));
102 }
103 
104 
105 //! Test parallel prefix sum calculation for scan-based interface
106 //! \brief \ref requirement \ref interface
107 TEST_CASE_TEMPLATE("Test parallel scan with body", Partitioner, default_partitioner_tag, oneapi::tbb::simple_partitioner, oneapi::tbb::auto_partitioner) {
108     std::vector<std::size_t> input(size);
109     std::vector<std::size_t> output(size);
110     std::vector<std::size_t> control(size);
111 
112     for (std::size_t i = 0; i<size; ++i) {
113         input[i] = i;
114         if (i)
115             control[i] = control[i-1]+input[i];
116         else
117             control[i] = input[i];
118     }
119     parallel_scan_wrapper<Partitioner>()(oneapi::tbb::blocked_range<std::size_t>(0U, size, 1U), std::size_t(0),
120         [&](const oneapi::tbb::blocked_range<std::size_t>& r, std::size_t sum, bool is_final) -> std::size_t
121         {
122             std::size_t temp = sum;
123             for (std::size_t i = r.begin(); i<r.end(); ++i) {
124                 temp = temp + input[i];
125                 if (is_final)
126                     output[i] = temp;
127             }
128             return temp;
129         },
130         [](std::size_t a, std::size_t b) -> std::size_t
131         {
132             return a + b;
133         });
134 
135     CHECK((control==output));
136 }
137