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::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>


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::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. 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 20. Numeric Parallel Algorithms (In Header: <hpx/include/parallel_numeric.hpp>)

Name

Description

In Header

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>


Table 21. 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