UT/UT_ParallelUtil.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_ParallelUtil.h ( UT Library, C++)
 *
 * COMMENTS:    Simple wrappers on tbb interface
 */

#ifndef __UT_ParallelUtil__
#define __UT_ParallelUtil__

#include "UT_API.h"
#include <tbb/parallel_for.h>
#include <tbb/parallel_reduce.h>
#include <tbb/blocked_range.h>
#include <tbb/blocked_range2d.h>
#include <UT/UT_Thread.h>

/// Typedef to denote the "split" constructor of a range
typedef tbb::split      UT_Split;

/// Declare prior to use.
template <typename T> 
class UT_BlockedRange;

template <typename T_ROW, typename T_COL=T_ROW> 
class UT_BlockedRange2D;

/// This is needed by UT_CoarsenedRange
template <typename T>
inline size_t UTestimatedNumItems(const tbb::blocked_range<T>& range)
{
    return range.size();
}

template <typename T>
inline size_t UTestimatedNumItems(const UT_BlockedRange<T>& range)
{
    return range.size();
}

template <typename T>
inline size_t UTestimatedNumItems(const UT_BlockedRange2D<T>& range)
{
    return range.rows().size() * range.cols().size();
}

/// UT_CoarsenedRange: This should be used only inside 
/// UT_ParallelFor and UT_ParallelReduce
/// This class wraps an existing range with a new range.
/// This allows us to use simple_partitioner, rather than
/// auto_partitioner, which has disastrous performance with
/// the default grain size in ttb 4.
template< typename RANGE >
class UT_CoarsenedRange : public RANGE
{
public:
    // Compiler-generated versions are fine:
    // ~UT_CoarsenedRange();
    // UT_CoarsenedRange(const UT_CoarsenedRange&);

    // Split into two sub-ranges:
    UT_CoarsenedRange(UT_CoarsenedRange& range, tbb::split spl) :
        RANGE(range, spl),
        myGrainSize(range.myGrainSize)
    {        
    }

    // Inherited: bool empty() const

    bool is_divisible() const
    {
        return 
            RANGE::is_divisible() &&
            (UTestimatedNumItems(static_cast<const RANGE&>(*this)) > myGrainSize);
    }

private:
    size_t myGrainSize;

    UT_CoarsenedRange(const RANGE& base_range, const size_t grain_size) :
        RANGE(base_range),
        myGrainSize(grain_size)
    {        
    }

    template <typename Range, typename Body>
    friend void UTparallelFor(
        const Range &range, const Body &body,
        const int subscribe_ratio, const int min_grain_size
    );
};

/// Run the @c body function over a range in parallel.
/// UTparallelFor attempts to spread the range out over at most 
/// subscribe_ratio * num_processor tasks.
/// The factor subscribe_ratio can be used to help balance the load.
/// UTparallelFor() uses tbb for its implementation.
/// The used grain size is the maximum of min_grain_size and
/// if UTestimatedNumItems(range) / (subscribe_ratio * num_processor).
/// If subscribe_ratio == 0, then a grain size of min_grain_size will be used.
/// A range can be split only when UTestimatedNumItems(range) exceeds the
/// grain size the range is divisible. 

///
/// Requirements for the Range functor are:
///   - the requirements of the tbb Range Concept
///   - there must be a member UTestimatedRange that takes a Range object
///     and returns the estimated number of work items in it.
///
/// Requirements for the Body function are:
///  - @code Body(const Body &); @endcode @n
///     Copy Constructor
///  - @code Body()::~Body(); @endcode @n
///     Destructor
///  - @code void Body::operator()(const Range &range) const; @endcode
///     Function call to perform operation on the range.  Note the operator is
///     @b const.
///
/// The requirements for a Range object are:
///  - @code Range::Range(const Range&); @endcode @n
///     Copy constructor
///  - @code Range::~Range(); @endcode @n
///     Destructor
///  - @code bool Range::is_divisible() const; @endcode @n
///     True if the range can be partitioned into two sub-ranges
///  - @code bool Range::empty() const; @endcode @n
///     True if the range is empty
///  - @code Range::Range(Range &r, UT_Split) const; @endcode @n
///     Split the range @c r into two sub-ranges (i.e. modify @c r and *this)
///
/// Example: @code
///     class Square {
///     public:
///          Square(fpreal *data) : myData(data) {}
///         ~Square();
///         void        operator()(const UT_BlockedRange<int64> &range) const
///                     {
///                         for (int64 i = range.begin(); i != range.end(); ++i)
///                             myData[i] *= myData[i];
///                     }
///         fpreal      *myData;
///     };
///     ...
///
///     void
///     parallel_square(fpreal *array, int64 length)
///     {
///         UTparallelFor(UT_BlockedRange<int64>(0, length), Square(array));
///     }
/// @endcode
///     
/// @see UTparallelReduce(), UT_BlockedRange()

template <typename Range, typename Body>
void UTparallelFor(
    const Range &range, const Body &body,
    const int subscribe_ratio = 2,
    const int min_grain_size = 1
)
{
    const size_t num_processors( UT_Thread::getNumProcessors() );

    UT_ASSERT( num_processors >= 1 );
    UT_ASSERT( min_grain_size >= 1 );
    UT_ASSERT( subscribe_ratio >= 0 );

    const size_t est_range_size( UTestimatedNumItems(range) );

    // Avoid tbb overhead if entire range needs to be single threaded
    if( est_range_size <= min_grain_size )
    {
        body(range);
        return;
    }

    size_t grain_size(min_grain_size);
    if( subscribe_ratio > 1 )
        grain_size = std::max(
                         grain_size, 
                         est_range_size / (subscribe_ratio * num_processors)
                     );

    UT_CoarsenedRange< Range > coarsened_range(range, grain_size);

    tbb::parallel_for(coarsened_range, body, tbb::simple_partitioner());
}

/// Version of UTparallelFor that is tuned for the case where the range
/// consists of lightweight items, for example,
/// float additions or matrix-vector multiplications.
template <typename Range, typename Body>
void UTparallelForLightItems(
    const Range &range, const Body &body
)
{
    UTparallelFor(range, body, 2, 1024);
}

/// Version of UTparallelFor that is tuned for the case where the range
/// consists of heavy items, for example, defragmenting an entire attribute.
template <typename Range, typename Body>
void UTparallelForHeavyItems(
    const Range &range, const Body &body
)
{
    UTparallelFor(range, body, 1, 1);
}

/// UTserialFor can be used as a debugging tool to quickly replace a parallel
/// for with a serial for.
template <typename Range, typename Body>
void UTserialFor(const Range &range, const Body &body)
        { body(range); }

/// UTparallelReduce() is a simple wrapper that uses tbb for its implementation.
/// Run the @c body function over a range in parallel.
/// Note that the @c operator() and @c join() functions should @b not
/// initialize data.  @b Both these functions should only accumulate data.  The
/// body operations may get re-used for multiple iterations.
///
/// Requirements for the Body function are:
///  - @code Body()::~Body(); @endcode @n
///     Destructor
///  - @code Body::Body(Body &r, UT_Split) const; @endcode @n
///     The splitting constructor.  This must be able to run concurrently with
///     the @c operator() and @c join() methods.
///  - @code void Body::operator()(const Range &range); @endcode
///     Function call to perform operation on the range.  Note the operator is
///     @b not const.
///  - @code void Body::join(const Body &other); @endcode
///     Join the results from another operation with this operation.
///     @b not const.
///
/// The requirements for a Range object are:
///  - @code Range::Range(const Range&); @endcode @n
///     Copy constructor
///  - @code Range::~Range(); @endcode @n
///     Destructor
///  - @code bool Range::is_divisible() const; @endcode @n
///     True if the range can be partitioned into two sub-ranges
///  - @code bool Range::empty() const; @endcode @n
///     True if the range is empty
///  - @code Range::Range(Range &r, UT_Split) const; @endcode @n
///     Split the range @c r into two sub-ranges (i.e. modify @c r and *this)
///
/// Example: @code
///    class Dot {
///    public:
///     Dot(const fpreal *a, const fpreal *b)
///         : myA(a)
///         , myB(b)
///         , mySum(0)
///     {}
///     Dot(Dot &src, UT_Split)
///         : myA(src.myA)
///         , myB(src.myB)
///         , mySum(0)
///     {}
///     void    operator()(const UT_BlockedRange<int64> &range)
///             {
///                  for (int64 i = range.begin(); i != range.end(); ++i)
///                      mySum += myA[i] * myB[i];
///             }
///     void    join(const Dot &other)
///             {
///                 mySum += other.mySum;
///             }
///     fpreal          mySum;
///     const fpreal    *myA, *myB;
///    };
///
///    fpreal
///    parallel_dot(const fpreal *a, const fpreal *b, int64 length)
///    {
///     Dot     body(a, b);
///     UTparallelReduce(UT_BlockedRange<int64>(0, length), body);
///     return body.mySum;
///    }
/// @endcode
/// @see UTparallelFor(), UT_BlockedRange()
template <typename Range, typename Body>
void UTparallelReduce(const Range &range, Body &body)
        { tbb::parallel_reduce(range, body); }

/// UTserialReduce can be used as a debugging tool to quickly replace a
/// parallel reduce with a serial for.
template <typename Range, typename Body>
void UTserialReduce(const Range &range, Body &body)
        { body(range); }

/// UT_BlockedRange() is a simple wrapper using tbb for its implementation
/// This meets the requirements for a Range object, which are:
///  - @code Range::Range(const Range&); @endcode @n
///     Copy constructor
///  - @code Range::~Range(); @endcode @n
///     Destructor
///  - @code bool Range::is_divisible() const; @endcode @n
///     True if the range can be partitioned into two sub-ranges
///  - @code bool Range::empty() const; @endcode @n
///     True if the range is empty
///  - @code Range::Range(Range &r, UT_Split) const; @endcode @n
///     Split the range @c r into two sub-ranges (i.e. modify @c r and *this)
template <typename T>
class UT_BlockedRange : public tbb::blocked_range<T>
{
public:
    UT_BlockedRange()
        : tbb::blocked_range<T>()
    {}
    UT_BlockedRange(T begin_value, T end_value, size_t grainsize=1)
        : tbb::blocked_range<T>(begin_value, end_value, grainsize)
    {}
    UT_BlockedRange(UT_BlockedRange &R, UT_Split split)
        : tbb::blocked_range<T>(R, split)
    {}
};

/// UT_BlockedRange2D() is a simple wrapper using tbb for its implementation
/// This meets the requirements for a Range object, which are:
///  - @code Range::Range(const Range&); @endcode @n
///     Copy constructor
///  - @code Range::~Range(); @endcode @n
///     Destructor
///  - @code bool Range::is_divisible() const; @endcode @n
///     True if the range can be partitioned into two sub-ranges
///  - @code bool Range::empty() const; @endcode @n
///     True if the range is empty
///  - @code Range::Range(Range &r, UT_Split) const; @endcode @n
///     Split the range @c r into two sub-ranges (i.e. modify @c r and *this)
template <typename T_ROW, typename T_COL>
class UT_BlockedRange2D : public tbb::blocked_range2d<T_ROW, T_COL>
{
public:
    UT_BlockedRange2D()
        : tbb::blocked_range2d<T_ROW, T_COL>()
    {}
    /// NB:  The arguments are in a different order than tbb
    UT_BlockedRange2D(T_ROW row_begin, T_ROW row_end,
                      T_COL col_begin, T_COL col_end,
                      size_t row_grainsize=1, size_t col_grainsize=1)
        : tbb::blocked_range2d<T_ROW, T_COL>(row_begin, row_end, row_grainsize,
                                col_begin, col_end, col_grainsize)
    {}
    UT_BlockedRange2D(UT_BlockedRange2D &R, UT_Split split)
        : tbb::blocked_range2d<T_ROW, T_COL>(R, split)
    {}
};

#endif

---