pAlgorithms

Collaboration diagram for pAlgorithms:

Modules
	Non-modifying Sequence Operations
	Search and query view elements.
	Mutating Sequence Operations
	Modify the elements in a view.
	Sorting and Related Operations
	Sort elements in a view or perform operations on sorted sequences.
	Generalized Numeric Algorithms
	Algorithms for numeric operations on view elements. Defined in stapl/algorithms/numeric.hpp.
	Function Objects
	A collection of element-wise operations commonly used to process view elements in a pAlgorithm. Defined in stapl/algorithms/functional.hpp.

Detailed Description

A pAlgorithm is the parallel counterpart of the STL algorithm. There are three types of pAlgorithms in STAPL:

• pAlgorithms with semantics identical to their sequential counterparts.
• pAlgorithms with enhanced semantics (e.g. a parallel find could return any (or all) element found, while STL find only returns the first).
• pAlgorithms with no sequential equivalent in STL.

STL algorithms take iterators marking the start and end of an input sequence as parameters. Using STL constructs, such as the vector, this can be illustrated as follows:

std::vector<int> v(1000000);
// initialize v
std::find( v.begin(), v.end(), 0 );

However, regular C++ arrays also support iterators, because iterators are in fact just generalized pointers:

int v[1000000];
... initialize v ...
find( &v[0], &v[1000000], 0 );

STAPL pAlgorithms take one or more pView instances as parameters instead. For example, STL provides an algorithm to find an element in a list, find. STAPL provides find which works with pViews. The construction of the pView over a container is an additional step, but the same pView instance can be used across multiple pAlgorithm calls and allows additional flexibility such as providing access to a portion of the container instead of the entire data set.

stapl::vector<int> v(1000000);
stapl::vector_view<stapl::vector<int>> vw(v);
// initialize v
stapl::find( vw, 0 );

In describing the parameters of these sets of pAlgorithms, some conventions are used. All of the pAlgorithms operate on sequences of input and/or output data (there are a few STL algorithms that only operate on a few elements, such as min or max, which are not parallel operations). STL generally describes this sequence using set notation as [first, last), where first is an iterator to the start of a sequence and last is an iterator to the end of a sequence, and everything from the first element up to, but not including, the last element is considered part of the sequence. STAPL's pViews completely encapsulate this information. Hence, when describing a given pAlgorithm, a sequence is represented as a pView.

Many pAlgorithms behavior is described in terms of operator?, where ? is one of the C++ operators such as <, >, ==, etc. C++ allows the programmer to override the actions taken when one of the operators is called on a given class or type, and it may be helpful for the learning STAPL programmer to study this mechanism in C++. Another method that STL uses to change the default behavior of operators is to define Function Objects. These are functions or classes that implement operator() that will be used instead of the given operator. Most pAlgorithms (and algorithms in STL), accept function objects, and in fact such flexibility lets both STL and STAPL algorithms to be adjusted to exactly what is needed, reducing the amount of code that a user needs to rewrite to obtain the desired effect.

All pAlgorithms are expressed using dependence patterns, which when combined with the functor describing the operation on a single element and the set of pViews to process are using to instantiate the parallel task graph, PARAGRAPH. When the PARAGRAPH instance is executed using the executor and scheduler facilities of the STAPL runtime the desired parallel computation is performed. The scheduling policy can be specified for each PARAGRAPH instance if desired, otherwise the default FIFO policy is used. Multiple PARAGRAPHS may be processed concurrently by a PARAGRAPH executor that the set of locations executing the STAPL applications use to perform work.