CnC
default_partitioner.h
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_