CnC
default_partitioner.h
1 /* *******************************************************************************
2  * Copyright (c) 2007-2014, Intel Corporation
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * * Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of Intel Corporation nor the names of its contributors
13  * may be used to endorse or promote products derived from this software
14  * without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  ********************************************************************************/
27 
28 /*
29  CnC partitioner interfacem used by CnC tuners.
30 */
31 
32 #ifndef _DEFAULT_PARTITIONER_H_
33 #define _DEFAULT_PARTITIONER_H_
34 
35 #include <cnc/internal/tbbcompat.h>
36 #include <tbb/task_scheduler_init.h>
37 #include <cstdlib>
38 
39 namespace CnC {
40 
41  class range_is_tag_type {};
42  class range_is_range_type {};
43 
44  /// \brief Interface for partitioners: configuring how ranges are partitioned.
45  ///
46  /// The default_partitioner implements the template interface that each partitioner must satisfy.
47  ///
48  /// Given a range type "R", a partitioner "P" must provide a copy-constructor
49  /// and the following (template) interface:
50  /// - template< typename T > void divide_and_originate( R &, T & ) const;
51  /// - split_type
52  ///
53  /// The default_partitioner can be parametrized as follows:
54  /// Set template argument to > 0 to let it use a fixed grainsize.
55  /// If it equals 0, the grainsize is set to "original_rangeSize / #threads / 4"
56  /// If it is < 0, the grainsize of the given range is obeyed.
57  template< int grainSize = 0 >
59  {
60  public:
62  : m_grainSize( grainSize ),
63  m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() )
64  {
65  // std::cerr << "d";
66  }
68  : m_grainSize( o.m_grainSize ),
69  m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() )
70  {
71  // std::cerr << "c";
72  }
73  /// \brief divide given range into in arbitrary number of ranges of type Range
74  ///
75  /// Call si.originate_range( r ) for each new range.
76  /// The original - but modified - range must *not* be passed to originate_range!
77  /// If tag-types are self-dividing (e.g. if range-type == tag-type) you should call "originate"
78  /// instead of "originate_range" for leaves of the recursive range-tree.
79  /// \return true if the orignal - but modified - range needs further splitting, false if no further splitting is desired.
80  ///
81  /// The aggregated set of the members of the sub-ranges applied to "t.originate[_range]" must equal the set of member in given range.
82  /// Overlapping ranges or gaps may lead to arbitrary effects.
83  ///
84  /// \param range the original range to split, may be altered
85  /// \param si opaque object, call t.originate[_range]( r ) for all split-off sub-ranges
86  template< typename Range, typename StepInstance >
87  inline bool divide_and_originate( Range & range, StepInstance & si ) const;
88 
89  /// 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
90  /// set to range_is_range_type if tag is undivisible, e.g. if range-type != step_type
91  typedef range_is_range_type split_type;
92 
93  protected:
94  /// \brief return true, if given range is divisible, false otherwise
95  template< typename Range >
96  bool is_divisible( const Range & range ) const;
97 
98  /// \return grainsize for given size of unsplitted range
99  int grain_size( size_t fullRangeSize ) const;
100 
101  template< typename Range >
102  bool is_divisible( const Range & range, int grain ) const;
103 
104  private:
105  // actual implemenation of divide_and_originate, avoiding repeated access to range.size() and grain_size()
106  template< typename Range, typename StepInstance >
107  bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
108  int m_grainSize;
109  int m_nt;
110  };
111 
112 
113  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
114  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
115  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
116  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
117 
118  template< int grainSize >
119  inline int default_partitioner< grainSize >::grain_size( size_t rangeSize ) const
120  {
121  if( grainSize != 0 ) return grainSize;
122  else {
123  if( m_grainSize <= 0 ) {
124 #define MX( _a, _b ) ((_a) > (_b) ? (_a) : (_b))
125  const_cast< int & >( m_grainSize ) = rangeSize > 0 ? MX( 1, (int)(rangeSize / (size_t)m_nt / 4) ) : 1;
126  }
127  return m_grainSize;
128  }
129  }
130 
131  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
132  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
133 
134  template< int grainSize >
135  template< typename Range, typename StepInstance >
136  inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
137  {
138  if( this->is_divisible( range, grain ) ) {
139  Range _r( range, tbb::split() );
140  si.originate_range( _r );
141  }
142  return this->is_divisible( range, grain );
143  }
144 
145  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
146  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147 
148  template< int grainSize >
149  template< typename Range, typename StepInstance >
150  inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
151  {
152  return this->divide_and_originate( range, si, this->grain_size( range.size() ) );
153  }
154 
155  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
156  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157 
158  template< int grainSize >
159  template< typename Range >
160  inline bool default_partitioner< grainSize >::is_divisible( const Range & range ) const
161  {
162  return this->is_divisible( range, this->grain_size( range.size() ) );
163  }
164 
165  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
166  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
167 
168  template< int grainSize >
169  template< typename Range >
170  bool default_partitioner< grainSize >::is_divisible( const Range & range, int grain ) const
171  {
172  return ( grainSize < 0 || (int)range.size() > grain ) && range.is_divisible();
173  }
174 
175  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
176  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
177  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
178  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
179 
180  /// Use this instead of default_partitioner if your tag is self-dividing (e.g. a range)
181  /// and you want to use the partitioning mechanism through cnC::tag_collection::put_range
182  template< int grainSize = 0 >
183  class tag_partitioner : public default_partitioner< grainSize >
184  {
185  public:
186  template< typename Range, typename StepInstance >
187  inline bool divide_and_originate( Range & range, StepInstance & si ) const;
188  typedef range_is_tag_type split_type;
189 
190  private:
191  template< typename Range, typename StepInstance >
192  bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
193  };
194 
195  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
196  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
197 
198  template< int grainSize >
199  template< typename Range, typename StepInstance >
200  inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
201  {
202  if( this->is_divisible( range, grain ) ) {
203  Range _r( range, tbb::split() );
204  si.originate_range( _r );
205  if( this->is_divisible( range, grain ) ) return true;
206  }
207  si.originate( range );
208  return false;
209  }
210 
211  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
212  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
213 
214  template< int grainSize >
215  template< typename Range, typename StepInstance >
216  inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
217  {
218  return this->divide_and_originate( range, si, this->grain_size( range.size() ) );
219  }
220 
221 } // namspace CnC
222 
223 #endif // _DEFAULT_PARTITIONER_H_
range_is_range_type split_type
Interface for partitioners: configuring how ranges are partitioned.
bool divide_and_originate(Range &range, StepInstance &si) const
divide given range into in arbitrary number of ranges of type Range
CnC API.
Definition: cnc.h:49
bool is_divisible(const Range &range) const
return true, if given range is divisible, false otherwise
int grain_size(size_t fullRangeSize) const