Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
partitioner.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #ifndef __TBB_partitioner_H
22 #define __TBB_partitioner_H
23 
24 #ifndef __TBB_INITIAL_CHUNKS
25 // initial task divisions per thread
26 #define __TBB_INITIAL_CHUNKS 2
27 #endif
28 #ifndef __TBB_RANGE_POOL_CAPACITY
29 // maximum number of elements in range pool
30 #define __TBB_RANGE_POOL_CAPACITY 8
31 #endif
32 #ifndef __TBB_INIT_DEPTH
33 // initial value for depth of range pool
34 #define __TBB_INIT_DEPTH 5
35 #endif
36 #ifndef __TBB_DEMAND_DEPTH_ADD
37 // when imbalance is found range splits this value times more
38 #define __TBB_DEMAND_DEPTH_ADD 1
39 #endif
40 #ifndef __TBB_STATIC_THRESHOLD
41 // necessary number of clocks for the work to be distributed among all tasks
42 #define __TBB_STATIC_THRESHOLD 40000
43 #endif
44 #if __TBB_DEFINE_MIC
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
51 
52 #include "task.h"
53 #include "task_arena.h"
54 #include "aligned_space.h"
55 #include "atomic.h"
57 
58 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
59  // Workaround for overzealous compiler warnings
60  #pragma warning (push)
61  #pragma warning (disable: 4244)
62 #endif
63 
64 namespace tbb {
65 
66 class auto_partitioner;
67 class simple_partitioner;
68 class static_partitioner;
69 class affinity_partitioner;
70 
71 namespace interface9 {
72  namespace internal {
73  class affinity_partition_type;
74  }
75 }
76 
77 namespace internal { //< @cond INTERNAL
79 
85 
88  size_t my_size;
94 
95  void __TBB_EXPORTED_METHOD resize( unsigned factor );
96 };
97 
100 public:
101  void set_affinity( task & ) {}
104  bool decide_whether_to_delay() {return false;}
105  void spawn_or_delay( bool, task& b ) {
106  task::spawn(b);
107  }
108 };
109 
110 template<typename Range, typename Body, typename Partitioner> class start_scan;
111 
112 } //< namespace internal @endcond
113 
114 namespace serial {
115 namespace interface9 {
116 template<typename Range, typename Body, typename Partitioner> class start_for;
117 }
118 }
119 
120 namespace interface9 {
122 namespace internal {
123 using namespace tbb::internal;
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;
127 
129 class flag_task: public task {
130 public:
132  flag_task() { my_child_stolen = false; }
133  task* execute() __TBB_override { return NULL; }
134  static void mark_task_stolen(task &t) {
135  tbb::atomic<bool> &flag = static_cast<flag_task*>(t.parent())->my_child_stolen;
136 #if TBB_USE_THREADING_TOOLS
137  // Threading tools respect lock prefix but report false-positive data-race via plain store
138  flag.fetch_and_store<release>(true);
139 #else
140  flag = true;
141 #endif //TBB_USE_THREADING_TOOLS
142  }
143  static bool is_peer_stolen(task &t) {
144  return static_cast<flag_task*>(t.parent())->my_child_stolen;
145  }
146 };
147 
151 typedef unsigned char depth_t;
152 
154 template <typename T, depth_t MaxCapacity>
159  depth_t my_depth[MaxCapacity]; // relative depths of stored ranges
161 
162 public:
164  range_vector(const T& elem) : my_head(0), my_tail(0), my_size(1) {
165  my_depth[0] = 0;
166  new( static_cast<void *>(my_pool.begin()) ) T(elem);//TODO: std::move?
167  }
169  while( !empty() ) pop_back();
170  }
171  bool empty() const { return my_size == 0; }
172  depth_t size() const { return my_size; }
175  void split_to_fill(depth_t max_depth) {
176  while( my_size < MaxCapacity && is_divisible(max_depth) ) {
177  depth_t prev = my_head;
178  my_head = (my_head + 1) % MaxCapacity;
179  new(my_pool.begin()+my_head) T(my_pool.begin()[prev]); // copy TODO: std::move?
180  my_pool.begin()[prev].~T(); // instead of assignment
181  new(my_pool.begin()+prev) T(my_pool.begin()[my_head], split()); // do 'inverse' split
182  my_depth[my_head] = ++my_depth[prev];
183  my_size++;
184  }
185  }
186  void pop_back() {
187  __TBB_ASSERT(my_size > 0, "range_vector::pop_back() with empty size");
188  my_pool.begin()[my_head].~T();
189  my_size--;
190  my_head = (my_head + MaxCapacity - 1) % MaxCapacity;
191  }
192  void pop_front() {
193  __TBB_ASSERT(my_size > 0, "range_vector::pop_front() with empty size");
194  my_pool.begin()[my_tail].~T();
195  my_size--;
196  my_tail = (my_tail + 1) % MaxCapacity;
197  }
198  T& back() {
199  __TBB_ASSERT(my_size > 0, "range_vector::back() with empty size");
200  return my_pool.begin()[my_head];
201  }
202  T& front() {
203  __TBB_ASSERT(my_size > 0, "range_vector::front() with empty size");
204  return my_pool.begin()[my_tail];
205  }
208  __TBB_ASSERT(my_size > 0, "range_vector::front_depth() with empty size");
209  return my_depth[my_tail];
210  }
212  __TBB_ASSERT(my_size > 0, "range_vector::back_depth() with empty size");
213  return my_depth[my_head];
214  }
215  bool is_divisible(depth_t max_depth) {
216  return back_depth() < max_depth && back().is_divisible();
217  }
218 };
219 
221 template <typename Partition>
223  typedef split split_type;
224  // decision makers
225  void set_affinity( task & ) {}
227  bool check_being_stolen(task &) { return false; } // part of old should_execute_range()
228  bool check_for_demand(task &) { return false; }
229  bool is_divisible() { return true; } // part of old should_execute_range()
230  depth_t max_depth() { return 0; }
232  template <typename Range> split_type get_split() { return split(); }
233  Partition& self() { return *static_cast<Partition*>(this); } // CRTP helper
234 
235  template<typename StartType, typename Range>
236  void work_balance(StartType &start, Range &range) {
237  start.run_body( range ); // simple partitioner goes always here
238  }
239 
240  template<typename StartType, typename Range>
241  void execute(StartType &start, Range &range) {
242  // The algorithm in a few words ([]-denotes calls to decision methods of partitioner):
243  // [If this task is stolen, adjust depth and divisions if necessary, set flag].
244  // If range is divisible {
245  // Spread the work while [initial divisions left];
246  // Create trap task [if necessary];
247  // }
248  // If not divisible or [max depth is reached], execute, else do the range pool part
249  if ( range.is_divisible() ) {
250  if ( self().is_divisible() ) {
251  do { // split until 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() );
255  }
256  }
257  self().work_balance(start, range);
258  }
259 };
260 
262 template <typename Partition>
263 struct adaptive_mode : partition_type_base<Partition> {
264  typedef Partition my_partition;
265  size_t my_divisor;
266  // For affinity_partitioner, my_divisor indicates the number of affinity array indices the task reserves.
267  // A task which has only one index must produce the right split without reserved index in order to avoid
268  // it to be overwritten in note_affinity() of the created (right) task.
269  // I.e. a task created deeper than the affinity array can remember must not save its affinity (LIFO order)
270  static const unsigned factor = 1;
271  adaptive_mode() : my_divisor(tbb::internal::get_initial_auto_partitioner_divisor() / 4 * my_partition::factor) {}
272  adaptive_mode(adaptive_mode &src, split) : my_divisor(do_split(src, split())) {}
274  size_t do_split(adaptive_mode &src, split) {
275  return src.my_divisor /= 2u;
276  }
277 };
278 
280 
283 // TODO: check if this helper can be a nested class of proportional_mode.
284 template <typename Range, typename = void>
286  static proportional_split get_split(size_t) { return proportional_split(1,1); }
287 };
288 template <typename Range>
289 struct proportion_helper<Range, typename enable_if<Range::is_splittable_in_proportion, void>::type> {
290  static proportional_split get_split(size_t n) {
291 #if __TBB_NONUNIFORM_TASK_CREATION
292  size_t right = (n + 2) / 3;
293 #else
294  size_t right = n / 2;
295 #endif
296  size_t left = n - right;
297  return proportional_split(left, right);
298  }
299 };
300 
302 template <typename Partition>
303 struct proportional_mode : adaptive_mode<Partition> {
304  typedef Partition my_partition;
305  using partition_type_base<Partition>::self; // CRTP helper to get access to derived classes
306 
307  proportional_mode() : adaptive_mode<Partition>() {}
309  proportional_mode(proportional_mode &src, const proportional_split& split_obj) { self().my_divisor = do_split(src, split_obj); }
310  size_t do_split(proportional_mode &src, const proportional_split& split_obj) {
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);
314 #else
315  size_t portion = split_obj.right() * my_partition::factor;
316 #endif
317  portion = (portion + my_partition::factor/2) & (0ul - my_partition::factor);
318 #if __TBB_ENABLE_RANGE_FEEDBACK
319 
320  if (!portion)
321  portion = my_partition::factor;
322  else if (portion == src.my_divisor)
323  portion = src.my_divisor - my_partition::factor;
324 #endif
325  src.my_divisor -= portion;
326  return portion;
327  }
328  bool is_divisible() { // part of old should_execute_range()
329  return self().my_divisor > my_partition::factor;
330  }
331  template <typename Range>
333  // Create a proportion for the number of threads expected to handle "this" subrange
334  return proportion_helper<Range>::get_split( self().my_divisor / my_partition::factor );
335  }
336 };
337 
338 static size_t get_initial_partition_head() {
339  int current_index = tbb::this_task_arena::current_thread_index();
340  if (current_index == tbb::task_arena::not_initialized)
341  current_index = 0;
342  return size_t(current_index);
343 }
344 
346 template <typename Partition>
348  size_t my_head;
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) {}
355  linear_affinity_mode(linear_affinity_mode &src, const proportional_split& split_obj) : proportional_mode<Partition>(src, split_obj)
356  , my_head((src.my_head + src.my_divisor) % src.my_max_affinity), my_max_affinity(src.my_max_affinity) {}
357  void set_affinity( task &t ) {
358  if( self().my_divisor )
359  t.set_affinity( affinity_id(my_head) + 1 );
360  }
361 };
362 
364 template<class Mode>
365 struct dynamic_grainsize_mode : Mode {
366  using Mode::self;
367 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
368  tbb::internal::machine_tsc_t my_dst_tsc;
369 #endif
370  enum {
371  begin = 0,
373  pass
374  } my_delay;
376  static const unsigned range_pool_size = __TBB_RANGE_POOL_CAPACITY;
378 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
379  , my_dst_tsc(0)
380 #endif
381  , my_delay(begin)
382  , my_max_depth(__TBB_INIT_DEPTH) {}
384  : Mode(p, split())
385 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
386  , my_dst_tsc(0)
387 #endif
388  , my_delay(pass)
389  , my_max_depth(p.my_max_depth) {}
391  : Mode(p, split_obj)
392 #ifdef __TBB_USE_MACHINE_TIME_STAMPS
393  , my_dst_tsc(0)
394 #endif
395  , my_delay(begin)
396  , my_max_depth(p.my_max_depth) {}
397  bool check_being_stolen(task &t) { // part of old should_execute_range()
398  if( !(self().my_divisor / Mode::my_partition::factor) ) { // if not from the top P tasks of binary tree
399  self().my_divisor = 1; // TODO: replace by on-stack flag (partition_state's member)?
400  if( t.is_stolen_task() && t.parent()->ref_count() >= 2 ) { // runs concurrently with the left task
401 #if __TBB_USE_OPTIONAL_RTTI
402  // RTTI is available, check whether the cast is valid
403  __TBB_ASSERT(dynamic_cast<flag_task*>(t.parent()), 0);
404  // correctness of the cast relies on avoiding the root task for which:
405  // - initial value of my_divisor != 0 (protected by separate assertion)
406  // - is_stolen_task() always returns false for the root task.
407 #endif
409  if( !my_max_depth ) my_max_depth++;
410  my_max_depth += __TBB_DEMAND_DEPTH_ADD;
411  return true;
412  }
413  }
414  return false;
415  }
416  depth_t max_depth() { return my_max_depth; }
417  void align_depth(depth_t base) {
418  __TBB_ASSERT(base <= my_max_depth, 0);
419  my_max_depth -= base;
420  }
421  template<typename StartType, typename Range>
422  void work_balance(StartType &start, Range &range) {
423  if( !range.is_divisible() || !self().max_depth() ) {
424  start.run_body( range ); // simple partitioner goes always here
425  }
426  else { // do range pool
427  internal::range_vector<Range, range_pool_size> range_pool(range);
428  do {
429  range_pool.split_to_fill(self().max_depth()); // fill range pool
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();
434  continue;
435  }
436  if( range_pool.is_divisible(self().max_depth()) ) // was not enough depth to fork a task
437  continue; // note: next split_to_fill() should split range at least once
438  }
439  start.run_body( range_pool.back() );
440  range_pool.pop_back();
441  } while( !range_pool.empty() && !start.is_cancelled() );
442  }
443  }
444  bool check_for_demand( task &t ) {
445  if( pass == my_delay ) {
446  if( self().my_divisor > 1 ) // produce affinitized tasks while they have slot in array
447  return true; // do not do my_max_depth++ here, but be sure range_pool is splittable once more
448  else if( self().my_divisor && my_max_depth ) { // make balancing task
449  self().my_divisor = 0; // once for each task; depth will be decreased in align_depth()
450  return true;
451  }
452  else if( flag_task::is_peer_stolen(t) ) {
453  my_max_depth += __TBB_DEMAND_DEPTH_ADD;
454  return true;
455  }
456  } else if( begin == my_delay ) {
457 #ifndef __TBB_USE_MACHINE_TIME_STAMPS
458  my_delay = pass;
459 #else
460  my_dst_tsc = __TBB_time_stamp() + __TBB_task_duration();
461  my_delay = run;
462  } else if( run == my_delay ) {
463  if( __TBB_time_stamp() < my_dst_tsc ) {
464  __TBB_ASSERT(my_max_depth > 0, NULL);
465  my_max_depth--; // increase granularity since tasks seem having too small work
466  return false;
467  }
468  my_delay = pass;
469  return true;
470 #endif // __TBB_USE_MACHINE_TIME_STAMPS
471  }
472  return false;
473  }
474 };
475 
476 class auto_partition_type: public dynamic_grainsize_mode<adaptive_mode<auto_partition_type> > {
477 public:
480  my_divisor *= __TBB_INITIAL_CHUNKS;
481  }
484  bool is_divisible() { // part of old should_execute_range()
485  if( my_divisor > 1 ) return true;
486  if( my_divisor && my_max_depth ) { // can split the task. TODO: on-stack flag instead
487  // keep same fragmentation while splitting for the local task pool
488  my_max_depth--;
489  my_divisor = 0; // decrease max_depth once per task
490  return true;
491  } else return false;
492  }
494  if( flag_task::is_peer_stolen(t) ) {
495  my_max_depth += __TBB_DEMAND_DEPTH_ADD;
496  return true;
497  } else return false;
498  }
499 };
500 
501 class simple_partition_type: public partition_type_base<simple_partition_type> {
502 public:
506  template<typename StartType, typename Range>
507  void execute(StartType &start, Range &range) {
508  split_type split_obj = split(); // start.offer_work accepts split_type as reference
509  while( range.is_divisible() )
510  start.offer_work( split_obj );
511  start.run_body( range );
512  }
513 };
514 
515 class static_partition_type : public linear_affinity_mode<static_partition_type> {
516 public:
524 };
525 
526 class affinity_partition_type : public dynamic_grainsize_mode<linear_affinity_mode<affinity_partition_type> > {
527  static const unsigned factor_power = 4; // TODO: get a unified formula based on number of computing units
529 public:
530  static const unsigned factor = 1 << factor_power; // number of slots in affinity array per task
534  __TBB_ASSERT( (factor&(factor-1))==0, "factor must be power of two" );
535  ap.resize(factor);
536  my_array = ap.my_array;
537  my_max_depth = factor_power + 1;
538  __TBB_ASSERT( my_max_depth < __TBB_RANGE_POOL_CAPACITY, 0 );
539  }
542  , my_array(p.my_array) {}
545  , my_array(p.my_array) {}
546  void set_affinity( task &t ) {
547  if( my_divisor ) {
548  if( !my_array[my_head] )
549  // TODO: consider new ideas with my_array for both affinity and static partitioner's, then code reuse
550  t.set_affinity( affinity_id(my_head / factor + 1) );
551  else
552  t.set_affinity( my_array[my_head] );
553  }
554  }
556  if( my_divisor )
557  my_array[my_head] = id;
558  }
559 };
560 
563  size_t num_chunks;
564  static const size_t VICTIM_CHUNKS = 4;
565 public:
566  bool should_execute_range(const task &t) {
567  if( num_chunks<VICTIM_CHUNKS && t.is_stolen_task() )
568  num_chunks = VICTIM_CHUNKS;
569  return num_chunks==1;
570  }
572  : num_chunks(internal::get_initial_auto_partitioner_divisor()*__TBB_INITIAL_CHUNKS/4) {}
574  : num_chunks(internal::get_initial_auto_partitioner_divisor()*__TBB_INITIAL_CHUNKS/4) {}
576  num_chunks = pt.num_chunks = (pt.num_chunks+1u) / 2u;
577  }
578 };
579 
580 } // namespace interfaceX::internal
582 } // namespace interfaceX
583 
585 
588 public:
590 private:
591  template<typename Range, typename Body, typename Partitioner> friend class serial::interface9::start_for;
592  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_for;
593  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_reduce;
594  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_deterministic_reduce;
595  template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
596  // backward compatibility
597  class partition_type: public internal::partition_type_base {
598  public:
599  bool should_execute_range(const task& ) {return false;}
602  };
603  // new implementation just extends existing interface
605 
606  // TODO: consider to make split_type public
607  typedef interface9::internal::simple_partition_type::split_type split_type;
608 };
609 
611 
615 public:
617 
618 private:
619  template<typename Range, typename Body, typename Partitioner> friend class serial::interface9::start_for;
620  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_for;
621  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_reduce;
622  template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
623  // backward compatibility
625  // new implementation just extends existing interface
627 
628  // TODO: consider to make split_type public
629  typedef interface9::internal::auto_partition_type::split_type split_type;
630 };
631 
634 public:
636 private:
637  template<typename Range, typename Body, typename Partitioner> friend class serial::interface9::start_for;
638  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_for;
639  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_reduce;
640  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_deterministic_reduce;
641  template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
642  // backward compatibility
644  // new implementation just extends existing interface
646 
647  // TODO: consider to make split_type public
649 };
650 
652 class affinity_partitioner: internal::affinity_partitioner_base_v3 {
653 public:
655 
656 private:
657  template<typename Range, typename Body, typename Partitioner> friend class serial::interface9::start_for;
658  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_for;
659  template<typename Range, typename Body, typename Partitioner> friend class interface9::internal::start_reduce;
660  template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
661  // backward compatibility - for parallel_scan only
663  // new implementation just extends existing interface
665 
666  // TODO: consider to make split_type public
668 };
669 
670 } // namespace tbb
671 
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
678 #endif /* __TBB_partitioner_H */
#define __TBB_time_stamp()
size_t left() const
Definition: tbb_stddef.h:413
~affinity_partitioner_base_v3()
Deallocates my_array.
Definition: partitioner.h:92
Type enables transmission of splitting proportion from partitioners to range objects.
Definition: tbb_stddef.h:409
#define __TBB_override
Definition: tbb_stddef.h:244
unsigned short affinity_id
An id as used for specifying affinity.
Definition: task.h:124
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: partitioner.h:133
interface9::internal::static_partition_type::split_type split_type
Definition: partitioner.h:648
dynamic_grainsize_mode(dynamic_grainsize_mode &p, split)
Definition: partitioner.h:383
An auto partitioner.
Definition: partitioner.h:614
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.
Definition: aligned_space.h:39
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
static proportional_split get_split(size_t)
Definition: partitioner.h:286
depth_t front_depth()
similarly to front(), returns depth of the first range in the pool
Definition: partitioner.h:207
Provides backward-compatible methods for partition objects without affinity.
Definition: partitioner.h:99
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
Definition: partitioner.h:624
void split_to_fill(depth_t max_depth)
Definition: partitioner.h:175
void spawn_or_delay(bool, task &b)
Definition: partitioner.h:105
Task type used to split the work of parallel_deterministic_reduce.
static bool is_peer_stolen(task &t)
Definition: partitioner.h:143
Provides default linear indexing of partitioner's sequence.
Definition: partitioner.h:347
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)
Definition: partitioner.h:540
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:335
old_auto_partition_type(old_auto_partition_type &pt, split)
Definition: partitioner.h:575
A helper class to create a proportional_split object for a given type of Range.
Definition: partitioner.h:285
linear_affinity_mode(linear_affinity_mode &src, split)
Definition: partitioner.h:353
Range pool stores ranges of type T in a circular buffer with MaxCapacity.
Definition: partitioner.h:155
Base class for user-defined tasks.
Definition: task.h:592
interface9::internal::auto_partition_type task_partition_type
Definition: partitioner.h:626
old_auto_partition_type(const affinity_partitioner &)
Definition: partitioner.h:573
void work_balance(StartType &start, Range &range)
Definition: partitioner.h:236
static_partition_type(static_partition_type &p, split)
Definition: partitioner.h:520
void const char const char int ITT_FORMAT __itt_group_sync p
Provides proportional splitting strategy for partition objects.
Definition: partitioner.h:303
interface9::internal::static_partition_type task_partition_type
Definition: partitioner.h:645
adaptive_mode(adaptive_mode &src, split)
Definition: partitioner.h:272
internal::affinity_id affinity_id
An id as used for specifying affinity.
Definition: task.h:879
void execute(StartType &start, Range &range)
simplified algorithm
Definition: partitioner.h:507
#define __TBB_RANGE_POOL_CAPACITY
Definition: partitioner.h:30
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
Definition: task.h:830
size_t right() const
Definition: tbb_stddef.h:414
range_vector(const T &elem)
initialize via first range in pool
Definition: partitioner.h:164
interface9::internal::old_auto_partition_type partition_type
Definition: partitioner.h:643
#define __TBB_EXPORTED_METHOD
Definition: tbb_stddef.h:102
#define __TBB_INIT_DEPTH
Definition: partitioner.h:34
void execute(StartType &start, Range &range)
Definition: partitioner.h:241
affinity_partition_type(tbb::internal::affinity_partitioner_base_v3 &ap)
Definition: partitioner.h:532
uint64_t machine_tsc_t
interface9::internal::auto_partition_type::split_type split_type
Definition: partitioner.h:629
static size_t get_initial_partition_head()
Definition: partitioner.h:338
The graph class.
static void mark_task_stolen(task &t)
Definition: partitioner.h:134
void __TBB_EXPORTED_METHOD resize(unsigned factor)
Resize my_array.
Definition: task.cpp:161
auto_partition_type(const auto_partitioner &)
Definition: partitioner.h:478
linear_affinity_mode(linear_affinity_mode &src, const proportional_split &split_obj)
Definition: partitioner.h:355
Backward-compatible partition for auto and affinity partition objects.
Definition: partitioner.h:562
interface9::internal::affinity_partition_type task_partition_type
Definition: partitioner.h:664
Enables one or the other code branches.
partition_type(const simple_partitioner &)
Definition: partitioner.h:600
interface9::internal::simple_partition_type task_partition_type
Definition: partitioner.h:604
interface9::internal::affinity_partition_type::split_type split_type
Definition: partitioner.h:667
Dummy type that distinguishes splitting constructor from copy constructor.
Definition: tbb_stddef.h:399
void set_affinity(affinity_id id)
Set affinity for this task.
Definition: task.h:882
proportional_mode(proportional_mode &src, const proportional_split &split_obj)
Definition: partitioner.h:309
tbb::aligned_space< T, MaxCapacity > my_pool
Definition: partitioner.h:160
void note_affinity(task::affinity_id)
Definition: partitioner.h:102
Task type used in parallel_for.
static_partition_type(static_partition_type &p, const proportional_split &split_obj)
Definition: partitioner.h:522
An affinity partitioner.
Definition: partitioner.h:652
size_t do_split(adaptive_mode &src, split)
Definition: partitioner.h:274
bool is_divisible(depth_t max_depth)
Definition: partitioner.h:215
partition_type(const partition_type &, split)
Definition: partitioner.h:601
#define __TBB_EXPORTED_FUNC
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor()
Definition: task.cpp:153
simple_partition_type(const simple_partitioner &)
Definition: partitioner.h:503
simple_partition_type(const simple_partition_type &, split)
Definition: partitioner.h:504
static_partition_type(const static_partitioner &)
Definition: partitioner.h:518
affinity_id * my_array
Array that remembers affinities of tree positions to affinity_id.
Definition: partitioner.h:86
interface9::internal::old_auto_partition_type partition_type
Definition: partitioner.h:662
Defines entry point for affinity partitioner into tbb run-time library.
Definition: partitioner.h:81
#define __TBB_DEMAND_DEPTH_ADD
Definition: partitioner.h:38
tbb::atomic< bool > my_child_stolen
Definition: partitioner.h:131
interface9::internal::simple_partition_type::split_type split_type
Definition: partitioner.h:607
size_t do_split(proportional_mode &src, const proportional_split &split_obj)
Definition: partitioner.h:310
dynamic_grainsize_mode(dynamic_grainsize_mode &p, const proportional_split &split_obj)
Definition: partitioner.h:390
auto_partition_type(auto_partition_type &src, split)
Definition: partitioner.h:482
int current_thread_index()
Returns the index, aka slot number, of the calling thread in its current arena.
Definition: task_arena.h:406
proportional_mode(proportional_mode &src, split)
Definition: partitioner.h:308
size_t my_size
Number of elements in my_array.
Definition: partitioner.h:88
Provides default splitting strategy for partition objects.
Definition: partitioner.h:263
bool is_stolen_task() const
True if task was stolen from the task pool of another thread.
Definition: task.h:850
void work_balance(StartType &start, Range &range)
Definition: partitioner.h:422
Join task node that contains shared flag for stealing feedback.
Definition: partitioner.h:129
#define __TBB_INITIAL_CHUNKS
Definition: partitioner.h:26
Identifiers declared inside namespace internal should never be used directly by client code.
Definition: atomic.h:55
Release.
Definition: atomic.h:49
affinity_partition_type(affinity_partition_type &p, const proportional_split &split_obj)
Definition: partitioner.h:543
value_type fetch_and_store(value_type value)
Definition: atomic.h:278
A static partitioner.
Definition: partitioner.h:633
Task type used to split the work of parallel_reduce.
int ref_count() const
The internal reference count.
Definition: task.h:862
Initial task to split the work.
A simple partitioner.
Definition: partitioner.h:587

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.