Embedded Multicore Building Blocks V1.0.0
|
Parallel scan computation. More...
Functions | |
template<typename RAIIn , typename RAIOut , typename ReturnType , typename ScanFunction , typename TransformationFunction > | |
void | embb::algorithms::Scan (RAIIn first, RAIIn last, RAIOut output_first, ReturnType neutral, ScanFunction scan, TransformationFunction transformation=Identity(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0) |
Performs a parallel scan (or prefix) computation on a range of elements. More... | |
Parallel scan computation.
void embb::algorithms::Scan | ( | RAIIn | first, |
RAIIn | last, | ||
RAIOut | output_first, | ||
ReturnType | neutral, | ||
ScanFunction | scan, | ||
TransformationFunction | transformation = Identity() , |
||
const embb::mtapi::ExecutionPolicy & | policy = embb::mtapi::ExecutionPolicy() , |
||
size_t | block_size = 0 |
||
) |
Performs a parallel scan (or prefix) computation on a range of elements.
The algorithm reads an input range and writes its result to a separate output range. The input range consists of the elements from first
to last
, excluding the last element. The output range consists of the elements from output_first
to output_first + std::difference(last - first)
.
The algorithm performs two runs on the given range. Hence, a performance speedup can only be expected on processors with more than two cores.
embb::base::ErrorException | if not enough MTAPI tasks can be created to satisfy the requirements of the algorithm. |
scan
and transformation
are applied to the elements.x
of type ReturnType
it must hold that reduction(x, neutral) == x
. reduction(x, reduction(y, z)) == reduction(reduction(x, y), z))
for all x
, y
, z
of type ReturnType
.RAIIn | Random access iterator type of input range |
RAIOut | Random access iterator type of output range |
ReturnType | Type of output elements of scan operation, deduced from neutral |
ScanFunction | Binary scan function object with signature ReturnType ScanFunction(ReturnType, ReturnType) or an embb::mtapi::Job associated with an action function accepting a struct containing two ReturnType members as its argument buffer and a struct containing one ReturnType member as its result buffer. |
TransformationFunction | Unary transformation function object with signature ReturnType TransformationFunction(typename std::iterator_traits<RAIIn>::value_type) or an embb::mtapi::Job associated with an action function accepting a struct containing one InputType member as its argument buffer and a struct containing one ReturnType member as its result buffer. |
[in] | first | Random access iterator pointing to the first element of the input range |
[in] | last | Random access iterator pointing to the last plus one element of the input range |
[in] | output_first | Random access iterator pointing to the first element of the output range |
[in] | neutral | Neutral element of the scan operation. |
[in] | scan | Scan operation to be applied to the elements of the input range |
[in] | transformation | Transforms the elements of the input range before the scan operation is applied |
[in] | policy | embb::mtapi::ExecutionPolicy for the scan computation |
[in] | block_size | Lower bound for partitioning the range of elements into blocks that are treated in parallel. Partitioning of a block stops if its size is less than or equal to block_size . The default value 0 means that the minimum block size is determined automatically depending on the number of elements in the range divided by the number of available cores. |