oneapi/tbb/blocked_nd_range.h

0001 /*
0002     Copyright (c) 2017-2025 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_blocked_nd_range_H
0018 #define __TBB_blocked_nd_range_H
0019
0020 #include <algorithm>    // std::any_of
0021 #include <array>
0022 #include <cstddef>
0023 #include <type_traits>  // std::is_same, std::enable_if
0024
0025 #include "detail/_config.h"
0026 #include "detail/_template_helpers.h" // index_sequence, make_index_sequence
0027 #include "detail/_namespace_injection.h"
0028 #include "detail/_range_common.h"
0029
0030 #include "blocked_range.h"
0031
0032 namespace tbb {
0033 namespace detail {
0034 namespace d1 {
0035
0036 /*
0037     The blocked_nd_range_impl uses make_index_sequence<N> to automatically generate a ctor with
0038     exactly N arguments of the type tbb::blocked_range<Value>. Such ctor provides an opportunity
0039     to use braced-init-list parameters to initialize each dimension.
0040     Use of parameters, whose representation is a braced-init-list, but they're not
0041     std::initializer_list or a reference to one, produces a non-deduced context
0042     within template argument deduction.
0043
0044     NOTE: blocked_nd_range must be exactly a templated alias to the blocked_nd_range_impl
0045     (and not e.g. a derived class), otherwise it would need to declare its own ctor
0046     facing the same problem that the impl class solves.
0047 */
0048
0049 template<typename Value, unsigned int N, typename = detail::make_index_sequence<N>>
0050 class blocked_nd_range_impl;
0051
0052 template<typename Value, unsigned int N, std::size_t... Is>
0053 class blocked_nd_range_impl<Value, N, detail::index_sequence<Is...>> {
0054 public:
0055     //! Type of a value.
0056     using value_type = Value;
0057
0058     //! Type of a dimension range.
0059     using dim_range_type = tbb::blocked_range<value_type>;
0060
0061     //! Type for the size of a range.
0062     using size_type = typename dim_range_type::size_type;
0063
0064     blocked_nd_range_impl() = delete;
0065
0066     //! Constructs N-dimensional range over N half-open intervals each represented as tbb::blocked_range<Value>.
0067     blocked_nd_range_impl(const indexed_t<dim_range_type, Is>&... args) : my_dims{ {args...} } {}
0068
0069 #if __clang__ && __TBB_CLANG_VERSION < 140000
0070     // On clang prior to version 14.0.0, passing a single braced init list to the constructor of blocked_nd_range<T, 1>
0071     // matches better on the C array constructor and generates compile-time error because of unexpected size
0072     // Adding constraints for this constructor to force the compiler to drop it from overload resolution if the size is unexpected
0073     template <unsigned int M, typename = typename std::enable_if<M == N>::type>
0074     blocked_nd_range_impl(const value_type (&size)[M], size_type grainsize = 1) :
0075 #else
0076     blocked_nd_range_impl(const value_type (&size)[N], size_type grainsize = 1) :
0077 #endif
0078         my_dims { dim_range_type(0, size[Is], grainsize)... } {}
0079
0080     //! Dimensionality of a range.
0081     static constexpr unsigned int dim_count() { return N; }
0082
0083     //! Range in certain dimension.
0084     const dim_range_type& dim(unsigned int dimension) const {
0085         __TBB_ASSERT(dimension < N, "out of bound");
0086         return my_dims[dimension];
0087     }
0088
0089     //------------------------------------------------------------------------
0090     // Methods that implement Range concept
0091     //------------------------------------------------------------------------
0092
0093     //! True if at least one dimension is empty.
0094     bool empty() const {
0095         return std::any_of(my_dims.begin(), my_dims.end(), [](const dim_range_type& d) {
0096             return d.empty();
0097         });
0098     }
0099
0100     //! True if at least one dimension is divisible.
0101     bool is_divisible() const {
0102         return std::any_of(my_dims.begin(), my_dims.end(), [](const dim_range_type& d) {
0103             return d.is_divisible();
0104         });
0105     }
0106
0107     blocked_nd_range_impl(blocked_nd_range_impl& r, proportional_split proportion) : my_dims(r.my_dims) {
0108         do_split(r, proportion);
0109     }
0110
0111     blocked_nd_range_impl(blocked_nd_range_impl& r, split proportion) : my_dims(r.my_dims) {
0112         do_split(r, proportion);
0113     }
0114
0115 private:
0116     static_assert(N != 0, "zero dimensional blocked_nd_range can't be constructed");
0117
0118     //! Ranges in each dimension.
0119     std::array<dim_range_type, N> my_dims;
0120
0121     template<typename split_type>
0122     void do_split(blocked_nd_range_impl& r, split_type proportion) {
0123         static_assert((std::is_same<split_type, split>::value || std::is_same<split_type, proportional_split>::value),
0124                       "type of split object is incorrect");
0125         __TBB_ASSERT(r.is_divisible(), "can't split not divisible range");
0126
0127         auto my_it = std::max_element(my_dims.begin(), my_dims.end(), [](const dim_range_type& first, const dim_range_type& second) {
0128             return (first.size() * double(second.grainsize()) < second.size() * double(first.grainsize()));
0129         });
0130
0131         auto r_it = r.my_dims.begin() + (my_it - my_dims.begin());
0132
0133         my_it->my_begin = dim_range_type::do_split(*r_it, proportion);
0134
0135         // (!(my_it->my_begin < r_it->my_end) && !(r_it->my_end < my_it->my_begin)) equals to
0136         // (my_it->my_begin == r_it->my_end), but we can't use operator== due to Value concept
0137         __TBB_ASSERT(!(my_it->my_begin < r_it->my_end) && !(r_it->my_end < my_it->my_begin),
0138                      "blocked_range has been split incorrectly");
0139     }
0140 };
0141
0142 template<typename Value, unsigned int N>
0143          __TBB_requires(blocked_range_value<Value>)
0144 class blocked_nd_range : public blocked_nd_range_impl<Value, N> {
0145     using base = blocked_nd_range_impl<Value, N>;
0146     // Making constructors of base class visible
0147     using base::base;
0148 };
0149
0150 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT && __TBB_PREVIEW_BLOCKED_ND_RANGE_DEDUCTION_GUIDES
0151 // blocked_nd_range(const dim_range_type& dim0, const dim_range_type& dim1, ...)
0152 // while the arguments are passed as braced-init-lists
0153 // Works only for 2 and more arguments since the deduction from
0154 // single braced-init-list or single C-array argument prefers the multi-dimensional range
0155 // Only braced-init-lists of size 2 and 3 are allowed since dim_range_type may only
0156 // be constructed from 2 or 3 arguments
0157 template <typename Value, unsigned int... Ns,
0158           typename = std::enable_if_t<sizeof...(Ns) >= 2>,
0159           typename = std::enable_if_t<(... && (Ns == 2 || Ns == 3))>>
0160 blocked_nd_range(const Value (&... dim)[Ns])
0161 -> blocked_nd_range<Value, sizeof...(Ns)>;
0162
0163 // blocked_nd_range(const dim_range_type& dim0, const dim_range_type& dim1, ...)
0164 // while the arguments are passed as blocked_range objects of the same type
0165 template <typename Value, typename... Values,
0166           typename = std::enable_if_t<(... && std::is_same_v<Value, Values>)>>
0167 blocked_nd_range(blocked_range<Value>, blocked_range<Values>...)
0168 -> blocked_nd_range<Value, 1 + sizeof...(Values)>;
0169
0170 // blocked_nd_range(const value_type (&size)[N], size_type grainsize = 1)
0171 template <typename Value, unsigned int N>
0172 blocked_nd_range(const Value (&)[N], typename blocked_nd_range<Value, N>::size_type = 1)
0173 -> blocked_nd_range<Value, N>;
0174
0175 // blocked_nd_range(blocked_nd_range<Value, N>&, oneapi::tbb::split)
0176 template <typename Value, unsigned int N>
0177 blocked_nd_range(blocked_nd_range<Value, N>, oneapi::tbb::split)
0178 -> blocked_nd_range<Value, N>;
0179
0180 // blocked_nd_range(blocked_nd_range<Value, N>&, oneapi::tbb::proportional_split)
0181 template <typename Value, unsigned int N>
0182 blocked_nd_range(blocked_nd_range<Value, N>, oneapi::tbb::proportional_split)
0183 -> blocked_nd_range<Value, N>;
0184
0185 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT && __TBB_PREVIEW_BLOCKED_ND_RANGE_DEDUCTION_GUIDES
0186
0187 } // namespace d1
0188 } // namespace detail
0189
0190 inline namespace v1 {
0191 using detail::d1::blocked_nd_range;
0192 } // namespace v1
0193 } // namespace tbb
0194
0195 #endif /* __TBB_blocked_nd_range_H */