Parallel Primitives

Detailed Description

This module provides a set of convenience wrappers to invoke system-wide CUB's parallel primitives without worrying about the memory management. All temporary storage is in fact allocated within a single thrust::system_vector passed by the user, which can be safely reused across function calls.

Classes
struct	nvbio::for_each_enactor< system_tag >
struct	nvbio::for_each_enactor< device_tag >

Functions
template<typename system_tag , typename PredicateIterator >
bool	nvbio::any (const uint32 n, const PredicateIterator pred)
template<typename system_tag , typename PredicateIterator >
bool	nvbio::all (const uint32 n, const PredicateIterator pred)
template<typename system_tag , typename Iterator >
bool	nvbio::is_sorted (const uint32 n, const Iterator values)
template<typename system_tag , typename Iterator , typename Headflags >
bool	nvbio::is_segment_sorted (const uint32 n, const Iterator values, const Headflags flags)
template<typename system_tag , typename Iterator , typename Functor >
void	nvbio::for_each (const uint64 n, const Iterator in, Functor functor)
template<typename system_tag , typename Iterator , typename Output , typename Functor >
void	nvbio::transform (const uint32 n, const Iterator in, const Output out, const Functor functor)
template<typename system_tag , typename Iterator1 , typename Iterator2 , typename Output , typename Functor >
void	nvbio::transform (const uint32 n, const Iterator1 in1, const Iterator2 in2, const Output out, const Functor functor)
template<typename system_tag , typename InputIterator , typename BinaryOp >
std::iterator_traits < InputIterator >::value_type	nvbio::reduce (const uint32 n, InputIterator in, BinaryOp op, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename InputIterator , typename OutputIterator , typename BinaryOp >
void	nvbio::inclusive_scan (const uint32 n, InputIterator in, OutputIterator out, BinaryOp op, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename InputIterator , typename OutputIterator , typename BinaryOp , typename Identity >
void	nvbio::exclusive_scan (const uint32 n, InputIterator in, OutputIterator out, BinaryOp op, Identity identity, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename InputIterator , typename FlagsIterator , typename OutputIterator >
uint32	nvbio::copy_flagged (const uint32 n, InputIterator in, FlagsIterator flags, OutputIterator out, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename InputIterator , typename OutputIterator , typename Predicate >
uint32	nvbio::copy_if (const uint32 n, InputIterator in, OutputIterator out, const Predicate pred, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename InputIterator , typename OutputIterator , typename CountIterator >
uint32	nvbio::runlength_encode (const uint32 n, InputIterator in, OutputIterator out, CountIterator counts, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputKeyIterator , typename OutputValueIterator , typename ReductionOp >
uint32	nvbio::reduce_by_key (const uint32 n, KeyIterator keys_in, ValueIterator values_in, OutputKeyIterator keys_out, OutputValueIterator values_out, ReductionOp reduction_op, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputIterator >
void	nvbio::lower_bound (const uint32 n, ValueIterator values, const uint32 n_keys, KeyIterator keys, OutputIterator indices)
template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputIterator >
void	nvbio::upper_bound (const uint32 n, ValueIterator values, const uint32 n_keys, KeyIterator keys, OutputIterator indices)
template<typename system_tag , typename KeyIterator >
void	nvbio::radix_sort (const uint32 n, KeyIterator keys, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename KeyIterator , typename ValueIterator >
void	nvbio::radix_sort (const uint32 n, KeyIterator keys, ValueIterator values, nvbio::vector< system_tag, uint8 > &temp_storage)
template<typename system_tag , typename key_iterator1 , typename key_iterator2 , typename value_iterator1 , typename value_iterator2 , typename key_output , typename value_output >
void	nvbio::merge_by_key (const uint32 A_len, const uint32 B_len, const key_iterator1 A_keys, const key_iterator2 B_keys, const value_iterator1 A_values, const value_iterator2 B_values, key_output C_keys, value_output C_values, nvbio::vector< system_tag, uint8 > &temp_storage)

Function Documentation

template<typename system_tag , typename PredicateIterator >

bool nvbio::all	(	const uint32	n,
		const PredicateIterator	pred
	)

return true if all items in the range [0,n) evaluate to true

Definition at line 101 of file primitives_inl.h.

template<typename system_tag , typename PredicateIterator >

bool nvbio::any	(	const uint32	n,
		const PredicateIterator	pred
	)

return true if any item in the range [0,n) evaluates to true

Definition at line 91 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename FlagsIterator , typename OutputIterator >

uint32 nvbio::copy_flagged	(	const uint32	n,
		InputIterator	in,
		FlagsIterator	flags,
		OutputIterator	out,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide copy of flagged items

Parameters

n	number of input items
in	a system input iterator
flags	a system flags iterator
out	a system output iterator
temp_storage	some temporary storage

Returns

the number of copied items

Definition at line 817 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename OutputIterator , typename Predicate >

uint32 nvbio::copy_if	(	const uint32	n,
		InputIterator	in,
		OutputIterator	out,
		const Predicate	pred,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide copy of predicated items

Parameters

n	number of input items
in	a system input iterator
out	a system output iterator
pred	a unary predicate functor
temp_storage	some temporary storage

Returns

the number of copied items

Definition at line 838 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename OutputIterator , typename BinaryOp , typename Identity >

void nvbio::exclusive_scan	(	const uint32	n,
		InputIterator	in,
		OutputIterator	out,
		BinaryOp	op,
		Identity	identity,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide exclusive scan

Parameters

n	number of items to reduce
in	a system input iterator
out	a system output iterator
op	the binary reduction operator
identity	the identity element
temp_storage	some temporary storage

Definition at line 569 of file primitives_inl.h.

template<typename system_tag , typename Iterator , typename Functor >

void nvbio::for_each	(	const uint64	n,
		const Iterator	in,
		Functor	functor
	)

invoke a functor for each element of the given sequence

Definition at line 284 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename OutputIterator , typename BinaryOp >

void nvbio::inclusive_scan	(	const uint32	n,
		InputIterator	in,
		OutputIterator	out,
		BinaryOp	op,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide inclusive scan

Parameters

n	number of items to reduce
in	a system input iterator
out	a system output iterator
op	the binary reduction operator
temp_storage	some temporary storage

Definition at line 543 of file primitives_inl.h.

template<typename system_tag , typename Iterator , typename Headflags >

bool nvbio::is_segment_sorted	(	const uint32	n,
		const Iterator	values,
		const Headflags	flags
	)

return true if the items in the range [0,n) are sorted by segment, where the beginning of each segment is identified by a set head flag

Definition at line 245 of file primitives_inl.h.

template<typename system_tag , typename Iterator >

bool nvbio::is_sorted	(	const uint32	n,
		const Iterator	values
	)

return true if the items in the range [0,n) are sorted

Definition at line 234 of file primitives_inl.h.

template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputIterator >

void nvbio::lower_bound	(	const uint32	n,
		ValueIterator	values,
		const uint32	n_keys,
		KeyIterator	keys,
		OutputIterator	indices
	)

system-wide lower_bound

Parameters

n	number of input items
values	a system input iterator of values to be searched
n_keys	number of sorted keys
keys	a system input iterator of sorted keys
indices	a system output iterator

Definition at line 953 of file primitives_inl.h.

template<typename system_tag , typename key_iterator1 , typename key_iterator2 , typename value_iterator1 , typename value_iterator2 , typename key_output , typename value_output >

void nvbio::merge_by_key	(	const uint32	A_len,
		const uint32	B_len,
		const key_iterator1	A_keys,
		const key_iterator2	B_keys,
		const value_iterator1	A_values,
		const value_iterator2	B_values,
		key_output	C_keys,
		value_output	C_values,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

merge two sequences by key

Parameters

A_len	number of input items in the first sequence
B_len	number of input items in the second sequence
A_keys	a system input iterator of keys to be merged from the first sequence
B_keys	a system input iterator of keys to be merged from the second sequence
A_values	a system input iterator of values to be merged from the first sequence
B_values	a system input iterator of values to be merged from the second sequence
C_keys	a system output iterator to the final merged keys
C_values	a system output iterator of the final merged values
temp_storage	some temporary storage

Definition at line 1351 of file primitives_inl.h.

template<typename system_tag , typename KeyIterator >

void nvbio::radix_sort	(	const uint32	n,
		KeyIterator	keys,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide radix-sort

Parameters

n	number of input items
keys	a system input iterator of keys to be sorted
temp_storage	some temporary storage

Definition at line 1146 of file primitives_inl.h.

template<typename system_tag , typename KeyIterator , typename ValueIterator >

void nvbio::radix_sort	(	const uint32	n,
		KeyIterator	keys,
		ValueIterator	values,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide radix-sort by key

Parameters

n	number of input items
keys	a system input iterator of keys to be sorted
values	a system input iterator of values to be sorted
temp_storage	some temporary storage

Definition at line 1178 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename BinaryOp >

std::iterator_traits< InputIterator >::value_type nvbio::reduce	(	const uint32	n,
		InputIterator	in,
		BinaryOp	op,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide reduce

Parameters

n	number of items to reduce
in	a system iterator
op	the binary reduction operator
temp_storage	some temporary storage

Definition at line 520 of file primitives_inl.h.

template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputKeyIterator , typename OutputValueIterator , typename ReductionOp >

uint32 nvbio::reduce_by_key	(	const uint32	n,
		KeyIterator	keys_in,
		ValueIterator	values_in,
		OutputKeyIterator	keys_out,
		OutputValueIterator	values_out,
		ReductionOp	reduction_op,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide run-length encode

Parameters

n	number of input items
keys_in	a system input iterator
values_in	a system input iterator
keys_out	a system output iterator
values_out	a system output iterator
reduction_op	a reduction operator
temp_storage	some temporary storage

Returns

the number of copied items

Definition at line 882 of file primitives_inl.h.

template<typename system_tag , typename InputIterator , typename OutputIterator , typename CountIterator >

uint32 nvbio::runlength_encode	(	const uint32	n,
		InputIterator	in,
		OutputIterator	out,
		CountIterator	counts,
		nvbio::vector< system_tag, uint8 > &	temp_storage
	)

system-wide run-length encode

Parameters

n	number of input items
in	a system input iterator
out	a system output iterator
counts	a system output count iterator
temp_storage	some temporary storage

Returns

the number of copied items

Definition at line 859 of file primitives_inl.h.

template<typename system_tag , typename Iterator , typename Output , typename Functor >

void nvbio::transform	(	const uint32	n,
		const Iterator	in,
		const Output	out,
		const Functor	functor
	)

apply a functor to each element of the given sequence

Definition at line 357 of file primitives_inl.h.

template<typename system_tag , typename Iterator1 , typename Iterator2 , typename Output , typename Functor >

void nvbio::transform	(	const uint32	n,
		const Iterator1	in1,
		const Iterator2	in2,
		const Output	out,
		const Functor	functor
	)

apply a binary functor to each pair of elements of the given sequences

Definition at line 369 of file primitives_inl.h.

template<typename system_tag , typename KeyIterator , typename ValueIterator , typename OutputIterator >

void nvbio::upper_bound	(	const uint32	n,
		ValueIterator	values,
		const uint32	n_keys,
		KeyIterator	keys,
		OutputIterator	indices
	)

system-wide upper_bound

Parameters

n	number of input items
values	a system input iterator of values to be searched
n_keys	number of sorted keys
keys	a system input iterator of sorted keys
indices	a system output iterator

Definition at line 1020 of file primitives_inl.h.