git.sesse.net Git - casparcg/blob - tbb/include/tbb/partitioner.h

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 #ifndef __TBB_partitioner_H
  30 #define __TBB_partitioner_H
  31
  32 #include "task.h"
  33
  34 namespace tbb {
  35 class affinity_partitioner;
  36
  37 //! @cond INTERNAL
  38 namespace internal {
  39 size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor();
  40
  41 //! Defines entry points into tbb run-time library;
  42 /** The entry points are the constructor and destructor. */
  43 class affinity_partitioner_base_v3: no_copy {
  44     friend class tbb::affinity_partitioner;
  45     //! Array that remembers affinities of tree positions to affinity_id.
  46     /** NULL if my_size==0. */
  47     affinity_id* my_array;
  48     //! Number of elements in my_array.
  49     size_t my_size;
  50     //! Zeros the fields.
  51     affinity_partitioner_base_v3() : my_array(NULL), my_size(0) {}
  52     //! Deallocates my_array.
  53     ~affinity_partitioner_base_v3() {resize(0);}
  54     //! Resize my_array.
  55     /** Retains values if resulting size is the same. */
  56     void __TBB_EXPORTED_METHOD resize( unsigned factor );
  57     friend class affinity_partition_type;
  58 };
  59
  60 //! Provides default methods for partition objects without affinity.
  61 class partition_type_base {
  62 public:
  63     void set_affinity( task & ) {}
  64     void note_affinity( task::affinity_id ) {}
  65     task* continue_after_execute_range() {return NULL;}
  66     bool decide_whether_to_delay() {return false;}
  67     void spawn_or_delay( bool, task& b ) {
  68         task::spawn(b);
  69     }
  70 };
  71
  72 class affinity_partition_type;
  73
  74 template<typename Range, typename Body, typename Partitioner> class start_for;
  75 template<typename Range, typename Body, typename Partitioner> class start_reduce;
  76 template<typename Range, typename Body, typename Partitioner> class start_scan;
  77
  78 } // namespace internal
  79 //! @endcond
  80
  81 //! A simple partitioner
  82 /** Divides the range until the range is not divisible.
  83     @ingroup algorithms */
  84 class simple_partitioner {
  85 public:
  86     simple_partitioner() {}
  87 private:
  88     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
  89     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
  90     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
  91
  92     class partition_type: public internal::partition_type_base {
  93     public:
  94         bool should_execute_range(const task& ) {return false;}
  95         partition_type( const simple_partitioner& ) {}
  96         partition_type( const partition_type&, split ) {}
  97     };
  98 };
  99
 100 //! An auto partitioner
 101 /** The range is initial divided into several large chunks.
 102     Chunks are further subdivided into VICTIM_CHUNKS pieces if they are stolen and divisible.
 103     @ingroup algorithms */
 104 class auto_partitioner {
 105 public:
 106     auto_partitioner() {}
 107
 108 private:
 109     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
 110     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
 111     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
 112
 113     class partition_type: public internal::partition_type_base {
 114         size_t num_chunks;
 115         static const size_t VICTIM_CHUNKS = 4;
 116 public:
 117         bool should_execute_range(const task &t) {
 118             if( num_chunks<VICTIM_CHUNKS && t.is_stolen_task() )
 119                 num_chunks = VICTIM_CHUNKS;
 120             return num_chunks==1;
 121         }
 122         partition_type( const auto_partitioner& ) : num_chunks(internal::get_initial_auto_partitioner_divisor()) {}
 123         partition_type( partition_type& pt, split ) {
 124             num_chunks = pt.num_chunks /= 2u;
 125         }
 126     };
 127 };
 128
 129 //! An affinity partitioner
 130 class affinity_partitioner: internal::affinity_partitioner_base_v3 {
 131 public:
 132     affinity_partitioner() {}
 133
 134 private:
 135     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
 136     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
 137     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
 138
 139     typedef internal::affinity_partition_type partition_type;
 140     friend class internal::affinity_partition_type;
 141 };
 142
 143 //! @cond INTERNAL
 144 namespace internal {
 145
 146 class affinity_partition_type: public no_copy {
 147     //! Must be power of two
 148     static const unsigned factor = 16;
 149     static const size_t VICTIM_CHUNKS = 4;
 150
 151     internal::affinity_id* my_array;
 152     task_list delay_list;
 153     unsigned map_begin, map_end;
 154     size_t num_chunks;
 155 public:
 156     affinity_partition_type( affinity_partitioner& ap ) {
 157         __TBB_ASSERT( (factor&(factor-1))==0, "factor must be power of two" );
 158         ap.resize(factor);
 159         my_array = ap.my_array;
 160         map_begin = 0;
 161         map_end = unsigned(ap.my_size);
 162         num_chunks = internal::get_initial_auto_partitioner_divisor();
 163     }
 164     affinity_partition_type(affinity_partition_type& p, split) : my_array(p.my_array) {
 165         __TBB_ASSERT( p.map_end-p.map_begin<factor || (p.map_end-p.map_begin)%factor==0, NULL );
 166         num_chunks = p.num_chunks /= 2;
 167         unsigned e = p.map_end;
 168         unsigned d = (e - p.map_begin)/2;
 169         if( d>factor )
 170             d &= 0u-factor;
 171         map_end = e;
 172         map_begin = p.map_end = e-d;
 173     }
 174
 175     bool should_execute_range(const task &t) {
 176         if( num_chunks < VICTIM_CHUNKS && t.is_stolen_task() )
 177             num_chunks = VICTIM_CHUNKS;
 178         return num_chunks == 1;
 179     }
 180
 181     void set_affinity( task &t ) {
 182         if( map_begin<map_end )
 183             t.set_affinity( my_array[map_begin] );
 184     }
 185     void note_affinity( task::affinity_id id ) {
 186         if( map_begin<map_end )
 187             my_array[map_begin] = id;
 188     }
 189     task* continue_after_execute_range() {
 190         task* first = NULL;
 191         if( !delay_list.empty() ) {
 192             first = &delay_list.pop_front();
 193             while( !delay_list.empty() ) {
 194                 task::spawn(*first);
 195                 first = &delay_list.pop_front();
 196             }
 197         }
 198         return first;
 199     }
 200     bool decide_whether_to_delay() {
 201         // The possible underflow caused by "-1u" is deliberate
 202         return (map_begin&(factor-1))==0 && map_end-map_begin-1u<factor;
 203     }
 204     void spawn_or_delay( bool delay, task& b ) {
 205         if( delay )
 206             delay_list.push_back(b);
 207         else
 208             task::spawn(b);
 209     }
 210
 211     ~affinity_partition_type() {
 212         // The delay_list can be non-empty if an exception is thrown.
 213         while( !delay_list.empty() ) {
 214             task& t = delay_list.pop_front();
 215             t.destroy(t);
 216         }
 217     }
 218 };
 219
 220 } // namespace internal
 221 //! @endcond
 222
 223
 224 } // namespace tbb
 225
 226 #endif /* __TBB_partitioner_H */