Skip to main content Link Menu Expand (external link) Document Search Copy Copied

Prefix Sums

Groups

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator> __host__ __device__ OutputIterator thrust::inclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result);
template <typename InputIterator,   typename OutputIterator> OutputIterator thrust::inclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result);
template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename AssociativeOperator> __host__ __device__ OutputIterator thrust::inclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   AssociativeOperator binary_op);
template <typename InputIterator,   typename OutputIterator,   typename AssociativeOperator> OutputIterator thrust::inclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   AssociativeOperator binary_op);
template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator> __host__ __device__ OutputIterator thrust::exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result);
template <typename InputIterator,   typename OutputIterator> OutputIterator thrust::exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result);
template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename T> __host__ __device__ OutputIterator thrust::exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   T init);
template <typename InputIterator,   typename OutputIterator,   typename T> OutputIterator thrust::exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   T init);
template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename T,   typename AssociativeOperator> __host__ __device__ OutputIterator thrust::exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   T init,   AssociativeOperator binary_op);
template <typename InputIterator,   typename OutputIterator,   typename T,   typename AssociativeOperator> OutputIterator thrust::exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   T init,   AssociativeOperator binary_op);

Functions

Function thrust::inclusive_scan

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator> __host__ __device__ OutputIterator inclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result); inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, *first is assigned to *result and the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. This version of inclusive_scan assumes plus as the associative operator.

When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use inclusive_scan to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::inclusive_scan(thrust::host, data, data + 6, data); // in-place scan

// data is now {1, 1, 3, 5, 6, 9}

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined. If T is OutputIterator'svalue_type, then T(0) is defined.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::inclusive_scan

template <typename InputIterator,   typename OutputIterator> OutputIterator inclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result); inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. More precisely, *first is assigned to *result and the sum of *first and *(first + 1) is assigned to *(result + 1), and so on. This version of inclusive_scan assumes plus as the associative operator.

When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use inclusive_scan

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::inclusive_scan(data, data + 6, data); // in-place scan

// data is now {1, 1, 3, 5, 6, 9}

Template Parameters:

  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined. If T is OutputIterator'svalue_type, then T(0) is defined.

Function Parameters:

  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::inclusive_scan

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename AssociativeOperator> __host__ __device__ OutputIterator inclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   AssociativeOperator binary_op); inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use inclusive_scan to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::inclusive_scan(thrust::host, data, data + 10, data, binary_op); // in-place scan

// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator and OutputIterator'svalue_type is convertible to both AssociativeOperator'sfirst_argument_type and second_argument_type.
  • AssociativeOperator is a model of Binary Function and AssociativeOperator'sresult_type is convertible to OutputIterator'svalue_type.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • binary_op The associatve operator used to ‘sum’ values.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::inclusive_scan

template <typename InputIterator,   typename OutputIterator,   typename AssociativeOperator> OutputIterator inclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   AssociativeOperator binary_op); inclusive_scan computes an inclusive prefix sum operation. The term ‘inclusive’ means that each result includes the corresponding input operand in the partial sum. When the input and output sequences are the same, the scan is performed in-place.

inclusive_scan is similar to std::partial_sum in the STL. The primary difference between the two functions is that std::partial_sum guarantees a serial summation order, while inclusive_scan requires associativity of the binary operation to parallelize the prefix sum.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use inclusive_scan

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::inclusive_scan(data, data + 10, data, binary_op); // in-place scan

// data is now {-5, 0, 2, 2, 2, 4, 4, 4, 4, 8}

Template Parameters:

  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator and OutputIterator'svalue_type is convertible to both AssociativeOperator'sfirst_argument_type and second_argument_type.
  • AssociativeOperator is a model of Binary Function and AssociativeOperator'sresult_type is convertible to OutputIterator'svalue_type.

Function Parameters:

  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • binary_op The associatve operator used to ‘sum’ values.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator> __host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, 0 is assigned to *result and the sum of 0 and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator and 0 as the initial value. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use exclusive_scan to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>
...

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(thrust::host, data, data + 6, data); // in-place scan

// data is now {0, 1, 1, 3, 5, 6}

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined. If T is OutputIterator'svalue_type, then T(0) is defined.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename InputIterator,   typename OutputIterator> OutputIterator exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, 0 is assigned to *result and the sum of 0 and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator and 0 as the initial value. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use exclusive_scan

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(data, data + 6, data); // in-place scan

// data is now {0, 1, 1, 3, 5, 6}

Template Parameters:

  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined. If T is OutputIterator'svalue_type, then T(0) is defined.

Function Parameters:

  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename T> __host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   T init); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the sum of init and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator but requires an initial value init. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use exclusive_scan to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/execution_policy.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(thrust::host, data, data + 6, data, 4); // in-place scan

// data is now {4, 5, 5, 7, 9, 10}

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined.
  • T is convertible to OutputIterator'svalue_type.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • init The initial value.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename InputIterator,   typename OutputIterator,   typename T> OutputIterator exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   T init); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the sum of init and *first is assigned to *(result + 1), and so on. This version of exclusive_scan assumes plus as the associative operator but requires an initial value init. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use exclusive_scan

#include <thrust/scan.h>

int data[6] = {1, 0, 2, 2, 1, 3};

thrust::exclusive_scan(data, data + 6, data, 4); // in-place scan

// data is now {4, 5, 5, 7, 9, 10}

Template Parameters:

  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator, and if x and y are objects of OutputIterator'svalue_type, then x + y is defined.
  • T is convertible to OutputIterator'svalue_type.

Function Parameters:

  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • init The initial value.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename DerivedPolicy,   typename InputIterator,   typename OutputIterator,   typename T,   typename AssociativeOperator> __host__ __device__ OutputIterator exclusive_scan(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   InputIterator first,   InputIterator last,   OutputIterator result,   T init,   AssociativeOperator binary_op); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the value binary_op(init, *first) is assigned to *(result + 1), and so on. This version of the function requires both an associative operator and an initial value init. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use exclusive_scan to compute an in-place prefix sum using the thrust::host execution policy for parallelization:

#include <thrust/scan.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::exclusive_scan(thrust::host, data, data + 10, data, 1, binary_op); // in-place scan

// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator and OutputIterator'svalue_type is convertible to both AssociativeOperator'sfirst_argument_type and second_argument_type.
  • T is convertible to OutputIterator'svalue_type.
  • AssociativeOperator is a model of Binary Function and AssociativeOperator'sresult_type is convertible to OutputIterator'svalue_type.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • init The initial value.
  • binary_op The associatve operator used to ‘sum’ values.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum

Function thrust::exclusive_scan

template <typename InputIterator,   typename OutputIterator,   typename T,   typename AssociativeOperator> OutputIterator exclusive_scan(InputIterator first,   InputIterator last,   OutputIterator result,   T init,   AssociativeOperator binary_op); exclusive_scan computes an exclusive prefix sum operation. The term ‘exclusive’ means that each result does not include the corresponding input operand in the partial sum. More precisely, init is assigned to *result and the value binary_op(init, *first) is assigned to *(result + 1), and so on. This version of the function requires both an associative operator and an initial value init. When the input and output sequences are the same, the scan is performed in-place.

Results are not deterministic for pseudo-associative operators (e.g., addition of floating-point types). Results for pseudo-associative operators may vary from run to run.

The following code snippet demonstrates how to use exclusive_scan

#include <thrust/scan.h>
#include <thrust/functional.h>

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};

thrust::maximum<int> binary_op;

thrust::exclusive_scan(data, data + 10, data, 1, binary_op); // in-place scan

// data is now {1, 1, 1, 2, 2, 2, 4, 4, 4, 4 }

Template Parameters:

  • InputIterator is a model of Input Iterator and InputIterator'svalue_type is convertible to OutputIterator'svalue_type.
  • OutputIterator is a model of Output Iterator and OutputIterator'svalue_type is convertible to both AssociativeOperator'sfirst_argument_type and second_argument_type.
  • T is convertible to OutputIterator'svalue_type.
  • AssociativeOperator is a model of Binary Function and AssociativeOperator'sresult_type is convertible to OutputIterator'svalue_type.

Function Parameters:

  • first The beginning of the input sequence.
  • last The end of the input sequence.
  • result The beginning of the output sequence.
  • init The initial value.
  • binary_op The associatve operator used to ‘sum’ values.

Preconditions: first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

Returns: The end of the output sequence.

See: https://en.cppreference.com/w/cpp/algorithm/partial_sum