Intel Threading Building Blocks

Name

parallel_scan<Range,Body> Template Function — Template function that computes parallel prefix.

Synopsis

#include "tbb/parallel_scan.h"

template<typename Range, typename Body>

  void parallel_scan( const Range& range, Body& body );

template<typename Range, typename Body, typename Partitioner>

    void parallel_scan( const Range& range, Body& body,

                            Partitioner &partitioner );

Description

A parallel_scan<Range,Body> computes a parallel prefix, also known as a parallel scan. This can be useful in scenarios that appear to have inherently serial dependencies. Given an associative operation ⊕ with left-identity element id⊕, the parallel prefix of ⊕ over a sequence x₀, x₁ , … x_{n − 1} is a sequence y₀, y₁, y₂ , … y_{n − 1} , where y₀ = ^{id ⊕} ⊕ x0 and yi = yi − 1 ⊕ xi .

The template parallel_scan<Range,Body> implements a parallel prefix generically. The body must model the requirements in Table 3-8.

Table 3-8. parallel_scan requirements

Pseudosignature	Semantics
void Body::operator()( constRange&r, pre_scan_tag )	Preprocess iterations for range r.
void Body::operator()( constRange&r, final_scan_tag )	Do final processing for iterations of range r.
Body::Body( Body&b, split )	Split bso that this and bcan accumulate separately.
VoidBody::reverse_join( Body&a )	Merge preprocessing state of ainto this, where awas created earlier from bby b’s splitting constructor.
VoidBody::assign( Body&b )	Assign state of bto this.