[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]
Summary
Requirements for a type that decides if a range ( 3.2 ) should be operated over by a task body or if the range should be further split.
Requirements
Table 6 lists the requirements for a Partitioner type P.
Table 6: Partitioner Concept
Pseudo-Signature
Semantics
P::~P()
Destructor
template <typename Range>
bool P::should_execute_range(const Range &r, const task &t)
True if r should be passed to the body of t. False if r should instead be split.
P::P( P& p, split )
Split p into two partitioners.
Description
The Partitioner concept implements rules for deciding when a given range should no longer be subdivided, but should be operated over as a whole by a task’s body.
The default behavior of the algorithms parallel_for (3.4), parallel_reduce (3.5) and parallel_scan (3.6) is to recursively split a range until no subrange remains that is divisible, as decided by the function is_divisible of the Range concept (3.2). The Partitioner concept models rules for the early termination of the recursive splitting of a range, providing ability to change the default behavior. A Partitioner object’s decision making is implemented using two functions, a splitting constructor and the function should_execute_range.
Within the parallel algorithms, each Range object is now associated with a Partitioner object. Whenever a Range object is split using its splitting constructor to create two subranges, the associated Partitioner object is likewise split to create two matching Partitioner objects.
When a parallel_for, parallel_reduce or parallel_scan algorithm needs to decide whether to further subdivide a range, it invokes the function should_execute_range for the Partitioner object associated with the range. If the function should_execute_range returns true for the given range and task, then no further splits are performed on the range and the current task applies its body over the entire range.
Example
The following code defines a type simple_partitioner that models the Partitioner concept. It returns true from its function should_execute_range if the range function is_divisible returns false.
class simple_partitioner {
public:
simple_partitioner() {}
simple_partitioner(simple_partitioner &partitioner,
split) {}
template <typename Range>
inline bool should_execute_range(const Range &r, const task &t) {
return ( !r.is_divisible() );
}
};
This class encodes the default behavior, where a range is recursively split until it cannot be further subdivided.
Model Types
simple_partitioner ( 3.3.1 ) models the default behavior of splitting a range until it cannot be further subdivided.
auto_partitioner ( 3.3.2) models an adaptive behavior that monitors the work-stealing actions of the task_scheduler ( 8) to reduce the number of splits performed.
Summary
A class that models that default range splitting behavior of the parallel_for ( 3.4), parallel_reduce ( 3.5) and parallel_scan ( 3.6) algorithms, where a range is recursively split until it cannot be further subdivided.
Syntax
class simple_partitioner;
Header
#include "tbb/partitioner.h"
Description
The class simple_partitioner models the default range splitting behavior of the parallel_for, parallel_reduce and parallel_scan algorithms.
3.3.1.1 simple_partitioner()
An empty default constructor.
3.3.1.2 simple_partitioner(simple_partitioner &partitioner, split )
An empty splitting constructor.
3.3.1.3 template<typename Range> bool should_execute_range (const Range &r, const task &t)
A function that returns true when the provided range should be executed to completion by the given task. It returns !range.is_divisible().
Summary
A class that models an adaptive partitioner that monitors the work-stealing actions of the task_scheduler to manage the number of splits performed.
Syntax
class auto_partitioner;
Header
#include "tbb/partitioner.h"
Description
The class auto_partitioner models an adaptive partitioner that limits the number of splits needed for load balancing by reacting to work-stealing events.
The range is first divided into SI subranges, where SI is proportional to the number of threads created by the task scheduler. These subranges are executed to completion by tasks unless they are stolen. If a subrange is stolen by an idle thread, the auto_partitioner further subdivides the range to create additional subranges.
The auto_partitioner creates additional subranges only if threads are actively stealing work. If the load is well balanced, the use of only a few large initial subranges reduces the overheads incurred when splitting and joining ranges. However, if there is a load imbalance that results in work-stealing, the auto_partitioner creates additional subranges that can be stolen to more finely balance the load.
The auto_partitioner therefore attempts to minimize the number of range splits, while providing ample opportunities for work-stealing.
3.3.2.1 auto_partitioner()
An empty default constructor.
3.3.2.2 auto_partitioner(auto_partitioner &partitioner, split )
A splitting constructor that divides the auto_partitioner partitioner into two partitioners.
3.3.2.3 template<typename Range> bool should_execute_range (const Range &r, const task &t)
A function that returns true when the provided range should be operated over as a whole by the given task’s body. This function may return true even if range.is_divisible() == true and always returns true if range.is_divisible() == false. That is, this function may decide that t should process an r that can be further subdivided, but it always decides that t should process an r that cannot be further subdivided.
[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]