CL-Segmented Prefix Sums

Functions
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	bolt::cl::inclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, const std::string &user_code="")
	inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), and the BinaryPredicate is equal_to(). inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	bolt::cl::inclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate >
OutputIterator	bolt::cl::inclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, const std::string &user_code="")
	inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(). inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate >
OutputIterator	bolt::cl::inclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate , typename BinaryFunction >
OutputIterator	bolt::cl::inclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, BinaryFunction binary_funct, const std::string &user_code="")
	inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys. inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate , typename BinaryFunction >
OutputIterator	bolt::cl::inclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryPredicate binary_pred, BinaryFunction binary_funct, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	bolt::cl::exclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, const std::string &user_code="")
	exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), the BinaryPredicate is equal_to(), and init is 0. exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >
OutputIterator	bolt::cl::exclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T >
OutputIterator	bolt::cl::exclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, const std::string &user_code="")
	exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), and the BinaryPredicate is equal_to(). exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T >
OutputIterator	bolt::cl::exclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate >
OutputIterator	bolt::cl::exclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, const std::string &user_code="")
	exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(). exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate >
OutputIterator	bolt::cl::exclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, const std::string &user_code="")
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate , typename BinaryFunction >
OutputIterator	bolt::cl::exclusive_scan_by_key (control &ctl, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, BinaryFunction binary_funct, const std::string &user_code="")
	exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys. exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.
template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate , typename BinaryFunction >
OutputIterator	bolt::cl::exclusive_scan_by_key (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, T init, BinaryPredicate binary_pred, BinaryFunction binary_funct, const std::string &user_code="")

Detailed Description

Function Documentation

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator bolt::cl::exclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		const std::string &	user_code = ""
	)

exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), the BinaryPredicate is equal_to(), and init is 0. exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 1, 1, 1, 1, 1, 1,  1,  1,  1,  1, 1 };
int out[11];

bolt::cl::control ctrl = control::getDefault();

bolt::cl::exclusive_scan_by_key( ctrl, keys, keys+11, vals, out );
// out => { 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0 }

See Also

exclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T >

OutputIterator bolt::cl::exclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		T	init,
		const std::string &	user_code = ""
	)

exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), and the BinaryPredicate is equal_to(). exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
init	The value used to initialize the output scan sequence.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.
T	is convertible to OutputIterator's value_type.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 1, 1, 1, 1, 1, 1,  1,  1,  1,  1, 1 };
int out[11];

bolt::cl::control ctrl = control::getDefault();

bolt::cl::exclusive_scan_by_key( ctrl, keys, keys+11, vals, out, 0 );
// out => { 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0 }

See Also

exclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate >

OutputIterator bolt::cl::exclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		T	init,
		BinaryPredicate	binary_pred,
		const std::string &	user_code = ""
	)

exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(). exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
init	The value used to initialize the output scan sequence.
binary_pred	Binary predicate which determines if two keys are equal.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.
T	is convertible to OutputIterator's value_type.
BinaryPredicate	is a model of Binary Predicate.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 1, 1, 1, 1, 1, 1,  1,  1,  1,  1, 1 };
int out[11];

bolt::cl::equal_to<int> eq;
bolt::cl::control ctrl = control::getDefault();

bolt::cl::exclusive_scan_by_key( ctrl, keys, keys+11, vals, out, 1, eq );
// out => { 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1 }

See Also

exclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename T , typename BinaryPredicate , typename BinaryFunction >

OutputIterator bolt::cl::exclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		T	init,
		BinaryPredicate	binary_pred,
		BinaryFunction	binary_funct,
		const std::string &	user_code = ""
	)

exclusive_scan_by_key performs, on a sequence, an exclusive scan of each sub-sequence as defined by equivalent keys. exclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
init	The value used to initialize the output scan sequence.
binary_pred	Binary predicate which determines if two keys are equal.
binary_funct	Binary function for scanning transformed elements.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.
T	is convertible to OutputIterator's value_type.
BinaryPredicate	is a model of Binary Predicate.
BinaryFunction	is a model of Binary Function whose return type is convertible to OutputIterator's value_type.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 2, 2, 2, 2, 2, 2,  2,  2,  2,  2, 2 };
int out[11];

bolt::cl::equal_to<int> eq;
bolt::cl::multiplies<int> mult;
bolt::cl::control ctrl = control::getDefault();

bolt::cl::exclusive_scan_by_key( ctrl, keys, keys+11, vals, out, 1, eq, mult );
// out => { 1, 1, 2, 1, 2, 4, 1, 2, 4, 8, 1 }

See Also

exclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator >

OutputIterator bolt::cl::inclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		const std::string &	user_code = ""
	)

inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(), and the BinaryPredicate is equal_to(). inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc.See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.

Returns

result+(last1-first1).

Example

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 1, 1, 1, 1, 1, 1,  1,  1,  1,  1, 1 };
int out[11];

bolt::cl::control ctrl = control::getDefault();

bolt::cl::inclusive_scan_by_key( ctrl, keys, keys+11, vals, out );
// out => { 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1 }

See Also

inclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate >

OutputIterator bolt::cl::inclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		BinaryPredicate	binary_pred,
		const std::string &	user_code = ""
	)

inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys; the BinaryFunction in this version is plus(). inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
binary_pred	Binary predicate which determines if two keys are equal.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.
BinaryPredicate	is a model of Binary Predicate.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 1, 1, 1, 1, 1, 1,  1,  1,  1,  1, 1 };
int out[11];

bolt::cl::equal_to<int> eq;
bolt::cl::control ctrl = control::getDefault();

bolt::cl::inclusive_scan_by_key( ctrl, keys, keys+11, vals, out, eq );
// out => { 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1 }

See Also

inclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html

template<typename InputIterator1 , typename InputIterator2 , typename OutputIterator , typename BinaryPredicate , typename BinaryFunction >

OutputIterator bolt::cl::inclusive_scan_by_key	(	control &	ctl,
		InputIterator1	first1,
		InputIterator1	last1,
		InputIterator2	first2,
		OutputIterator	result,
		BinaryPredicate	binary_pred,
		BinaryFunction	binary_funct,
		const std::string &	user_code = ""
	)

inclusive_scan_by_key performs, on a sequence, an inclusive scan of each sub-sequence as defined by equivalent keys. inclusive_scan_by_key uses the associative operator binary_op to perform the parallel segmented prefix sum.

Parameters

ctl	Optional Control structure to control command-queue, debug, tuning, etc. See bolt::cl::control.
first1	The first element of the key sequence.
last1	The last element of the key sequence.
first2	The first element of the value sequence.
result	The first element of the output sequence.
binary_pred	Binary predicate which determines if two keys are equal.
binary_funct	Binary function for scanning transformed elements.
user_code	A user-specified string that is preppended to the generated OpenCL kernel.

Template Parameters

InputIterator1	is a model of Input Iterator.
InputIterator2	is a model of Input Iterator.
OutputIterator	is a model of Output Iterator.
BinaryPredicate	is a model of Binary Predicate.
BinaryFunction	is a model of Binary Function whose return type is convertible to OutputIterator's value_type.

Returns

result+(last1-first1).

#include "bolt/cl/scan_by_key.h"
...

int keys[11] = { 7, 0, 0, 3, 3, 3, -5, -5, -5, -5, 3 };
int vals[11] = { 2, 2, 2, 2, 2, 2,  2,  2,  2,  2, 2 };
int out[11];

bolt::cl::equal_to<int> eq;
bolt::cl::multiplies<int> mult;
bolt::cl::control ctrl = control::getDefault();

bolt::cl::inclusive_scan_by_key( ctrl, keys, keys+11, vals, out, eq, mult );
// out => { 2, 2, 4, 2, 4, 8, 2, 4, 8, 16, 2 }

See Also

inclusive_scan

http://www.sgi.com/tech/stl/partial_sum.html

http://www.sgi.com/tech/stl/InputIterator.html

http://www.sgi.com/tech/stl/OutputIterator.html

http://www.sgi.com/tech/stl/BinaryPredicate.html

http://www.sgi.com/tech/stl/BinaryFunction.html