Embedded Multicore Building Blocks V1.0.0
Functions

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...
 

Detailed Description

Parallel scan computation.

Function Documentation

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.

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.

Exceptions
embb::base::ErrorExceptionif not enough MTAPI tasks can be created to satisfy the requirements of the algorithm.
Concurrency
Thread-safe if the elements in the range are not modified by another thread while the algorithm is executed.
Note
No guarantee is given on the order in which the functions scan and transformation are applied to the elements.
For all x of type ReturnType it must hold that reduction(x, neutral) == x.
The reduction operation need not be commutative but must be associative, i.e., reduction(x, reduction(y, z)) == reduction(reduction(x, y), z)) for all x, y, z of type ReturnType.
For nested algorithms, the task limit may be exceeded. In that case, increase the task limit of the MTAPI node.
See also
embb::mtapi::ExecutionPolicy, Identity, ZipIterator
Template Parameters
RAIInRandom access iterator type of input range
RAIOutRandom access iterator type of output range
ReturnTypeType of output elements of scan operation, deduced from neutral
ScanFunctionBinary 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.
TransformationFunctionUnary 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.
Parameters
[in]firstRandom access iterator pointing to the first element of the input range
[in]lastRandom access iterator pointing to the last plus one element of the input range
[in]output_firstRandom access iterator pointing to the first element of the output range
[in]neutralNeutral element of the scan operation.
[in]scanScan operation to be applied to the elements of the input range
[in]transformationTransforms the elements of the input range before the scan operation is applied
[in]policyembb::mtapi::ExecutionPolicy for the scan computation
[in]block_sizeLower 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.