HPX - High Performance ParalleX

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 sequential_execution_policy or sequential_task_execution_policy execute in sequential order. For sequential_execution_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_execution_policy or parallel_task_execution_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_vector_execution_policy is in HPX equivalent to the use of the execution policy parallel_execution_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 sequential_task_execution_policy or parallel_task_execution_policy (which normally turn the algorithm into its asynchronous version). In this case the execution is semantically equivalent to the case of passing a sequential_execution_policy or parallel_execution_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_algortithm.hpp>)

Name

Description

In Header

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>

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>

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>

hpx::parallel::for_each

Applies a function to a range of elements.

<hpx/include/parallel_for_each.hpp>

hpx::parallel::for_each_n

Applies a function to a number of elements.

<hpx/include/parallel_for_each.hpp>

hpx::parallel::count

Returns the number of elements equal to a given value.

<hpx/include/parallel_count.hpp>

hpx::parallel::count_if

Returns the number of elements satisfying a specific criteria.

<hpx/include/parallel_count.hpp>

hpx::parallel::equal

Determines if two sets of elements are the same.

<hpx/include/parallel_equal.hpp>

hpx::parallel::mismatch

Finds the first position where two ranges differ.

<hpx/include/parallel_mismatch.hpp>

hpx::parallel::find

Finds the first element equal to a given value.

<hpx/include/parallel_find.hpp>

hpx::parallel::find_end

Finds the last sequence of elements in a certain range.

<hpx/include/parallel_find.hpp>

hpx::parallel::find_if

Finds the first element satisfying a specific criteria.

<hpx/include/parallel_find.hpp>

hpx::parallel::find_first_of

Searches for any one of a set of elements.

<hpx/include/parallel_find.hpp>

hpx::parallel::find_if_not

Finds the first element not satisfying a specific criteria.

<hpx/include/parallel_find.hpp>

hpx::parallel::adjacent_find

Computes the differences between adjacent elements in a range.

<hpx/include/parallel_adjacent_find.hpp>

hpx::parallel::lexicographical_compare

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

<hpx/include/parallel_lexicographical_compare.hpp>

hpx::parallel::search

Searches for a range of elements.

<hpx/include/parallel_search.hpp>

hpx::parallel::search_n

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

<hpx/include/parallel_search.hpp>

hpx::parallel::inclusive_scan

Does an inclusive parallel scan over a range of elements.

<hpx/include/parallel_scan.hpp>

hpx::parallel::exclusive_scan

Does an exclusive parallel scan over a range of elements.

<hpx/include/parallel_scan.hpp>


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

Name

Description

In Header

hpx::parallel::copy

Copies a range of elements to a new location.

<hpx/include/parallel_copy.hpp>

hpx::parallel::copy_n

Copies a number of elements to a new location.

<hpx/include/parallel_copy.hpp>

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>

hpx::parallel::move

Moves a range of elements to a new location.

<hpx/include/parallel_fill.hpp>

hpx::parallel::fill

Assigns a range of elements a certain value.

<hpx/include/parallel_fill.hpp>

hpx::parallel::fill_n

Assigns a value to a number of elements.

<hpx/include/parallel_fill.hpp>

hpx::parallel::transform

Applies a function to a range of elements.

<hpx/include/parallel_transform.hpp>

hpx::parallel::generate

Saves the result of a function in a range.

<hpx/include/parallel_generate.hpp>

hpx::parallel::generate_n

Saves the result of N applications of a function.

<hpx/include/parallel_generate.hpp>

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>

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>

hpx::parallel::replace

Replaces all values satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

hpx::parallel::replace_if

Replaces all values satisfying specific criteria with another value.

<hpx/include/parallel_replace.hpp>

hpx::parallel::replace_copy

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

<hpx/include/parallel_replace.hpp>

hpx::parallel::replace_copy_if

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

<hpx/include/parallel_replace.hpp>

hpx::parallel::reverse

Reverses the order elements in a range.

<hpx/include/parallel_reverse.hpp>

hpx::parallel::reverse_copy

Creates a copy of a range that is reversed.

<hpx/include/parallel_reverse.hpp>

hpx::parallel::rotate

Rotates the order of elements in a range.

<hpx/include/parallel_rotate.hpp>

hpx::parallel::rotate_copy

Copies and rotates a range of elements.

<hpx/include/parallel_rotate.hpp>

hpx::parallel::swap_ranges

Swaps two ranges of elements.

<hpx/include/parallel_swap_ranges.hpp>


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

Name

Description

In Header

hpx::parallel::includes

Returns true if one set is a subset of another.

<hpx/include/parallel_set_operations.hpp>

hpx::parallel::set_difference

Computes the difference between two sets.

<hpx/include/parallel_set_operations.hpp>

hpx::parallel::set_intersection

Computes the intersection of two sets.

<hpx/include/parallel_set_operations.hpp>

hpx::parallel::set_symmetric_difference

Computes the symmetric difference between two sets.

<hpx/include/parallel_set_operations.hpp>

hpx::parallel::set_union

Computes the union of two sets.

<hpx/include/parallel_set_operations.hpp>


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

Name

Description

In Header

hpx::parallel::max_element

Returns the largest element in a range.

<hpx/include/parallel_minmax.hpp>

hpx::parallel::min_element

Returns the smallest element in a range.

<hpx/include/parallel_minmax.hpp>

hpx::parallel::minmax_element

Returns the smallest and the largest element in a range.

<hpx/include/parallel_minmax.hpp>


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

Name

Description

In Header

hpx::parallel::is_sorted

Returns true if each element in a range is sorted

<hpx/include/parallel_is_sorted.hpp>

hpx::parallel::is_sorted_until

Returns the first unsorted element

<hpx/include/parallel_is_sorted.hpp>

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>

hpx::parallel::sort

Sorts the elements in a range in ascending order

<hpx/include/parallel_sort.hpp>


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

Name

Description

In Header

hpx::parallel::adjacent_difference

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

<hpx/include/parallel_adjacent_difference.hpp>

hpx::parallel::inner_product

Accumulates the inner products of two input ranges.

<hpx/include/parallel_inner_product.hpp>

hpx::parallel::reduce

Sums up a range of elements.

<hpx/include/parallel_reduce.hpp>

hpx::parallel::transform_reduce

Sums up a range of elements after applying a function.

<hpx/include/parallel_transform_reduce.hpp>

hpx::parallel::transform_inclusive_scan

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

<hpx/include/parallel_scan.hpp>

hpx::parallel::transform_exclusive_scan

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

<hpx/include/parallel_scan.hpp>


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

Name

Description

In Header

hpx::parallel::uninitialized_copy

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

<hpx/include/parallel_uninitialized_copy.hpp>

hpx::parallel::uninitialized_copy_n

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

<hpx/include/parallel_uninitialized_copy.hpp>

hpx::parallel::uninitialized_fill

Copies an object to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_fill.hpp>

hpx::parallel::uninitialized_fill_n

Copies an object to an uninitialized area of memory.

<hpx/include/parallel_uninitialized_fill.hpp>



PrevUpHomeNext