A new WG21 paper is available. A copy is linked below, and the paper will also appear in the next normal WG21 mailing. If you are not a committee member, please use the comments section below or the std-proposals forum for public discussion.

Document number: N3724

Date: 2013-08-30

A Parallel Algorithms Library

by J. Hoberock, O. Giroux, V. Grover, H. Sutter, et al.

Excerpt:

We propose an extension of the C++ standard library that provides access to parallel execution for a broad range of algorithms. Many of these algorithms correspond with algorithms already in the standard library, while some are novel. Our proposal is a pure extension, as it does not alter the meaning of any existing functionality. Our goal in this proposal is to provide access to the performance benefits of parallelism in a way that (1) can be easily adopted by programmers and (2) can be supported efficiently on the broadest possible range of hardware platforms.

We identify a collection of algorithms that permit efficient parallel implementations. We also introduce the concept of an execution policy, that may be used to specify how these algorithms should be executed. Execution policies become an optional parameter to a standard set of algorithms, permitting the programmer to write code such as the following:

std::vector<int> vec = ...

// previous standard sequential sort
std::sort(vec.begin(), vec.end());

// explicitly sequential sort
std::sort(std::seq, vec.begin(), vec.end());

// permitting parallel execution
std::sort(std::par, vec.begin(), vec.end());

// permitting vectorization as well
std::sort(std::vec, vec.begin(), vec.end());

// sort with dynamically-selected execution
size_t threshold = ...
std::execution_policy exec = std::seq;
if(vec.size() > threshold)
{
    exec = std::par;
}
std::sort(exec, vec.begin(), vec.end());

Interested programmers may experiment with this model of parallelism by accessing our prototype implementation at http://github.com/n3554/n3554.