17 #ifndef __TBB_partitioner_H 18 #define __TBB_partitioner_H 20 #ifndef __TBB_INITIAL_CHUNKS 22 #define __TBB_INITIAL_CHUNKS 2 24 #ifndef __TBB_RANGE_POOL_CAPACITY 26 #define __TBB_RANGE_POOL_CAPACITY 8 28 #ifndef __TBB_INIT_DEPTH 30 #define __TBB_INIT_DEPTH 5 32 #ifndef __TBB_DEMAND_DEPTH_ADD 34 #define __TBB_DEMAND_DEPTH_ADD 1 36 #ifndef __TBB_STATIC_THRESHOLD 38 #define __TBB_STATIC_THRESHOLD 40000 41 #define __TBB_NONUNIFORM_TASK_CREATION 1 42 #ifdef __TBB_time_stamp 43 #define __TBB_USE_MACHINE_TIME_STAMPS 1 44 #define __TBB_task_duration() __TBB_STATIC_THRESHOLD 45 #endif // __TBB_machine_time_stamp 46 #endif // __TBB_DEFINE_MIC 54 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) 56 #pragma warning (push) 57 #pragma warning (disable: 4244) 62 class auto_partitioner;
63 class simple_partitioner;
64 class static_partitioner;
65 class affinity_partitioner;
67 namespace interface9 {
69 class affinity_partition_type;
106 template<
typename Range,
typename Body,
typename Partitioner>
class start_scan;
111 namespace interface9 {
112 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
116 namespace interface9 {
120 template<
typename Range,
typename Body,
typename Partitioner>
class start_for;
121 template<
typename Range,
typename Body,
typename Partitioner>
class start_reduce;
122 template<
typename Range,
typename Body,
typename Partitioner>
class start_deterministic_reduce;
132 #if TBB_USE_THREADING_TOOLS 137 #endif //TBB_USE_THREADING_TOOLS 140 return static_cast<flag_task*>(t.
parent())->my_child_stolen;
150 template <
typename T, depth_t MaxCapacity>
162 new( static_cast<void *>(my_pool.
begin()) ) T(elem);
165 while( !empty() ) pop_back();
167 bool empty()
const {
return my_size == 0; }
172 while( my_size < MaxCapacity && is_divisible(max_depth) ) {
174 my_head = (my_head + 1) % MaxCapacity;
175 new(my_pool.
begin()+my_head) T(my_pool.
begin()[prev]);
176 my_pool.
begin()[prev].~T();
178 my_depth[my_head] = ++my_depth[prev];
183 __TBB_ASSERT(my_size > 0,
"range_vector::pop_back() with empty size");
184 my_pool.
begin()[my_head].~T();
186 my_head = (my_head + MaxCapacity - 1) % MaxCapacity;
189 __TBB_ASSERT(my_size > 0,
"range_vector::pop_front() with empty size");
190 my_pool.
begin()[my_tail].~T();
192 my_tail = (my_tail + 1) % MaxCapacity;
195 __TBB_ASSERT(my_size > 0,
"range_vector::back() with empty size");
196 return my_pool.
begin()[my_head];
199 __TBB_ASSERT(my_size > 0,
"range_vector::front() with empty size");
200 return my_pool.
begin()[my_tail];
204 __TBB_ASSERT(my_size > 0,
"range_vector::front_depth() with empty size");
205 return my_depth[my_tail];
208 __TBB_ASSERT(my_size > 0,
"range_vector::back_depth() with empty size");
209 return my_depth[my_head];
212 return back_depth() < max_depth && back().is_divisible();
217 template <
typename Partition>
229 Partition&
self() {
return *static_cast<Partition*>(
this); }
231 template<
typename StartType,
typename Range>
233 start.run_body( range );
236 template<
typename StartType,
typename Range>
237 void execute(StartType &start, Range &range) {
245 if ( range.is_divisible() ) {
246 if (
self().is_divisible() ) {
248 typename Partition::split_type split_obj =
self().
template get_split<Range>();
249 start.offer_work( split_obj );
250 }
while ( range.is_divisible() &&
self().is_divisible() );
253 self().work_balance(start, range);
258 template <
typename Partition>
266 static const unsigned factor = 1;
280 template <
typename Range,
typename =
void>
284 template <
typename Range>
287 #if __TBB_NONUNIFORM_TASK_CREATION 288 size_t right = (n + 2) / 3;
290 size_t right = n / 2;
292 size_t left = n - right;
298 template <
typename Partition>
307 #if __TBB_ENABLE_RANGE_FEEDBACK 308 size_t portion = size_t(
float(src.
my_divisor) *
float(split_obj.
right())
309 /
float(split_obj.
left() + split_obj.
right()) + 0.5f);
311 size_t portion = split_obj.
right() * my_partition::factor;
313 portion = (portion + my_partition::factor/2) & (0ul - my_partition::factor);
314 #if __TBB_ENABLE_RANGE_FEEDBACK 317 portion = my_partition::factor;
319 portion = src.
my_divisor - my_partition::factor;
325 return self().my_divisor > my_partition::factor;
327 template <
typename Range>
338 return size_t(current_index);
342 template <
typename Partition>
348 my_max_affinity(self().my_divisor) {}
350 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
352 , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
354 if(
self().my_divisor )
363 #ifdef __TBB_USE_MACHINE_TIME_STAMPS 374 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
381 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
385 , my_max_depth(
p.my_max_depth) {}
388 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
392 , my_max_depth(
p.my_max_depth) {}
394 if( !(
self().my_divisor / Mode::my_partition::factor) ) {
395 self().my_divisor = 1;
397 #if __TBB_USE_OPTIONAL_RTTI 405 if( !my_max_depth ) my_max_depth++;
415 my_max_depth -= base;
417 template<
typename StartType,
typename Range>
419 if( !range.is_divisible() || !
self().max_depth() ) {
420 start.run_body( range );
423 internal::range_vector<Range, range_pool_size> range_pool(range);
425 range_pool.split_to_fill(
self().max_depth());
426 if(
self().check_for_demand( start ) ) {
427 if( range_pool.size() > 1 ) {
428 start.offer_work( range_pool.front(), range_pool.front_depth() );
429 range_pool.pop_front();
432 if( range_pool.is_divisible(
self().max_depth()) )
435 start.run_body( range_pool.back() );
436 range_pool.pop_back();
437 }
while( !range_pool.empty() && !start.is_cancelled() );
441 if( pass == my_delay ) {
442 if(
self().my_divisor > 1 )
444 else if(
self().my_divisor && my_max_depth ) {
445 self().my_divisor = 0;
452 }
else if(
begin == my_delay ) {
453 #ifndef __TBB_USE_MACHINE_TIME_STAMPS 458 }
else if( run == my_delay ) {
466 #endif // __TBB_USE_MACHINE_TIME_STAMPS 481 if( my_divisor > 1 )
return true;
482 if( my_divisor && my_max_depth ) {
502 template<
typename StartType,
typename Range>
503 void execute(StartType &start, Range &range) {
504 split_type split_obj =
split();
505 while( range.is_divisible() )
506 start.offer_work( split_obj );
507 start.run_body( range );
523 static const unsigned factor_power = 4;
526 static const unsigned factor = 1 << factor_power;
530 __TBB_ASSERT( (factor&(factor-1))==0,
"factor must be power of two" );
533 my_max_depth = factor_power + 1;
538 , my_array(
p.my_array) {}
541 , my_array(
p.my_array) {}
544 if( !my_array[my_head] )
553 my_array[my_head] =
id;
560 static const size_t VICTIM_CHUNKS = 4;
564 num_chunks = VICTIM_CHUNKS;
565 return num_chunks==1;
591 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
603 typedef interface9::internal::simple_partition_type::split_type
split_type;
618 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
625 typedef interface9::internal::auto_partition_type::split_type
split_type;
637 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
656 template<
typename Range,
typename Body,
typename Partitioner>
friend class internal::start_scan;
668 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) 669 #pragma warning (pop) 670 #endif // warning 4244 is back 671 #undef __TBB_INITIAL_CHUNKS 672 #undef __TBB_RANGE_POOL_CAPACITY 673 #undef __TBB_INIT_DEPTH #define __TBB_RANGE_POOL_CAPACITY
bool check_being_stolen(task &)
bool check_for_demand(task &)
simple_partition_type(const simple_partitioner &)
static const unsigned factor
interface9::internal::simple_partition_type::split_type split_type
static const int not_initialized
Enables one or the other code branches.
interface9::internal::simple_partition_type task_partition_type
Dummy type that distinguishes splitting constructor from copy constructor.
interface9::internal::affinity_partition_type::split_type split_type
void __TBB_EXPORTED_METHOD resize(unsigned factor)
Resize my_array.
internal::affinity_id affinity_id
An id as used for specifying affinity.
void set_affinity(task &t)
partition_type(const partition_type &, split)
void set_affinity(task &)
#define __TBB_EXPORTED_FUNC
partition_type(const simple_partitioner &)
value_type fetch_and_store(value_type value)
tbb::internal::affinity_id * my_array
void note_affinity(task::affinity_id)
interface9::internal::auto_partition_type task_partition_type
interface9::internal::old_auto_partition_type partition_type
static void mark_task_stolen(task &t)
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor()
affinity_partition_type(affinity_partition_type &p, split)
void split_to_fill(depth_t max_depth)
interface9::internal::static_partition_type task_partition_type
#define __TBB_DEMAND_DEPTH_ADD
Provides backward-compatible methods for partition objects without affinity.
~affinity_partitioner_base_v3()
Deallocates my_array.
Task type used in parallel_for.
static proportional_split get_split(size_t)
static_partition_type(static_partition_type &p, split)
auto_partition_type(auto_partition_type &src, split)
#define __TBB_EXPORTED_METHOD
Task type used to split the work of parallel_deterministic_reduce.
Provides default linear indexing of partitioner's sequence.
old_auto_partition_type(const affinity_partitioner &)
auto_partition_type(const auto_partitioner &)
Base class for types that should not be copied or assigned.
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
affinity_partition_type(tbb::internal::affinity_partitioner_base_v3 &ap)
A helper class to create a proportional_split object for a given type of Range.
void execute(StartType &start, Range &range)
simplified algorithm
tbb::atomic< bool > my_child_stolen
Range pool stores ranges of type T in a circular buffer with MaxCapacity.
bool should_execute_range(const task &)
#define __TBB_INITIAL_CHUNKS
simple_partition_type(const simple_partition_type &, split)
Base class for user-defined tasks.
void note_affinity(task::affinity_id id)
Defines entry point for affinity partitioner into tbb run-time library.
proportional_split split_type
void note_affinity(task::affinity_id)
bool should_execute_range(const task &t)
adaptive_mode(adaptive_mode &src, split)
static proportional_split get_split(size_t n)
bool is_divisible(depth_t max_depth)
Provides proportional splitting strategy for partition objects.
interface9::internal::static_partition_type::split_type split_type
Provides default splitting strategy for partition objects.
void align_depth(depth_t)
bool decide_whether_to_delay()
Initial task to split the work.
size_t do_split(adaptive_mode &src, split)
bool check_for_demand(task &t)
affinity_id * my_array
Array that remembers affinities of tree positions to affinity_id.
Type enables transmission of splitting proportion from partitioners to range objects.
void spawn_or_delay(bool, task &b)
void set_affinity(affinity_id id)
Set affinity for this task.
int current_thread_index()
Returns the index, aka slot number, of the calling thread in its current arena.
tbb::aligned_space< T, MaxCapacity > my_pool
bool is_stolen_task() const
True if task was stolen from the task pool of another thread.
interface9::internal::old_auto_partition_type partition_type
linear_affinity_mode(linear_affinity_mode &src, split)
Backward-compatible partition for auto and affinity partition objects.
unsigned short affinity_id
An id as used for specifying affinity.
task * continue_after_execute_range()
void set_affinity(task &t)
proportional_split get_split()
interface9::internal::auto_partition_type::split_type split_type
size_t do_split(proportional_mode &src, const proportional_split &split_obj)
proportional_mode(proportional_mode &src, const proportional_split &split_obj)
#define __TBB_time_stamp()
int ref_count() const
The internal reference count.
task * execute() __TBB_override
Should be overridden by derived classes.
static_partition_type(const static_partitioner &)
void align_depth(depth_t base)
T * begin() const
Pointer to beginning of array.
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
proportional_mode(proportional_mode &src, split)
affinity_partitioner_base_v3()
Zeros the fields.
void set_affinity(task &)
static bool is_peer_stolen(task &t)
affinity_partition_type(affinity_partition_type &p, const proportional_split &split_obj)
old_auto_partition_type(old_auto_partition_type &pt, split)
dynamic_grainsize_mode(dynamic_grainsize_mode &p, const proportional_split &split_obj)
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
interface9::internal::affinity_partition_type task_partition_type
void work_balance(StartType &start, Range &range)
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
static size_t get_initial_partition_head()
static_partition_type(static_partition_type &p, const proportional_split &split_obj)
depth_t front_depth()
similarly to front(), returns depth of the first range in the pool
Join task node that contains shared flag for stealing feedback.
old_auto_partition_type(const auto_partitioner &)
proportional_split split_type
interface9::internal::old_auto_partition_type partition_type
dynamic_grainsize_mode(dynamic_grainsize_mode &p, split)
range_vector(const T &elem)
initialize via first range in pool
size_t my_size
Number of elements in my_array.
bool check_being_stolen(task &t)
Task type used to split the work of parallel_reduce.
linear_affinity_mode(linear_affinity_mode &src, const proportional_split &split_obj)
Identifiers declared inside namespace internal should never be used directly by client code.
bool check_for_demand(task &t)
void execute(StartType &start, Range &range)
void work_balance(StartType &start, Range &range)