Intel(R) Threading Building Blocks Doxygen Documentation
version 4.2.3
|
Go to the documentation of this file.
17 #ifndef __TBB_partitioner_H
18 #define __TBB_partitioner_H
20 #define __TBB_partitioner_H_include_area
23 #ifndef __TBB_INITIAL_CHUNKS
25 #define __TBB_INITIAL_CHUNKS 2
27 #ifndef __TBB_RANGE_POOL_CAPACITY
29 #define __TBB_RANGE_POOL_CAPACITY 8
31 #ifndef __TBB_INIT_DEPTH
33 #define __TBB_INIT_DEPTH 5
35 #ifndef __TBB_DEMAND_DEPTH_ADD
37 #define __TBB_DEMAND_DEPTH_ADD 1
39 #ifndef __TBB_STATIC_THRESHOLD
41 #define __TBB_STATIC_THRESHOLD 40000
44 #define __TBB_NONUNIFORM_TASK_CREATION 1
45 #ifdef __TBB_time_stamp
46 #define __TBB_USE_MACHINE_TIME_STAMPS 1
47 #define __TBB_task_duration() __TBB_STATIC_THRESHOLD
48 #endif // __TBB_machine_time_stamp
49 #endif // __TBB_DEFINE_MIC
57 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
59 #pragma warning (push)
60 #pragma warning (disable: 4244)
65 class auto_partitioner;
66 class simple_partitioner;
67 class static_partitioner;
68 class affinity_partitioner;
70 namespace interface9 {
72 class affinity_partition_type;
109 template<
typename Range,
typename Body,
typename Partitioner>
class start_scan;
114 namespace interface9 {
115 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
119 namespace interface9 {
123 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
124 template<
typename Range,
typename Body,
typename Partitioner>
class start_reduce;
125 template<
typename Range,
typename Body,
typename Partitioner>
class start_deterministic_reduce;
134 tbb::atomic<bool> &flag =
static_cast<flag_task*
>(t.
parent())->my_child_stolen;
135 #if TBB_USE_THREADING_TOOLS
137 flag.fetch_and_store<
release>(
true);
140 #endif //TBB_USE_THREADING_TOOLS
153 template <
typename T, depth_t MaxCapacity>
165 new(
static_cast<void *
>(my_pool.begin()) ) T(elem);
168 while( !empty() ) pop_back();
170 bool empty()
const {
return my_size == 0; }
175 while( my_size < MaxCapacity && is_divisible(max_depth) ) {
177 my_head = (my_head + 1) % MaxCapacity;
178 new(my_pool.begin()+my_head) T(my_pool.begin()[prev]);
179 my_pool.begin()[prev].~T();
180 new(my_pool.begin()+prev) T(my_pool.begin()[my_head],
split());
181 my_depth[my_head] = ++my_depth[prev];
186 __TBB_ASSERT(my_size > 0,
"range_vector::pop_back() with empty size");
187 my_pool.begin()[my_head].~T();
189 my_head = (my_head + MaxCapacity - 1) % MaxCapacity;
192 __TBB_ASSERT(my_size > 0,
"range_vector::pop_front() with empty size");
193 my_pool.begin()[my_tail].~T();
195 my_tail = (my_tail + 1) % MaxCapacity;
198 __TBB_ASSERT(my_size > 0,
"range_vector::back() with empty size");
199 return my_pool.begin()[my_head];
202 __TBB_ASSERT(my_size > 0,
"range_vector::front() with empty size");
203 return my_pool.begin()[my_tail];
207 __TBB_ASSERT(my_size > 0,
"range_vector::front_depth() with empty size");
208 return my_depth[my_tail];
211 __TBB_ASSERT(my_size > 0,
"range_vector::back_depth() with empty size");
212 return my_depth[my_head];
215 return back_depth() < max_depth && back().is_divisible();
220 template <
typename Partition>
232 Partition&
self() {
return *
static_cast<Partition*
>(
this); }
234 template<
typename StartType,
typename Range>
236 start.run_body( range );
239 template<
typename StartType,
typename Range>
240 void execute(StartType &start, Range &range) {
248 if ( range.is_divisible() ) {
249 if (
self().is_divisible() ) {
251 typename Partition::split_type split_obj =
self().
template get_split<Range>();
252 start.offer_work( split_obj );
253 }
while ( range.is_divisible() &&
self().is_divisible() );
256 self().work_balance(start, range);
261 template <
typename Partition>
269 static const unsigned factor = 1;
283 template <
typename Range,
typename =
void>
287 template <
typename Range>
290 #if __TBB_NONUNIFORM_TASK_CREATION
291 size_t right = (n + 2) / 3;
293 size_t right = n / 2;
295 size_t left = n - right;
301 template <
typename Partition>
310 #if __TBB_ENABLE_RANGE_FEEDBACK
311 size_t portion = size_t(
float(src.
my_divisor) *
float(split_obj.
right())
312 /
float(split_obj.
left() + split_obj.
right()) + 0.5f);
314 size_t portion = split_obj.
right() * my_partition::factor;
316 portion = (portion + my_partition::factor/2) & (0ul - my_partition::factor);
317 #if __TBB_ENABLE_RANGE_FEEDBACK
320 portion = my_partition::factor;
322 portion = src.
my_divisor - my_partition::factor;
328 return self().my_divisor > my_partition::factor;
330 template <
typename Range>
341 return size_t(current_index);
345 template <
typename Partition>
351 my_max_affinity(self().my_divisor) {}
353 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
355 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
357 if(
self().my_divisor )
366 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
377 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
384 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
388 , my_max_depth(
p.my_max_depth) {}
391 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
395 , my_max_depth(
p.my_max_depth) {}
397 if( !(
self().my_divisor / Mode::my_partition::factor) ) {
398 self().my_divisor = 1;
400 #if __TBB_USE_OPTIONAL_RTTI
408 if( !my_max_depth ) my_max_depth++;
418 my_max_depth -= base;
420 template<
typename StartType,
typename Range>
422 if( !range.is_divisible() || !
self().max_depth() ) {
423 start.run_body( range );
429 if(
self().check_for_demand( start ) ) {
430 if( range_pool.
size() > 1 ) {
438 start.run_body( range_pool.
back() );
440 }
while( !range_pool.
empty() && !start.is_cancelled() );
444 if( pass == my_delay ) {
445 if(
self().my_divisor > 1 )
447 else if(
self().my_divisor && my_max_depth ) {
448 self().my_divisor = 0;
455 }
else if(
begin == my_delay ) {
456 #ifndef __TBB_USE_MACHINE_TIME_STAMPS
461 }
else if( run == my_delay ) {
469 #endif // __TBB_USE_MACHINE_TIME_STAMPS
484 if( my_divisor > 1 )
return true;
485 if( my_divisor && my_max_depth ) {
505 template<
typename StartType,
typename Range>
506 void execute(StartType &start, Range &range) {
507 split_type split_obj =
split();
508 while( range.is_divisible() )
509 start.offer_work( split_obj );
510 start.run_body( range );
526 static const unsigned factor_power = 4;
529 static const unsigned factor = 1 << factor_power;
533 __TBB_ASSERT( (factor&(factor-1))==0,
"factor must be power of two" );
536 my_max_depth = factor_power + 1;
541 , my_array(
p.my_array) {}
544 , my_array(
p.my_array) {}
547 if( !my_array[my_head] )
556 my_array[my_head] =
id;
563 static const size_t VICTIM_CHUNKS = 4;
567 num_chunks = VICTIM_CHUNKS;
568 return num_chunks==1;
606 typedef interface9::internal::simple_partition_type::split_type
split_type;
628 typedef interface9::internal::auto_partition_type::split_type
split_type;
671 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
672 #pragma warning (pop)
673 #endif // warning 4244 is back
674 #undef __TBB_INITIAL_CHUNKS
675 #undef __TBB_RANGE_POOL_CAPACITY
676 #undef __TBB_INIT_DEPTH
679 #undef __TBB_partitioner_H_include_area
Task type used to split the work of parallel_reduce.
proportional_mode(proportional_mode &src, const proportional_split &split_obj)
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
void set_affinity(task &)
bool is_divisible(depth_t max_depth)
static_partition_type(static_partition_type &p, split)
void split_to_fill(depth_t max_depth)
internal::affinity_id affinity_id
An id as used for specifying affinity.
affinity_partition_type(affinity_partition_type &p, split)
interface9::internal::static_partition_type task_partition_type
size_t do_split(adaptive_mode &src, split)
bool check_for_demand(task &t)
Join task node that contains shared flag for stealing feedback.
void work_balance(StartType &start, Range &range)
static bool is_peer_stolen(task &t)
Enables one or the other code branches.
Provides default linear indexing of partitioner's sequence.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Task type used to split the work of parallel_deterministic_reduce.
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id id
old_auto_partition_type(const auto_partitioner &)
int ref_count() const
The internal reference count.
interface9::internal::old_auto_partition_type partition_type
A helper class to create a proportional_split object for a given type of Range.
bool check_for_demand(task &t)
Task type used in parallel_for.
size_t my_size
Number of elements in my_array.
interface9::internal::auto_partition_type task_partition_type
static proportional_split get_split(size_t n)
Base class for user-defined tasks.
Provides backward-compatible methods for partition objects without affinity.
bool decide_whether_to_delay()
old_auto_partition_type(old_auto_partition_type &pt, split)
Backward-compatible partition for auto and affinity partition objects.
void set_affinity(task &)
partition_type(const partition_type &, split)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
void work_balance(StartType &start, Range &range)
#define __TBB_RANGE_POOL_CAPACITY
bool should_execute_range(const task &t)
simple_partition_type(const simple_partition_type &, split)
range_vector(const T &elem)
initialize via first range in pool
bool check_being_stolen(task &t)
Dummy type that distinguishes splitting constructor from copy constructor.
interface9::internal::affinity_partition_type::split_type split_type
interface9::internal::simple_partition_type::split_type split_type
void note_affinity(task::affinity_id id)
affinity_partition_type(affinity_partition_type &p, const proportional_split &split_obj)
dynamic_grainsize_mode(dynamic_grainsize_mode &p, split)
proportional_split split_type
affinity_partitioner_base_v3()
Zeros the fields.
depth_t front_depth()
similarly to front(), returns depth of the first range in the pool
static_partition_type(static_partition_type &p, const proportional_split &split_obj)
interface9::internal::static_partition_type::split_type split_type
void set_affinity(task &t)
void execute(StartType &start, Range &range)
simplified algorithm
static const unsigned factor
interface9::internal::auto_partition_type::split_type split_type
proportional_split get_split()
void spawn_or_delay(bool, task &b)
interface9::internal::simple_partition_type task_partition_type
tbb::aligned_space< T, MaxCapacity > my_pool
void note_affinity(task::affinity_id)
task * continue_after_execute_range()
unsigned short affinity_id
An id as used for specifying affinity.
adaptive_mode(adaptive_mode &src, split)
~affinity_partitioner_base_v3()
Deallocates my_array.
interface9::internal::old_auto_partition_type partition_type
void execute(StartType &start, Range &range)
#define __TBB_INITIAL_CHUNKS
size_t do_split(proportional_mode &src, const proportional_split &split_obj)
int current_thread_index()
Returns the index, aka slot number, of the calling thread in its current arena.
linear_affinity_mode(linear_affinity_mode &src, split)
tbb::atomic< bool > my_child_stolen
static_partition_type(const static_partitioner &)
void align_depth(depth_t)
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor()
Base class for types that should not be copied or assigned.
simple_partition_type(const simple_partitioner &)
Initial task to split the work.
tbb::internal::affinity_id * my_array
dynamic_grainsize_mode(dynamic_grainsize_mode &p, const proportional_split &split_obj)
affinity_id * my_array
Array that remembers affinities of tree positions to affinity_id.
#define __TBB_EXPORTED_FUNC
bool check_being_stolen(task &)
void __TBB_EXPORTED_METHOD resize(unsigned factor)
Resize my_array.
Provides proportional splitting strategy for partition objects.
Provides default splitting strategy for partition objects.
static void mark_task_stolen(task &t)
interface9::internal::old_auto_partition_type partition_type
void set_affinity(affinity_id id)
Set affinity for this task.
task * execute() __TBB_override
Should be overridden by derived classes.
bool is_stolen_task() const
True if task was stolen from the task pool of another thread.
void note_affinity(task::affinity_id)
Type enables transmission of splitting proportion from partitioners to range objects.
interface9::internal::affinity_partition_type task_partition_type
auto_partition_type(const auto_partitioner &)
#define __TBB_DEMAND_DEPTH_ADD
Range pool stores ranges of type T in a circular buffer with MaxCapacity.
old_auto_partition_type(const affinity_partitioner &)
bool should_execute_range(const task &)
Defines entry point for affinity partitioner into tbb run-time library.
#define __TBB_time_stamp()
bool check_for_demand(task &)
linear_affinity_mode(linear_affinity_mode &src, const proportional_split &split_obj)
partition_type(const simple_partitioner &)
static proportional_split get_split(size_t)
Identifiers declared inside namespace internal should never be used directly by client code.
affinity_partition_type(tbb::internal::affinity_partitioner_base_v3 &ap)
void const char const char int ITT_FORMAT __itt_group_sync p
void align_depth(depth_t base)
#define __TBB_EXPORTED_METHOD
proportional_mode(proportional_mode &src, split)
auto_partition_type(auto_partition_type &src, split)
static const int not_initialized
void set_affinity(task &t)
proportional_split split_type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
static size_t get_initial_partition_head()
Copyright © 2005-2020 Intel Corporation. All Rights Reserved.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are
registered trademarks or trademarks of Intel Corporation or its
subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.