default_partitioner.h

//********************************************************************************
// Copyright 2007-2010 Intel Corporation All Rights Reserved.                   **
//                                                                              **
// The source code contained or described herein and all documents related to   **
// the source code ("Material") are owned by Intel Corporation or its suppliers **
// or licensors. Title to the Material remains with Intel Corporation or its    **
// suppliers and licensors. The Material contains trade secrets and proprietary **
// and confidential information of Intel or its suppliers and licensors. The    **
// Material is protected by worldwide copyright and trade secret laws and       **
// treaty provisions. No part of the Material may be used, copied, reproduced,  **
// modified, published, uploaded, posted, transmitted, distributed, or          **
// disclosed in any way without Intel's prior express written permission.       **
//                                                                              **
// No license under any patent, copyright, trade secret or other intellectual   **
// property right is granted to or conferred upon you by disclosure or delivery **
// of the Materials, either expressly, by implication, inducement, estoppel or  **
// otherwise. Any license under such intellectual property rights must be       **
// express and approved by Intel in writing.                                    **
//********************************************************************************


#ifndef _DEFAULT_PARTITIONER_H_
#define _DEFAULT_PARTITIONER_H_

#include <tbb/task_scheduler_init.h>
#include <cstdlib>

namespace CnC {

    class range_is_tag_type {};
    class range_is_range_type {};

    /// \brief Interface for partitioners: configuring how ranges are partitioned.
    ///
    /// The default_partitioner implements the template interface that each partitioner must satisfy.
    /// 
    /// Given a range type "R", a partitioner "P" must provide a copy-constructor
    /// and the following (template) interface:
    ///  - int size() const;
    ///  - template< typename T > void divide_and_originate( R &, T & ) const;
    ///  - bool is_divisible( const R & ) const;
    ///  - int grain_size( size_t fullRangeSize ) const;
    ///  - split_type
    ///
    /// The default_partitioner can be parametrized as follows:
    /// Set template argument to > 0 to let it use a fixed grainsize.
    /// If it equals 0, the grainsize is set to "original_rangeSize / #threads / 4"
    template< int grainSize = 0 >
    class default_partitioner
    {
    public:
        default_partitioner() : m_grainSize( grainSize )
        {
            //            std::cerr << "d";
        }
        default_partitioner( const default_partitioner< grainSize > & o ) : m_grainSize( o.m_grainSize )
        {
            //            std::cerr << "c";
        }
        /// \brief divide given range into in arbitrary number of ranges of type Range
        ///
        /// Call si.originate_range( r ) for each new range.
        /// The original - but modified - range is treated as unsplittable afterwards. It must *not* be passed to originate_range!
        /// If tag-types are self-dividing (e.g. if range-type == tag-type) you can call "originate"
        /// instead of "originate_range" for leaves of the recursive range-tree.
        ///
        /// The aggregated set of the members of the sub-ranges applied to "t.originate[_range]" must equal the set of member in given range.
        /// Overlapping ranges or gaps may lead to arbitrary effects.
        ///
        /// \param range the original range to split, may be altered
        /// \param si opaque object, call t.Put( r, splittable ) for all sub-ranges
        template< typename Range, typename StepInstance >
        inline void divide_and_originate( Range & range, StepInstance & si ) const;

        /// \brief return true, if given range is divisible, false otherwise
        template< typename Range >
        bool is_divisible( const Range & range ) const;

        /// \return grainsize for given size of unsplitted range
        int grain_size( size_t fullRangeSize ) const;

        /// 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
        /// set to range_is_range_type if tag is undivisible, e.g. if range-type != step_type
        typedef range_is_range_type split_type;

    private:
        template< typename Range >
        bool is_divisible( const Range & range, int grain ) const;
        // actual implemenation of divide_and_originate, avoiding repeated access to range.size() and grain_size()
        template< typename Range, typename StepInstance >
        void divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
        int m_grainSize;
    };


    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    inline int default_partitioner< grainSize >::grain_size( size_t rangeSize ) const
    {
        if( grainSize > 0 ) return grainSize;
        else {
            if( m_grainSize <= 0 ) {
                static int _nt = 0;
                if( _nt == 0 ) {
                    if( getenv( "CNC_NUM_THREADS" ) ) {
                        _nt = atoi( getenv( "CNC_NUM_THREADS" ) );
                    } else {
                        _nt = tbb::task_scheduler_init::default_num_threads();
                    }
                }
#define MX( _a, _b ) ((_a) > (_b) ? (_a) : (_b))
                const_cast< int & >( m_grainSize ) = rangeSize > 0 ? MX( 1, (int)(rangeSize / (size_t)_nt / 4) ) : 1;
            }
            return m_grainSize;
        }
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range, typename StepInstance >
    inline void default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
    {
        while( (int)range.size() > grain && range.is_divisible() ) {
            Range _r( range, tbb::split() );
            si.originate_range( _r );
        }
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range, typename StepInstance >
    inline void default_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
    {
        divide_and_originate( range, si, grain_size( range.size() ) );
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range >
    inline bool default_partitioner< grainSize >::is_divisible( const Range & range ) const
    {
        return is_divisible( range, grain_size( range.size() ) );
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range >
    bool default_partitioner< grainSize >::is_divisible( const Range & range, int grain ) const
    {
        return ( (int)range.size() > grain ) && range.is_divisible();
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    /// Use this instead of default_partitioner if your tag is self-dividing (e.g. a range)
    /// and you want to use the partitioning mechanism through cnC::tag_collection::put_range
    template< int grainSize = 0 >
    class tag_partitioner : public default_partitioner< grainSize >
    {
    public:
        template< typename Range, typename StepInstance >
        inline void divide_and_originate( Range & range, StepInstance & si ) const;
        typedef range_is_tag_type split_type;

    private:
        template< typename Range, typename StepInstance >
        void divide_and_originate( Range & range, StepInstance & si, const int grain ) const;
    };

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range, typename StepInstance >
    inline void tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si, const int grain ) const
    {
        while( (int)range.size() > grain && range.is_divisible() ) {
            Range _r( range, tbb::split() );
            si.originate_range( _r );
        }
        si.originate( range );
    }

    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    template< int grainSize >
    template< typename Range, typename StepInstance >
    inline void tag_partitioner< grainSize >::divide_and_originate( Range & range, StepInstance & si ) const
    {
        divide_and_originate( range, si, grain_size( range.size() ) );
    }

} // namspace CnC

#endif // _DEFAULT_PARTITIONER_H_