[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]
Summary
Requirements for type representing a recursively divisible set of values.
Requirements
lists the requirements for a Range type R. Table 4
Table 4: Range Concept
Pseudo-Signature
Semantics
R::R( const R& )
Copy constructor
R::~R()
Destructor
bool R::empty() const
True if range is empty
bool R::is_divisible() const
True if range can be partitioned into two subranges.
R::R( R& r, split )
Split r into two subranges.
Description
A Range can be recursively subdivided into two parts. It is recommended that the division be into nearly equal parts, but it is not required. Splitting as evenly as possible typically yields the best parallelism. Ideally, a range is recursively splittable until the parts represent portions of work that are more efficient to execute serially rather than split further. The amount of work represented by a Range typically depends upon higher level context, hence a typical type that models a Range should provide a way to control the degree of splitting. For example, the template class blocked_range ( 3.2.1 ) has a grainsize parameter that specifies the biggest range considered indivisible.
The constructor that implements splitting is called a splitting constructor. If the set of values has a sense of direction, then by convention the splitting constructor should construct the second part of the range, and update the argument to be the first half. Following this convention causes the parallel_for ( 3.4 ), parallel_reduce ( 3.5 ), and parallel_scan ( 3.6 ) algorithms, when running sequentially, to work across a range in the increasing order typical of an ordinary sequential loop.
Example
The following code defines a type TrivialIntegerRange that models the Range concept. It represents a half-open interval [lower,upper) that is divisible down to a single integer.
struct TrivialIntegerRange {
int lower;
int upper;
bool empty() const {return lower==upper;}
bool is_divisible() const {return upper>lower+1;}
TrivialIntegerRange( TrivialIntegerRange& r, split ) {
int m = (r.lower+r.upper)/2;
lower = m;
upper = r.upper;
r.upper = m;
}
};
TrivialIntegerRange is for demonstration and not very practical, because it lacks a grainsize parameter. Use the library class blocked_range instead.
Model Types
blocked_range ( 3.2.1 ) models a one-dimensional range.
blocked_range2d ( 3.2.2 ) models a two-dimensional range.
Summary
Template class for a recursively divisible half-open interval.
TIP: For a blocked_range [i,j) where j<i, not all methods have specified behavior. However, enough methods do have specified behavior that parallel_for ( 3.4 ), parallel_reduce ( 3.5 ), and parallel_scan ( 3.6 ) iterate over the same iteration space as the serial loop for( Value index=i; index<j; ++index )... , even when j<i. If TBB_DO_ASSERT ( 2.6.1 ) is nonzero, methods with unspecified behavior raise an assertion failure.
Examples
A blocked_range<Value> typically appears as a range argument to a loop template. See the examples for parallel_for ( 3.4 ), parallel_reduce ( 3.5 ), and parallel_scan ( 3.6 ).
Members
namespace tbb {
template<typename Value>
class blocked_range {
public:
// types
typedef size_t size_type;
typedef Value const_iterator;
// constructors
blocked_range( Value begin, Value end, size_type grainsize=1);
blocked_range( blocked_range& r, split );
// capacity
size_type size() const;
bool empty() const;
// access
size_type grainsize() const;
bool is_divisible() const;
// iterators
const_iterator begin() const;
const_iterator end() const;
};
}
3.2.1.1 size_type
Description
The type for measuring the size of a blocked_range. The type is always a size_t.
const_iterator
Description
The type of a value in the range. Despite its name, the type const_iterator is not necessarily an STL iterator; it merely needs to meet the Value requirements in Table
const size_t N = 300;
void SerialMatrixMultiply( float c[M][N], float a[M][L], float b[L][N] ) {
for( size_t i=0; i<M; ++i ) {
for( size_t j=0; j<N; ++j ) {
float sum = 0;
for( size_t k=0; k<L; ++k )
sum += a[i][k]*b[k][j];
c[i][j] = sum;
}
}
}
#include "tbb/parallel_for.h"
#include "tbb/blocked_range2d.h"
using namespace tbb;
const size_t L = 150;
const size_t M = 225;
const size_t N = 300;
class MatrixMultiplyBody2D {
float (*my_a)[L];
float (*my_b)[N];
float (*my_c)[N];
public:
void operator()( const blocked_range2d<size_t>& r ) const {
float (*a)[L] = my_a;
float (*b)[N] = my_b;
float (*c)[N] = my_c;
for( size_t i=r.rows().begin(); i!=r.rows().end(); ++i ){
for( size_t j=r.cols().begin(); j!=r.cols().end(); ++j ) {
float sum = 0;
for( size_t k=0; k<L; ++k )
sum += a[i][k]*b[k][j];
c[i][j] = sum;
}
}
}
MatrixMultiplyBody2D( float c[M][N], float a[M][L], float b[L][N] ) :
my_a(a), my_b(b), my_c(c)
{}
};
void ParallelMatrixMultiply(float c[M][N], float a[M][L], float b[L][N]){
parallel_for( blocked_range2d<size_t>(0, M, 16, 0, N, 32),
MatrixMultiplyBody2D(c,a,b) );
}
The blocked_range2d enables the two outermost loops of the serial version to become parallel loops. The parallel_for recursively splits the blocked_range2d until
3.2.2.5 bool empty() const
Effects
Determines if range is empty.
Returns
rows().empty()||cols().empty()
3.2.2.6 bool is_divisible() const
Effects
Determine if range can be split into subranges.
Returns
rows().is_divisible()||cols().is_divisible()
3.2.2.7 const row_range_type& rows() const
Returns
Range containing the rows of the value space.
3.2.2.8 const col_range_type& cols() const
Returns
Range containing the columns of the value space.
[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]