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

   1 /*
   2     Copyright 2005-2010 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> class start_reduce_with_affinity;
  77 template<typename Range, typename Body, typename Partitioner> class start_scan;
  78
  79 } // namespace internal
  80 //! @endcond
  81
  82 //! A simple partitioner
  83 /** Divides the range until the range is not divisible.
  84     @ingroup algorithms */
  85 class simple_partitioner {
  86 public:
  87     simple_partitioner() {}
  88 private:
  89     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
  90     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
  91     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
  92
  93     class partition_type: public internal::partition_type_base {
  94     public:
  95         bool should_execute_range(const task& ) {return false;}
  96         partition_type( const simple_partitioner& ) {}
  97         partition_type( const partition_type&, split ) {}
  98     };
  99 };
 100
 101 //! An auto partitioner
 102 /** The range is initial divided into several large chunks.
 103     Chunks are further subdivided into VICTIM_CHUNKS pieces if they are stolen and divisible.
 104     @ingroup algorithms */
 105 class auto_partitioner {
 106 public:
 107     auto_partitioner() {}
 108
 109 private:
 110     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
 111     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
 112     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
 113
 114     class partition_type: public internal::partition_type_base {
 115         size_t num_chunks;
 116         static const size_t VICTIM_CHUNKS = 4;
 117 public:
 118         bool should_execute_range(const task &t) {
 119             if( num_chunks<VICTIM_CHUNKS && t.is_stolen_task() )
 120                 num_chunks = VICTIM_CHUNKS;
 121             return num_chunks==1;
 122         }
 123         partition_type( const auto_partitioner& ) : num_chunks(internal::get_initial_auto_partitioner_divisor()) {}
 124         partition_type( partition_type& pt, split ) {
 125             num_chunks = pt.num_chunks /= 2u;
 126         }
 127     };
 128 };
 129
 130 //! An affinity partitioner
 131 class affinity_partitioner: internal::affinity_partitioner_base_v3 {
 132 public:
 133     affinity_partitioner() {}
 134
 135 private:
 136     template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
 137     template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
 138     template<typename Range, typename Body> friend class internal::start_reduce_with_affinity;
 139     template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;
 140
 141     typedef internal::affinity_partition_type partition_type;
 142     friend class internal::affinity_partition_type;
 143 };
 144
 145 //! @cond INTERNAL
 146 namespace internal {
 147
 148 class affinity_partition_type: public no_copy {
 149     //! Must be power of two
 150     static const unsigned factor = 16;
 151     static const size_t VICTIM_CHUNKS = 4;
 152
 153     internal::affinity_id* my_array;
 154     task_list delay_list;
 155     unsigned map_begin, map_end;
 156     size_t num_chunks;
 157 public:
 158     affinity_partition_type( affinity_partitioner& ap ) {
 159         __TBB_ASSERT( (factor&(factor-1))==0, "factor must be power of two" );
 160         ap.resize(factor);
 161         my_array = ap.my_array;
 162         map_begin = 0;
 163         map_end = unsigned(ap.my_size);
 164         num_chunks = internal::get_initial_auto_partitioner_divisor();
 165     }
 166     affinity_partition_type(affinity_partition_type& p, split) : my_array(p.my_array) {
 167         __TBB_ASSERT( p.map_end-p.map_begin<factor || (p.map_end-p.map_begin)%factor==0, NULL );
 168         num_chunks = p.num_chunks /= 2;
 169         unsigned e = p.map_end;
 170         unsigned d = (e - p.map_begin)/2;
 171         if( d>factor )
 172             d &= 0u-factor;
 173         map_end = e;
 174         map_begin = p.map_end = e-d;
 175     }
 176
 177     bool should_execute_range(const task &t) {
 178         if( num_chunks < VICTIM_CHUNKS && t.is_stolen_task() )
 179             num_chunks = VICTIM_CHUNKS;
 180         return num_chunks == 1;
 181     }
 182
 183     void set_affinity( task &t ) {
 184         if( map_begin<map_end )
 185             t.set_affinity( my_array[map_begin] );
 186     }
 187     void note_affinity( task::affinity_id id ) {
 188         if( map_begin<map_end )
 189             my_array[map_begin] = id;
 190     }
 191     task* continue_after_execute_range() {
 192         task* first = NULL;
 193         if( !delay_list.empty() ) {
 194             first = &delay_list.pop_front();
 195             while( !delay_list.empty() ) {
 196                 task::spawn(*first);
 197                 first = &delay_list.pop_front();
 198             }
 199         }
 200         return first;
 201     }
 202     bool decide_whether_to_delay() {
 203         // The possible underflow caused by "-1u" is deliberate
 204         return (map_begin&(factor-1))==0 && map_end-map_begin-1u<factor;
 205     }
 206     void spawn_or_delay( bool delay, task& b ) {
 207         if( delay )
 208             delay_list.push_back(b);
 209         else
 210             task::spawn(b);
 211     }
 212
 213     ~affinity_partition_type() {
 214         // The delay_list can be non-empty if an exception is thrown.
 215         while( !delay_list.empty() ) {
 216             task& t = delay_list.pop_front();
 217             t.destroy(t);
 218         }
 219     }
 220 };
 221
 222 } // namespace internal
 223 //! @endcond
 224
 225
 226 } // namespace tbb
 227
 228 #endif /* __TBB_partitioner_H */