CnC
 All Classes Namespaces Functions Variables Typedefs Enumerator Friends Groups Pages
default_partitioner.h
1 //********************************************************************************
2 // Copyright (c) 2007-2013 Intel Corporation. All Rights Reserved. **
3 // **
4 // The source code contained or described herein and all documents related to **
5 // the source code ("Material") are owned by Intel Corporation or its suppliers **
6 // or licensors. Title to the Material remains with Intel Corporation or its **
7 // suppliers and licensors. The Material contains trade secrets and proprietary **
8 // and confidential information of Intel or its suppliers and licensors. The **
9 // Material is protected by worldwide copyright and trade secret laws and **
10 // treaty provisions. No part of the Material may be used, copied, reproduced, **
11 // modified, published, uploaded, posted, transmitted, distributed, or **
12 // disclosed in any way without Intel's prior express written permission. **
13 // **
14 // No license under any patent, copyright, trade secret or other intellectual **
15 // property right is granted to or conferred upon you by disclosure or delivery **
16 // of the Materials, either expressly, by implication, inducement, estoppel or **
17 // otherwise. Any license under such intellectual property rights must be **
18 // express and approved by Intel in writing. **
19 //********************************************************************************
20 
21 
22 #ifndef _DEFAULT_PARTITIONER_H_
23 #define _DEFAULT_PARTITIONER_H_
24 
25 #include <tbb/task_scheduler_init.h>
26 #include <cstdlib>
27 
28 namespace CnC {
29 
30  class range_is_tag_type {};
31  class range_is_range_type {};
32 
33  /// \brief Interface for partitioners: configuring how ranges are partitioned.
34  ///
35  /// The default_partitioner implements the template interface that each partitioner must satisfy.
36  ///
37  /// Given a range type "R", a partitioner "P" must provide a copy-constructor
38  /// and the following (template) interface:
39  /// - template< typename T > void divide_and_originate( R &, T & ) const;
40  /// - split_type
41  ///
42  /// The default_partitioner can be parametrized as follows:
43  /// Set template argument to > 0 to let it use a fixed grainsize.
44  /// If it equals 0, the grainsize is set to "original_rangeSize / #threads / 4"
45  /// If it is < 0, the grainsize of the given range is obeyed.
46  template< int grainSize = 0 >
48  {
49  public:
51  : m_grainSize( grainSize ),
52  m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() )
53  {
54  // std::cerr << "d";
55  }
57  : m_grainSize( o.m_grainSize ),
58  m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() )
59  {
60  // std::cerr << "c";
61  }
62  /// \brief divide given range into in arbitrary number of ranges of type Range
63  ///
64  /// Call si.originate_range( r ) for each new range.
65  /// The original - but modified - range must *not* be passed to originate_range!
66  /// If tag-types are self-dividing (e.g. if range-type == tag-type) you should call "originate"
67  /// instead of "originate_range" for leaves of the recursive range-tree.
68  /// \return true if the orignal - but modified - range needs further splitting, false if no further splitting is desired.
69  ///
70  /// The aggregated set of the members of the sub-ranges applied to "t.originate[_range]" must equal the set of member in given range.
71  /// Overlapping ranges or gaps may lead to arbitrary effects.
72  ///
73  /// \param range the original range to split, may be altered
74  /// \param si opaque object, call t.originate[_range]( r ) for all split-off sub-ranges
75  template< typename Range, typename StepInstance >
76  inline bool divide_and_originate( Range & range, StepInstance & si ) const;
77 
78  /// set to range_is_tag_type if tag is self-dividing, e.g. if the range-type is also the tag-type as passed to the step
79  /// set to range_is_range_type if tag is undivisible, e.g. if range-type != step_type
80  typedef range_is_range_type split_type;
81 
82  protected:
83  /// \brief return true, if given range is divisible, false otherwise
84  template< typename Range >
85  bool is_divisible( const Range & range ) const;
86 
87  /// \return grainsize for given size of unsplitted range
88  int grain_size( size_t fullRangeSize ) const;
89 
90  template< typename Range >
91  bool is_divisible( const Range & range, int grain ) const;
92 
93  private:
94  // actual implemenation of divide_and_originate, avoiding repeated access to range.size() and grain_size()
95  template< typename Range, typename StepInstance >
96  bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
97  int m_grainSize;
98  int m_nt;
99  };
100 
101 
102  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
103  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
104  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
105  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
106 
107  template< int grainSize >
108  inline int default_partitioner< grainSize >::grain_size( size_t rangeSize ) const
109  {
110  if( grainSize != 0 ) return grainSize;
111  else {
112  if( m_grainSize <= 0 ) {
113 #define MX( _a, _b ) ((_a) > (_b) ? (_a) : (_b))
114  const_cast< int & >( m_grainSize ) = rangeSize > 0 ? MX( 1, (int)(rangeSize / (size_t)m_nt / 4) ) : 1;
115  }
116  return m_grainSize;
117  }
118  }
119 
120  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
121  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
122 
123  template< int grainSize >
124  template< typename Range, typename StepInstance >
125  inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
126  {
127  if( this->is_divisible( range, grain ) ) {
128  Range _r( range, tbb::split() );
129  si.originate_range( _r );
130  }
131  return this->is_divisible( range, grain );
132  }
133 
134  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
135  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
136 
137  template< int grainSize >
138  template< typename Range, typename StepInstance >
139  inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
140  {
141  return this->divide_and_originate( range, si, this->grain_size( range.size() ) );
142  }
143 
144  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
145  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
146 
147  template< int grainSize >
148  template< typename Range >
149  inline bool default_partitioner< grainSize >::is_divisible( const Range & range ) const
150  {
151  return this->is_divisible( range, this->grain_size( range.size() ) );
152  }
153 
154  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
155  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
156 
157  template< int grainSize >
158  template< typename Range >
159  bool default_partitioner< grainSize >::is_divisible( const Range & range, int grain ) const
160  {
161  return ( grainSize < 0 || (int)range.size() > grain ) && range.is_divisible();
162  }
163 
164  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
165  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
166  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
167  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
168 
169  /// Use this instead of default_partitioner if your tag is self-dividing (e.g. a range)
170  /// and you want to use the partitioning mechanism through cnC::tag_collection::put_range
171  template< int grainSize = 0 >
172  class tag_partitioner : public default_partitioner< grainSize >
173  {
174  public:
175  template< typename Range, typename StepInstance >
176  inline bool divide_and_originate( Range & range, StepInstance & si ) const;
177  typedef range_is_tag_type split_type;
178 
179  private:
180  template< typename Range, typename StepInstance >
181  bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
182  };
183 
184  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
185  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186 
187  template< int grainSize >
188  template< typename Range, typename StepInstance >
189  inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
190  {
191  if( this->is_divisible( range, grain ) ) {
192  Range _r( range, tbb::split() );
193  si.originate_range( _r );
194  if( this->is_divisible( range, grain ) ) return true;
195  }
196  si.originate( range );
197  return false;
198  }
199 
200  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
201  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
202 
203  template< int grainSize >
204  template< typename Range, typename StepInstance >
205  inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
206  {
207  return this->divide_and_originate( range, si, this->grain_size( range.size() ) );
208  }
209 
210 } // namspace CnC
211 
212 #endif // _DEFAULT_PARTITIONER_H_