HPX

PrevUpHomeNext

Using Parallel Algorithms

A parallel algorithm is a function template described by this document which is declared in the (inline) namespace hpx::parallel::v1.

[Note] Note

For compilers which do not support inline namespaces, all of the namespace v1 is imported into the namespace hpx::parallel. The effect is similar to what inline namespaces would do, namely all names defined in hpx::parallel::v1 are accessible from the namespace hpx::parallel as well.

All parallel algorithms are very similar in semantics to their sequential counterparts (as defined in the namespace std) with an additional formal template parameter named ExecutionPolicy. The execution policy is generally passed as the first argument to any of the parallel algorithms and describes the manner in which the execution of these algorithms may be parallelized and the manner in which they apply user-provided function objects.

The applications of function objects in parallel algorithms invoked with an execution policy object of type sequenced_policy or sequenced_task_policy execute in sequential order. For sequenced_policy the execution happens in the calling thread.

The applications of function objects in parallel algorithms invoked with an execution policy object of type parallel_policy or parallel_task_policy are permitted to execute in an unordered fashion in unspecified threads, and indeterminately sequenced within each thread.

[Important] Important

It is the caller's responsibility to ensure correctness, for example that the invocation does not introduce data races or deadlocks.

The applications of function objects in parallel algorithms invoked with an execution policy of type parallel_unsequenced_policy is in HPX equivalent to the use of the execution policy parallel_policy.

Algorithms invoked with an execution policy object of type execution_policy execute internally as if invoked with the contained execution policy object. No exception is thrown when an execution_policy contains an execution policy of type sequenced_task_policy or parallel_task_policy (which normally turn the algorithm into its asynchronous version). In this case the execution is semantically equivalent to the case of passing a sequenced_policy or parallel_policy contained in the execution_policy object respectively.

Parallel Exceptions

During the execution of a standard parallel algorithm, if temporary memory resources are required by any of the algorithms and no memory are available, the algorithm throws a std::bad_alloc exception.

During the execution of any of the parallel algorithms, if the application of a function object terminates with an uncaught exception, the behavior of the program is determined by the type of execution policy used to invoke the algorithm:

For example, the number of invocations of the user-provided function object in for_each is unspecified. When for_each is executed sequentially, only one exception will be contained in the exception_list object.

These guarantees imply that, unless the algorithm has failed to allocate memory and terminated with std::bad_alloc, all exceptions thrown during the execution of the algorithm are communicated to the caller. It is unspecified whether an algorithm implementation will "forge ahead" after encountering and capturing a user exception.

The algorithm may terminate with the std::bad_alloc exception even if one or more user-provided function objects have terminated with an exception. For example, this can happen when an algorithm fails to allocate memory while creating or adding elements to the exception_list object.

Parallel Algorithms

HPX provides implementations of the following parallel algorithms:

Table 17. Non-modifying Parallel Algorithms (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::adjacent_find

Computes the differences between adjacent elements in a range.

<hpx/include/parallel_adjacent_find.hpp>

adjacent_find

hpx::parallel::all_of

Checks if a predicate is true for all of the elements in a range.

<hpx/include/parallel_all_any_none.hpp>

all_any_none_of

hpx::parallel::any_of

Checks if a predicate is true for any of the elements in a range.

<hpx/include/parallel_all_any_none.hpp>

all_any_none_of

hpx::parallel::count

Returns the number of elements equal to a given value.

<hpx/include/parallel_count.hpp>

count

hpx::parallel::count_if

Returns the number of elements satisfying a specific criteria.

<hpx/include/parallel_count.hpp>

count_if

hpx::parallel::equal

Determines if two sets of elements are the same.

<hpx/include/parallel_equal.hpp>

equal

hpx::parallel::exclusive_scan

Does an exclusive parallel scan over a range of elements.

<hpx/include/parallel_scan.hpp>

exclusive_scan

hpx::parallel::find

Finds the first element equal to a given value.

<hpx/include/parallel_find.hpp>

find

hpx::parallel::find_end

Finds the last sequence of elements in a certain range.

<hpx/include/parallel_find.hpp>

find_end

hpx::parallel::find_first_of

Searches for any one of a set of elements.

<hpx/include/parallel_find.hpp>

find_first_of

hpx::parallel::find_if

Finds the first element satisfying a specific criteria.

<hpx/include/parallel_find.hpp>

find

hpx::parallel::find_if_not

Finds the first element not satisfying a specific criteria.

<hpx/include/parallel_find.hpp>

find_if_not

hpx::parallel::for_each

Applies a function to a range of elements.

<hpx/include/parallel_for_each.hpp>

for_each

hpx::parallel::for_each_n

Applies a function to a number of elements.

<hpx/include/parallel_for_each.hpp>

for_each_n

hpx::parallel::inclusive_scan

Does an inclusive parallel scan over a range of elements.

<hpx/include/parallel_scan.hpp>

inclusive_scan

hpx::parallel::lexicographical_compare

Checks if a range of values is lexicographically less than another range of values.

<hpx/include/parallel_lexicographical_compare.hpp>

lexicographical_compare

hpx::parallel::mismatch

Finds the first position where two ranges differ.

<hpx/include/parallel_mismatch.hpp>

mismatch

hpx::parallel::none_of

Checks if a predicate is true for none of the elements in a range.

<hpx/include/parallel_all_any_none.hpp>

all_any_none_of

hpx::parallel::search

Searches for a range of elements.

<hpx/include/parallel_search.hpp>

search

hpx::parallel::search_n

Searches for a number consecutive copies of an element in a range.

<hpx/include/parallel_search.hpp>

search_n


Table 18. Modifying Parallel Algorithms (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::copy

Copies a range of elements to a new location.

<hpx/include/parallel_copy.hpp>

exclusive_scan

hpx::parallel::copy_n

Copies a number of elements to a new location.

<hpx/include/parallel_copy.hpp>

copy_n

hpx::parallel::copy_if

Copies the elements from a range to a new location for which the given predicate is true.

<hpx/include/parallel_copy.hpp>

copy

hpx::parallel::move

Moves a range of elements to a new location.

<hpx/include/parallel_fill.hpp>

move

hpx::parallel::fill

Assigns a range of elements a certain value.

<hpx/include/parallel_fill.hpp>

fill

hpx::parallel::fill_n

Assigns a value to a number of elements.

<hpx/include/parallel_fill.hpp>

fill_n

hpx::parallel::generate

Saves the result of a function in a range.

<hpx/include/parallel_generate.hpp>

generate

hpx::parallel::generate_n

Saves the result of N applications of a function.

<hpx/include/parallel_generate.hpp>

generate_n

hpx::parallel::remove_copy

Copies the elements from a range to a new location that are not equal to the given value.

<hpx/include/parallel_remove_copy.hpp>

remove_copy

hpx::parallel::remove_copy_if

Copies the elements from a range to a new location for which the given predicate is false.

<hpx/include/parallel_remove_copy.hpp>

remove_copy

hpx::parallel::replace

Replaces all values satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

replace

hpx::parallel::replace_if

Replaces all values satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

replace

hpx::parallel::replace_copy

Copies a range, replacing elements satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

replace_copy

hpx::parallel::replace_copy_if

Copies a range, replacing elements satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

replace_copy

hpx::parallel::reverse

Reverses the order elements in a range.

<hpx/include/parallel_reverse.hpp>

reverse

hpx::parallel::reverse_copy

Creates a copy of a range that is reversed.

<hpx/include/parallel_reverse.hpp>

reverse_copy

hpx::parallel::rotate

Rotates the order of elements in a range.

<hpx/include/parallel_rotate.hpp>

rotate

hpx::parallel::rotate_copy

Copies and rotates a range of elements.

<hpx/include/parallel_rotate.hpp>

rotate_copy

hpx::parallel::swap_ranges

Swaps two ranges of elements.

<hpx/include/parallel_swap_ranges.hpp>

swap_ranges

hpx::parallel::transform

Applies a function to a range of elements.

<hpx/include/parallel_transform.hpp>

transform

hpx::parallel::unique_copy

Applies a function to a range of elements.

<hpx/include/parallel_unique.hpp>

unique_copy


Table 19. Set operations on sorted sequences (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::merge

Merges two sorted ranges.

<hpx/include/parallel_merge.hpp>

merge

hpx::parallel::includes

Returns true if one set is a subset of another.

<hpx/include/parallel_set_operations.hpp>

includes

hpx::parallel::set_difference

Computes the difference between two sets.

<hpx/include/parallel_set_operations.hpp>

set_difference

hpx::parallel::set_intersection

Computes the intersection of two sets.

<hpx/include/parallel_set_operations.hpp>

set_intersection

hpx::parallel::set_symmetric_difference

Computes the symmetric difference between two sets.

<hpx/include/parallel_set_operations.hpp>

set_symmetric_difference

hpx::parallel::set_union

Computes the union of two sets.

<hpx/include/parallel_set_operations.hpp>

set_union


Table 20. Heap operations (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::is_heap

Returns true if the range is max heap.

<hpx/include/is_heap.hpp>

is_heap

hpx::parallel::is_heap_until

Returns the first element that breaks a max heap.

<hpx/include/is_heap.hpp>

is_heap_until


Table 21. Minimum/maximum operations (In Header: <hpx/include/parallel_algortithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::max_element

Returns the largest element in a range.

<hpx/include/parallel_minmax.hpp>

max_element

hpx::parallel::min_element

Returns the smallest element in a range.

<hpx/include/parallel_minmax.hpp>

min_element

hpx::parallel::minmax_element

Returns the smallest and the largest element in a range.

<hpx/include/parallel_minmax.hpp>

minmax_element


Table 22. Partitioning Operations (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::is_partitioned

Returns true if each true element for a predicate precedes the false elements in a range

<hpx/include/parallel_is_partitioned.hpp>

is_partitioned

hpx::parallel::partition

Divides elements into two groups while don't preserve their relative order

<hpx/include/parallel_partition.hpp>

partition

hpx::parallel::partition_copy

Copies a range dividing the elements into two groups

<hpx/include/parallel_partition.hpp>

partition_copy

hpx::parallel::stable_partition

Divides elements into two groups while preserving their relative order

<hpx/include/parallel_partition.hpp>

stable_partition


Table 23. Sorting Operations (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::is_sorted

Returns true if each element in a range is sorted

<hpx/include/parallel_is_sorted.hpp>

is_sorted

hpx::parallel::is_sorted_until

Returns the first unsorted element

<hpx/include/parallel_is_sorted.hpp>

is_sorted_until

hpx::parallel::sort

Sorts the elements in a range

<hpx/include/parallel_sort.hpp>

sort

hpx::parallel::sort_by_key

Sorts one range of data using keys supplied in another range

<hpx/include/parallel_sort.hpp>


Table 24. Numeric Parallel Algorithms (In Header: <hpx/include/parallel_numeric.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::adjacent_difference

Calculates the difference between each element in an input range and the preceding element.

<hpx/include/parallel_adjacent_difference.hpp>

adjacent_difference

hpx::parallel::reduce

Sums up a range of elements.

<hpx/include/parallel_reduce.hpp>

reduce

hpx::parallel::reduce_by_key

Performs an inclusive scan on consecutive elements with matching keys, with a reduction to output only the final sum for each key. The key sequence {1,1,1,2,3,3,3,3,1} and value sequence {2,3,4,5,6,7,8,9,10} would be reduced to keys={1,2,3,1}, values={9,5,30,10}

<hpx/include/parallel_reduce.hpp>

 

hpx::parallel::transform_reduce

Sums up a range of elements after applying a function. Also, accumulates the inner products of two input ranges.

<hpx/include/parallel_transform_reduce.hpp>

transform_reduce

hpx::parallel::transform_inclusive_scan

Does an inclusive parallel scan over a range of elements after applying a function.

<hpx/include/parallel_scan.hpp>

transform_inclusive_scan

hpx::parallel::transform_exclusive_scan

Does an exclusive parallel scan over a range of elements after applying a function.

<hpx/include/parallel_scan.hpp>

transform_exclusive_scan


Table 25. Dynamic Memory Management (In Header: <hpx/include/parallel_memory.hpp>)

Name

Description

In Header

Algorithm page at cppreference.com

hpx::parallel::destroy

Destroys a range of objects.

<hpx/include/parallel_destroy.hpp>

destroy

hpx::parallel::destroy_n

Destroys a range of objects.

<hpx/include/parallel_destroy.hpp>

destroy_n

hpx::parallel::uninitialized_copy

Copies a range of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_copy.hpp>

uninitialized_copy

hpx::parallel::uninitialized_copy_n

Copies a number of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_copy.hpp>

uninitialized_copy_n

hpx::parallel::uninitialized_default_construct

Copies a range of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_default_construct.hpp>

uninitialized_default_construct

hpx::parallel::uninitialized_default_construct_n

Copies a number of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_default_construct.hpp>

uninitialized_default_construct_n

hpx::parallel::uninitialized_fill

Copies an object to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_fill.hpp>

uninitialized_fill

hpx::parallel::uninitialized_fill_n

Copies an object to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_fill.hpp>

uninitialized_fill_n

hpx::parallel::uninitialized_move

Moves a range of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_move.hpp>

uninitialized_move

hpx::parallel::uninitialized_move_n

Moves a number of objects to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_move.hpp>

uninitialized_move_n

hpx::parallel::uninitialized_value_construct

Constructs objects in an uninitialized area of memory.

<hpx/include/parallel_uninitialized_value_construct.hpp>

uninitialized_value_construct

hpx::parallel::uninitialized_value_construct_n

Constructs objects in an uninitialized area of memory.

<hpx/include/uninitialized_value_construct.hpp>

uninitialized_value_construct_n


Table 26. Index-based for-loops (In Header: <hpx/include/parallel_algorithm.hpp>)

Name

Description

In Header

hpx::parallel::for_loop

Implements loop functionality over a range specified by integral or iterator bounds.

<hpx/include/parallel_for_loop.hpp>

hpx::parallel::for_loop_strided

Implements loop functionality over a range specified by integral or iterator bounds.

<hpx/include/parallel_for_loop.hpp>

hpx::parallel::for_loop_n

Implements loop functionality over a range specified by integral or iterator bounds.

<hpx/include/parallel_for_loop.hpp>

hpx::parallel::for_loop_n_strided

Implements loop functionality over a range specified by integral or iterator bounds.

<hpx/include/parallel_for_loop.hpp>



PrevUpHomeNext