21 #ifndef __TBB_partitioner_H 22 #define __TBB_partitioner_H 24 #ifndef __TBB_INITIAL_CHUNKS 26 #define __TBB_INITIAL_CHUNKS 2 28 #ifndef __TBB_RANGE_POOL_CAPACITY 30 #define __TBB_RANGE_POOL_CAPACITY 8 32 #ifndef __TBB_INIT_DEPTH 34 #define __TBB_INIT_DEPTH 5 36 #ifndef __TBB_DEMAND_DEPTH_ADD 38 #define __TBB_DEMAND_DEPTH_ADD 1 40 #ifndef __TBB_STATIC_THRESHOLD 42 #define __TBB_STATIC_THRESHOLD 40000 45 #define __TBB_NONUNIFORM_TASK_CREATION 1 46 #ifdef __TBB_time_stamp 47 #define __TBB_USE_MACHINE_TIME_STAMPS 1 48 #define __TBB_task_duration() __TBB_STATIC_THRESHOLD 49 #endif // __TBB_machine_time_stamp 50 #endif // __TBB_DEFINE_MIC 58 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) 60 #pragma warning (push) 61 #pragma warning (disable: 4244) 66 class auto_partitioner;
67 class simple_partitioner;
68 class static_partitioner;
69 class affinity_partitioner;
71 namespace interface9 {
73 class affinity_partition_type;
110 template<
typename Range,
typename Body,
typename Partitioner>
class start_scan;
115 namespace interface9 {
116 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
120 namespace interface9 {
124 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
125 template<
typename Range,
typename Body,
typename Partitioner>
class start_reduce;
126 template<
typename Range,
typename Body,
typename Partitioner>
class start_deterministic_reduce;
136 #if TBB_USE_THREADING_TOOLS 141 #endif //TBB_USE_THREADING_TOOLS 144 return static_cast<flag_task*>(t.
parent())->my_child_stolen;
154 template <
typename T, depth_t MaxCapacity>
166 new( static_cast<void *>(my_pool.
begin()) ) T(elem);
169 while( !empty() ) pop_back();
171 bool empty()
const {
return my_size == 0; }
176 while( my_size < MaxCapacity && is_divisible(max_depth) ) {
178 my_head = (my_head + 1) % MaxCapacity;
179 new(my_pool.
begin()+my_head) T(my_pool.
begin()[prev]);
180 my_pool.
begin()[prev].~T();
182 my_depth[my_head] = ++my_depth[prev];
187 __TBB_ASSERT(my_size > 0,
"range_vector::pop_back() with empty size");
188 my_pool.
begin()[my_head].~T();
190 my_head = (my_head + MaxCapacity - 1) % MaxCapacity;
193 __TBB_ASSERT(my_size > 0,
"range_vector::pop_front() with empty size");
194 my_pool.
begin()[my_tail].~T();
196 my_tail = (my_tail + 1) % MaxCapacity;
199 __TBB_ASSERT(my_size > 0,
"range_vector::back() with empty size");
200 return my_pool.
begin()[my_head];
203 __TBB_ASSERT(my_size > 0,
"range_vector::front() with empty size");
204 return my_pool.
begin()[my_tail];
208 __TBB_ASSERT(my_size > 0,
"range_vector::front_depth() with empty size");
209 return my_depth[my_tail];
212 __TBB_ASSERT(my_size > 0,
"range_vector::back_depth() with empty size");
213 return my_depth[my_head];
216 return back_depth() < max_depth && back().is_divisible();
221 template <
typename Partition>
233 Partition&
self() {
return *static_cast<Partition*>(
this); }
235 template<
typename StartType,
typename Range>
237 start.run_body( range );
240 template<
typename StartType,
typename Range>
241 void execute(StartType &start, Range &range) {
249 if ( range.is_divisible() ) {
250 if (
self().is_divisible() ) {
252 typename Partition::split_type split_obj =
self().
template get_split<Range>();
253 start.offer_work( split_obj );
254 }
while ( range.is_divisible() &&
self().is_divisible() );
257 self().work_balance(start, range);
262 template <
typename Partition>
270 static const unsigned factor = 1;
284 template <
typename Range,
typename =
void>
288 template <
typename Range>
291 #if __TBB_NONUNIFORM_TASK_CREATION 292 size_t right = (n + 2) / 3;
294 size_t right = n / 2;
296 size_t left = n - right;
302 template <
typename Partition>
311 #if __TBB_ENABLE_RANGE_FEEDBACK 312 size_t portion = size_t(
float(src.
my_divisor) *
float(split_obj.
right())
313 /
float(split_obj.
left() + split_obj.
right()) + 0.5f);
315 size_t portion = split_obj.
right() * my_partition::factor;
317 portion = (portion + my_partition::factor/2) & (0ul - my_partition::factor);
318 #if __TBB_ENABLE_RANGE_FEEDBACK 321 portion = my_partition::factor;
323 portion = src.
my_divisor - my_partition::factor;
329 return self().my_divisor > my_partition::factor;
331 template <
typename Range>
342 return size_t(current_index);
346 template <
typename Partition>
352 my_max_affinity(self().my_divisor) {}
354 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
356 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
358 if(
self().my_divisor )
367 #ifdef __TBB_USE_MACHINE_TIME_STAMPS 378 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
385 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
389 , my_max_depth(
p.my_max_depth) {}
392 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
396 , my_max_depth(
p.my_max_depth) {}
398 if( !(
self().my_divisor / Mode::my_partition::factor) ) {
399 self().my_divisor = 1;
401 #if __TBB_USE_OPTIONAL_RTTI 409 if( !my_max_depth ) my_max_depth++;
419 my_max_depth -= base;
421 template<
typename StartType,
typename Range>
423 if( !range.is_divisible() || !
self().max_depth() ) {
424 start.run_body( range );
427 internal::range_vector<Range, range_pool_size> range_pool(range);
429 range_pool.split_to_fill(
self().max_depth());
430 if(
self().check_for_demand( start ) ) {
431 if( range_pool.size() > 1 ) {
432 start.offer_work( range_pool.front(), range_pool.front_depth() );
433 range_pool.pop_front();
436 if( range_pool.is_divisible(
self().max_depth()) )
439 start.run_body( range_pool.back() );
440 range_pool.pop_back();
441 }
while( !range_pool.empty() && !start.is_cancelled() );
445 if( pass == my_delay ) {
446 if(
self().my_divisor > 1 )
448 else if(
self().my_divisor && my_max_depth ) {
449 self().my_divisor = 0;
456 }
else if(
begin == my_delay ) {
457 #ifndef __TBB_USE_MACHINE_TIME_STAMPS 462 }
else if( run == my_delay ) {
470 #endif // __TBB_USE_MACHINE_TIME_STAMPS 485 if( my_divisor > 1 )
return true;
486 if( my_divisor && my_max_depth ) {
506 template<
typename StartType,
typename Range>
507 void execute(StartType &start, Range &range) {
508 split_type split_obj =
split();
509 while( range.is_divisible() )
510 start.offer_work( split_obj );
511 start.run_body( range );
527 static const unsigned factor_power = 4;
530 static const unsigned factor = 1 << factor_power;
534 __TBB_ASSERT( (factor&(factor-1))==0,
"factor must be power of two" );
537 my_max_depth = factor_power + 1;
542 , my_array(
p.my_array) {}
545 , my_array(
p.my_array) {}
548 if( !my_array[my_head] )
557 my_array[my_head] =
id;
564 static const size_t VICTIM_CHUNKS = 4;
568 num_chunks = VICTIM_CHUNKS;
569 return num_chunks==1;
595 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
607 typedef interface9::internal::simple_partition_type::split_type
split_type;
622 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
629 typedef interface9::internal::auto_partition_type::split_type
split_type;
641 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
660 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
672 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) 673 #pragma warning (pop) 674 #endif // warning 4244 is back 675 #undef __TBB_INITIAL_CHUNKS 676 #undef __TBB_RANGE_POOL_CAPACITY 677 #undef __TBB_INIT_DEPTH #define __TBB_time_stamp()
old_auto_partition_type(const auto_partitioner &)
~affinity_partitioner_base_v3()
Deallocates my_array.
Type enables transmission of splitting proportion from partitioners to range objects.
void align_depth(depth_t)
affinity_partitioner_base_v3()
Zeros the fields.
bool should_execute_range(const task &)
bool check_for_demand(task &t)
unsigned short affinity_id
An id as used for specifying affinity.
task * execute() __TBB_override
Should be overridden by derived classes.
interface9::internal::static_partition_type::split_type split_type
dynamic_grainsize_mode(dynamic_grainsize_mode &p, 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 id
T * begin() const
Pointer to beginning of array.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
static proportional_split get_split(size_t)
proportional_split split_type
depth_t front_depth()
similarly to front(), returns depth of the first range in the pool
Provides backward-compatible methods for partition objects without affinity.
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
interface9::internal::old_auto_partition_type partition_type
void split_to_fill(depth_t max_depth)
bool check_for_demand(task &)
void spawn_or_delay(bool, task &b)
Task type used to split the work of parallel_deterministic_reduce.
static bool is_peer_stolen(task &t)
Provides default linear indexing of partitioner's sequence.
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
affinity_partition_type(affinity_partition_type &p, split)
Base class for types that should not be copied or assigned.
old_auto_partition_type(old_auto_partition_type &pt, split)
void align_depth(depth_t base)
A helper class to create a proportional_split object for a given type of Range.
linear_affinity_mode(linear_affinity_mode &src, split)
Range pool stores ranges of type T in a circular buffer with MaxCapacity.
Base class for user-defined tasks.
interface9::internal::auto_partition_type task_partition_type
void set_affinity(task &t)
old_auto_partition_type(const affinity_partitioner &)
void note_affinity(task::affinity_id id)
void work_balance(StartType &start, Range &range)
bool decide_whether_to_delay()
static_partition_type(static_partition_type &p, split)
void const char const char int ITT_FORMAT __itt_group_sync p
Provides proportional splitting strategy for partition objects.
interface9::internal::static_partition_type task_partition_type
adaptive_mode(adaptive_mode &src, split)
internal::affinity_id affinity_id
An id as used for specifying affinity.
void execute(StartType &start, Range &range)
simplified algorithm
#define __TBB_RANGE_POOL_CAPACITY
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
task * continue_after_execute_range()
tbb::internal::affinity_id * my_array
range_vector(const T &elem)
initialize via first range in pool
interface9::internal::old_auto_partition_type partition_type
#define __TBB_EXPORTED_METHOD
void execute(StartType &start, Range &range)
bool check_being_stolen(task &)
bool should_execute_range(const task &t)
affinity_partition_type(tbb::internal::affinity_partitioner_base_v3 &ap)
static const unsigned factor
interface9::internal::auto_partition_type::split_type split_type
static size_t get_initial_partition_head()
static void mark_task_stolen(task &t)
void __TBB_EXPORTED_METHOD resize(unsigned factor)
Resize my_array.
auto_partition_type(const auto_partitioner &)
linear_affinity_mode(linear_affinity_mode &src, const proportional_split &split_obj)
Backward-compatible partition for auto and affinity partition objects.
interface9::internal::affinity_partition_type task_partition_type
Enables one or the other code branches.
partition_type(const simple_partitioner &)
interface9::internal::simple_partition_type task_partition_type
void set_affinity(task &)
interface9::internal::affinity_partition_type::split_type split_type
Dummy type that distinguishes splitting constructor from copy constructor.
void set_affinity(affinity_id id)
Set affinity for this task.
void note_affinity(task::affinity_id)
proportional_mode(proportional_mode &src, const proportional_split &split_obj)
tbb::aligned_space< T, MaxCapacity > my_pool
void note_affinity(task::affinity_id)
Task type used in parallel_for.
static_partition_type(static_partition_type &p, const proportional_split &split_obj)
size_t do_split(adaptive_mode &src, split)
bool is_divisible(depth_t max_depth)
partition_type(const partition_type &, split)
#define __TBB_EXPORTED_FUNC
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor()
simple_partition_type(const simple_partitioner &)
simple_partition_type(const simple_partition_type &, split)
static_partition_type(const static_partitioner &)
bool check_being_stolen(task &t)
affinity_id * my_array
Array that remembers affinities of tree positions to affinity_id.
interface9::internal::old_auto_partition_type partition_type
proportional_split get_split()
Defines entry point for affinity partitioner into tbb run-time library.
#define __TBB_DEMAND_DEPTH_ADD
static proportional_split get_split(size_t n)
tbb::atomic< bool > my_child_stolen
interface9::internal::simple_partition_type::split_type split_type
size_t do_split(proportional_mode &src, const proportional_split &split_obj)
dynamic_grainsize_mode(dynamic_grainsize_mode &p, const proportional_split &split_obj)
auto_partition_type(auto_partition_type &src, split)
int current_thread_index()
Returns the index, aka slot number, of the calling thread in its current arena.
proportional_mode(proportional_mode &src, split)
size_t my_size
Number of elements in my_array.
Provides default splitting strategy for partition objects.
bool is_stolen_task() const
True if task was stolen from the task pool of another thread.
void work_balance(StartType &start, Range &range)
void set_affinity(task &t)
bool check_for_demand(task &t)
Join task node that contains shared flag for stealing feedback.
#define __TBB_INITIAL_CHUNKS
void set_affinity(task &)
Identifiers declared inside namespace internal should never be used directly by client code.
affinity_partition_type(affinity_partition_type &p, const proportional_split &split_obj)
value_type fetch_and_store(value_type value)
static const int not_initialized
Task type used to split the work of parallel_reduce.
int ref_count() const
The internal reference count.
Initial task to split the work.
proportional_split split_type