thrust
Modules | Functions
Prefix Sums

Modules

 Segmented Prefix Sums
 
 Transformed Prefix Sums
 

Functions

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)
 

Detailed Description

Function Documentation

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 
)

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.

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

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
Returns
The end of the output sequence.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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>
...
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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
template<typename InputIterator , typename OutputIterator >
OutputIterator thrust::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.

Parameters
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
Returns
The end of the output sequence.
Template Parameters
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
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,
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.

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

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
initThe initial value.
Returns
The end of the output sequence.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined.
Tis convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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>
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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
template<typename InputIterator , typename OutputIterator , typename T >
OutputIterator thrust::exclusive_scan ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
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.

Parameters
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
initThe initial value.
Returns
The end of the output sequence.
Template Parameters
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined.
Tis convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
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,
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 and associative operator and an initial value init. When the input and output sequences are the same, the scan is performed in-place.

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

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
initThe initial value.
binary_opThe associatve operator used to 'sum' values.
Returns
The end of the output sequence.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.
Tis convertible to OutputIterator's value_type.
AssociativeOperatoris a model of Binary Function and AssociativeOperator's result_type is convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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>
...
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
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 }
See Also
http://www.sgi.com/tech/stl/partial_sum.html
template<typename InputIterator , typename OutputIterator , typename T , typename AssociativeOperator >
OutputIterator thrust::exclusive_scan ( InputIterator  first,
InputIterator  last,
OutputIterator  result,
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 and associative operator and an initial value init. When the input and output sequences are the same, the scan is performed in-place.

Parameters
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
initThe initial value.
binary_opThe associatve operator used to 'sum' values.
Returns
The end of the output sequence.
Template Parameters
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.
Tis convertible to OutputIterator's value_type.
AssociativeOperatoris a model of Binary Function and AssociativeOperator's result_type is convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

The following code snippet demonstrates how to use exclusive_scan

#include <thrust/scan.h>
int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
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 }
See Also
http://www.sgi.com/tech/stl/partial_sum.html
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 
)

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.

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

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
Returns
The end of the output sequence.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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>
...
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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
template<typename InputIterator , typename OutputIterator >
OutputIterator thrust::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.

Parameters
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
Returns
The end of the output sequence.
Template Parameters
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator, and if x and y are objects of OutputIterator's value_type, then x + y is defined. If T is OutputIterator's value_type, then T(0) is defined.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
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 
)

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.

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

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
binary_opThe associatve operator used to 'sum' values.
Returns
The end of the output sequence.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.
AssociativeOperatoris a model of Binary Function and AssociativeOperator's result_type is convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

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::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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html
template<typename InputIterator , typename OutputIterator , typename AssociativeOperator >
OutputIterator thrust::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.

Parameters
firstThe beginning of the input sequence.
lastThe end of the input sequence.
resultThe beginning of the output sequence.
binary_opThe associatve operator used to 'sum' values.
Returns
The end of the output sequence.
Template Parameters
InputIteratoris a model of Input Iterator and InputIterator's value_type is convertible to OutputIterator's value_type.
OutputIteratoris a model of Output Iterator and OutputIterator's value_type is convertible to both AssociativeOperator's first_argument_type and second_argument_type.
AssociativeOperatoris a model of Binary Function and AssociativeOperator's result_type is convertible to OutputIterator's value_type.
Precondition
first may equal result but the range [first, last) and the range [result, result + (last - first)) shall not overlap otherwise.

The following code snippet demonstrates how to use inclusive_scan

int data[10] = {-5, 0, 2, -3, 2, 4, 0, -1, 2, 8};
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}
See Also
http://www.sgi.com/tech/stl/partial_sum.html