CnC
|
00001 /* ******************************************************************************* 00002 * Copyright (c) 2007-2014, Intel Corporation 00003 * 00004 * Redistribution and use in source and binary forms, with or without 00005 * modification, are permitted provided that the following conditions are met: 00006 * 00007 * * Redistributions of source code must retain the above copyright notice, 00008 * this list of conditions and the following disclaimer. 00009 * * Redistributions in binary form must reproduce the above copyright 00010 * notice, this list of conditions and the following disclaimer in the 00011 * documentation and/or other materials provided with the distribution. 00012 * * Neither the name of Intel Corporation nor the names of its contributors 00013 * may be used to endorse or promote products derived from this software 00014 * without specific prior written permission. 00015 * 00016 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00017 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00018 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 00019 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 00020 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00021 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 00022 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 00023 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 00024 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00025 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00026 ********************************************************************************/ 00027 00028 /* 00029 CnC partitioner interfacem used by CnC tuners. 00030 */ 00031 00032 #ifndef _DEFAULT_PARTITIONER_H_ 00033 #define _DEFAULT_PARTITIONER_H_ 00034 00035 #include <cnc/internal/tbbcompat.h> 00036 #include <tbb/task_scheduler_init.h> 00037 #include <cstdlib> 00038 00039 namespace CnC { 00040 00041 class range_is_tag_type {}; 00042 class range_is_range_type {}; 00043 00044 /// \brief Interface for partitioners: configuring how ranges are partitioned. 00045 /// 00046 /// The default_partitioner implements the template interface that each partitioner must satisfy. 00047 /// 00048 /// Given a range type "R", a partitioner "P" must provide a copy-constructor 00049 /// and the following (template) interface: 00050 /// - template< typename T > void divide_and_originate( R &, T & ) const; 00051 /// - split_type 00052 /// 00053 /// The default_partitioner can be parametrized as follows: 00054 /// Set template argument to > 0 to let it use a fixed grainsize. 00055 /// If it equals 0, the grainsize is set to "original_rangeSize / #threads / 4" 00056 /// If it is < 0, the grainsize of the given range is obeyed. 00057 template< int grainSize = 0 > 00058 class default_partitioner 00059 { 00060 public: 00061 default_partitioner() 00062 : m_grainSize( grainSize ), 00063 m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() ) 00064 { 00065 // std::cerr << "d"; 00066 } 00067 default_partitioner( const default_partitioner< grainSize > & o ) 00068 : m_grainSize( o.m_grainSize ), 00069 m_nt( getenv( "CNC_NUM_THREADS" ) ? atoi( getenv( "CNC_NUM_THREADS" ) ) : tbb::task_scheduler_init::default_num_threads() ) 00070 { 00071 // std::cerr << "c"; 00072 } 00073 /// \brief divide given range into in arbitrary number of ranges of type Range 00074 /// 00075 /// Call si.originate_range( r ) for each new range. 00076 /// The original - but modified - range must *not* be passed to originate_range! 00077 /// If tag-types are self-dividing (e.g. if range-type == tag-type) you should call "originate" 00078 /// instead of "originate_range" for leaves of the recursive range-tree. 00079 /// \return true if the orignal - but modified - range needs further splitting, false if no further splitting is desired. 00080 /// 00081 /// The aggregated set of the members of the sub-ranges applied to "t.originate[_range]" must equal the set of member in given range. 00082 /// Overlapping ranges or gaps may lead to arbitrary effects. 00083 /// 00084 /// \param range the original range to split, may be altered 00085 /// \param si opaque object, call t.originate[_range]( r ) for all split-off sub-ranges 00086 template< typename Range, typename StepInstance > 00087 inline bool divide_and_originate( Range & range, StepInstance & si ) const; 00088 00089 /// 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 00090 /// set to range_is_range_type if tag is undivisible, e.g. if range-type != step_type 00091 typedef range_is_range_type split_type; 00092 00093 protected: 00094 /// \brief return true, if given range is divisible, false otherwise 00095 template< typename Range > 00096 bool is_divisible( const Range & range ) const; 00097 00098 /// \return grainsize for given size of unsplitted range 00099 int grain_size( size_t fullRangeSize ) const; 00100 00101 template< typename Range > 00102 bool is_divisible( const Range & range, int grain ) const; 00103 00104 private: 00105 // actual implemenation of divide_and_originate, avoiding repeated access to range.size() and grain_size() 00106 template< typename Range, typename StepInstance > 00107 bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const; 00108 int m_grainSize; 00109 int m_nt; 00110 }; 00111 00112 00113 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00114 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00115 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00116 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00117 00118 template< int grainSize > 00119 inline int default_partitioner< grainSize >::grain_size( size_t rangeSize ) const 00120 { 00121 if( grainSize != 0 ) return grainSize; 00122 else { 00123 if( m_grainSize <= 0 ) { 00124 #define MX( _a, _b ) ((_a) > (_b) ? (_a) : (_b)) 00125 const_cast< int & >( m_grainSize ) = rangeSize > 0 ? MX( 1, (int)(rangeSize / (size_t)m_nt / 4) ) : 1; 00126 } 00127 return m_grainSize; 00128 } 00129 } 00130 00131 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00132 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00133 00134 template< int grainSize > 00135 template< typename Range, typename StepInstance > 00136 inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const 00137 { 00138 if( this->is_divisible( range, grain ) ) { 00139 Range _r( range, tbb::split() ); 00140 si.originate_range( _r ); 00141 } 00142 return this->is_divisible( range, grain ); 00143 } 00144 00145 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00146 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00147 00148 template< int grainSize > 00149 template< typename Range, typename StepInstance > 00150 inline bool default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const 00151 { 00152 return this->divide_and_originate( range, si, this->grain_size( range.size() ) ); 00153 } 00154 00155 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00156 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00157 00158 template< int grainSize > 00159 template< typename Range > 00160 inline bool default_partitioner< grainSize >::is_divisible( const Range & range ) const 00161 { 00162 return this->is_divisible( range, this->grain_size( range.size() ) ); 00163 } 00164 00165 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00166 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00167 00168 template< int grainSize > 00169 template< typename Range > 00170 bool default_partitioner< grainSize >::is_divisible( const Range & range, int grain ) const 00171 { 00172 return ( grainSize < 0 || (int)range.size() > grain ) && range.is_divisible(); 00173 } 00174 00175 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00176 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00177 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00178 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00179 00180 /// Use this instead of default_partitioner if your tag is self-dividing (e.g. a range) 00181 /// and you want to use the partitioning mechanism through cnC::tag_collection::put_range 00182 template< int grainSize = 0 > 00183 class tag_partitioner : public default_partitioner< grainSize > 00184 { 00185 public: 00186 template< typename Range, typename StepInstance > 00187 inline bool divide_and_originate( Range & range, StepInstance & si ) const; 00188 typedef range_is_tag_type split_type; 00189 00190 private: 00191 template< typename Range, typename StepInstance > 00192 bool divide_and_originate( Range & range, StepInstance & si, const int grain ) const; 00193 }; 00194 00195 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00196 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00197 00198 template< int grainSize > 00199 template< typename Range, typename StepInstance > 00200 inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const 00201 { 00202 if( this->is_divisible( range, grain ) ) { 00203 Range _r( range, tbb::split() ); 00204 si.originate_range( _r ); 00205 if( this->is_divisible( range, grain ) ) return true; 00206 } 00207 si.originate( range ); 00208 return false; 00209 } 00210 00211 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00212 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 00213 00214 template< int grainSize > 00215 template< typename Range, typename StepInstance > 00216 inline bool tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const 00217 { 00218 return this->divide_and_originate( range, si, this->grain_size( range.size() ) ); 00219 } 00220 00221 } // namspace CnC 00222 00223 #endif // _DEFAULT_PARTITIONER_H_