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
143 return static_cast<flag_task*>(t.
parent())->my_child_stolen;
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
Provides default splitting strategy for partition objects.
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
Join task node that contains shared flag for stealing feedback.
interface9::internal::old_auto_partition_type partition_type
tbb::internal::affinity_id * my_array
void note_affinity(task::affinity_id id)
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor()
void work_balance(StartType &start, Range &range)
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
unsigned short affinity_id
An id as used for specifying affinity.
Type enables transmission of splitting proportion from partitioners to range objects.
range_vector(const T &elem)
initialize via first range in pool
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
auto_partition_type(const auto_partitioner &)
linear_affinity_mode(linear_affinity_mode &src, const proportional_split &split_obj)
interface9::internal::static_partition_type::split_type split_type
proportional_mode(proportional_mode &src, const proportional_split &split_obj)
affinity_partitioner_base_v3()
Zeros the fields.
interface9::internal::affinity_partition_type::split_type split_type
interface9::internal::static_partition_type task_partition_type
proportional_split split_type
void set_affinity(affinity_id id)
Set affinity for this task.
proportional_split split_type
void note_affinity(task::affinity_id)
void const char const char int ITT_FORMAT __itt_group_sync p
Provides backward-compatible methods for partition objects without affinity.
void align_depth(depth_t base)
~affinity_partitioner_base_v3()
Deallocates my_array.
void note_affinity(task::affinity_id)
int current_thread_index()
Returns the index, aka slot number, of the calling thread in its current arena.
bool check_for_demand(task &t)
Enables one or the other code branches.
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
#define __TBB_RANGE_POOL_CAPACITY
bool is_divisible(depth_t max_depth)
Defines entry point for affinity partitioner into tbb run-time library.
old_auto_partition_type(const auto_partitioner &)
size_t do_split(adaptive_mode &src, 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 __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_id __itt_string_handle __itt_metadata_type type
Initial task to split the work.
proportional_mode(proportional_mode &src, split)
old_auto_partition_type(old_auto_partition_type &pt, split)
simple_partition_type(const simple_partitioner &)
void execute(StartType &start, Range &range)
simplified algorithm
Task type used in parallel_for.
static_partition_type(const static_partitioner &)
task * execute() __TBB_override
Should be overridden by derived classes.
adaptive_mode(adaptive_mode &src, split)
interface9::internal::simple_partition_type task_partition_type
void set_affinity(task &t)
Provides default linear indexing of partitioner's sequence.
Task type used to split the work of parallel_deterministic_reduce.
affinity_partition_type(affinity_partition_type &p, split)
Backward-compatible partition for auto and affinity partition objects.
affinity_id * my_array
Array that remembers affinities of tree positions to affinity_id.
interface9::internal::old_auto_partition_type partition_type
interface9::internal::auto_partition_type::split_type split_type
void set_affinity(task &)
#define __TBB_INITIAL_CHUNKS
static void mark_task_stolen(task &t)
bool check_being_stolen(task &)
affinity_partition_type(affinity_partition_type &p, const proportional_split &split_obj)
Base class for user-defined tasks.
static bool is_peer_stolen(task &t)
task * continue_after_execute_range()
size_t my_size
Number of elements in my_array.
interface9::internal::simple_partition_type::split_type split_type
tbb::aligned_space< T, MaxCapacity > my_pool
interface9::internal::affinity_partition_type task_partition_type
dynamic_grainsize_mode(dynamic_grainsize_mode &p, const proportional_split &split_obj)
Identifiers declared inside namespace internal should never be used directly by client code.
bool decide_whether_to_delay()
tbb::atomic< bool > my_child_stolen
auto_partition_type(auto_partition_type &src, split)
simple_partition_type(const simple_partition_type &, split)
bool should_execute_range(const task &t)
static const int not_initialized
static const unsigned factor
static proportional_split get_split(size_t n)
partition_type(const simple_partitioner &)
#define __TBB_EXPORTED_FUNC
Dummy type that distinguishes splitting constructor from copy constructor.
bool check_being_stolen(task &t)
partition_type(const partition_type &, split)
size_t do_split(proportional_mode &src, const proportional_split &split_obj)
affinity_partition_type(tbb::internal::affinity_partitioner_base_v3 &ap)
void split_to_fill(depth_t max_depth)
static size_t get_initial_partition_head()
bool is_stolen_task() const
True if task was stolen from the task pool of another thread.
static_partition_type(static_partition_type &p, split)
void __TBB_EXPORTED_METHOD resize(unsigned factor)
Resize my_array.
Provides proportional splitting strategy for partition objects.
#define __TBB_DEMAND_DEPTH_ADD
depth_t front_depth()
similarly to front(), returns depth of the first range in the pool
interface9::internal::old_auto_partition_type partition_type
#define __TBB_time_stamp()
internal::affinity_id affinity_id
An id as used for specifying affinity.
static_partition_type(static_partition_type &p, const proportional_split &split_obj)
proportional_split get_split()
void spawn_or_delay(bool, task &b)
void work_balance(StartType &start, Range &range)
#define __TBB_EXPORTED_METHOD
static proportional_split get_split(size_t)
A helper class to create a proportional_split object for a given type of Range.
int ref_count() const
The internal reference count.
linear_affinity_mode(linear_affinity_mode &src, split)
Range pool stores ranges of type T in a circular buffer with MaxCapacity.
bool check_for_demand(task &t)
void set_affinity(task &)
bool should_execute_range(const task &)
Base class for types that should not be copied or assigned.
dynamic_grainsize_mode(dynamic_grainsize_mode &p, split)
old_auto_partition_type(const affinity_partitioner &)
void align_depth(depth_t)
Task type used to split the work of parallel_reduce.
interface9::internal::auto_partition_type task_partition_type
void set_affinity(task &t)
void execute(StartType &start, Range &range)
bool check_for_demand(task &)
Copyright © 2005-2019 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.