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