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.

Context: In Kona, Redmond, and Portland, Study Group 1 (SG1, Concurrency) discussed language- and library-based ways to add parallelization and vectorization to Standard C++. For Bristol, three participating companies -- NVIDIA, Microsoft, and Intel -- were asked to come up with a combined proposal for a parallel algorithms library as one contribution. This is their first combined paper.

Document number: N3554

Date: 2013-03-15

A Parallel Algorithms Library

by Jared Hoberock et al. (NVIDIA, Microsoft, Intel)

Excerpt:

1 Executive Summary

We introduce a library of algorithms with parallel execution semantics. Some of these algorithms have semantics similar to the existing standard library of sequential algorithms. Some of the algorithms we propose are novel.

We introduce three parallel execution policies for parallel algorithm execution: std::seq, std::par, and std::vec, as well as a facility for vendors to provide non-standard execution policies as extensions. These policy objects may be used to specify how a parallel algorithm should be executed:

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

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

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

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

// vectorized sort
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());

// parallel sort with non-standard implementation-provided execution policies:
std::sort(vectorize_in_this_thread, vec.begin(), vec.end());
std::sort(submit_to_my_thread_pool, vec.begin(), vec.end());
std::sort(execute_on_that_gpu, vec.begin(), vec.end());
std::sort(offload_to_my_fpga, vec.begin(), vec.end());
std::sort(send_this_computation_to_the_cloud, vec.begin(), vec.end());

Algorithms invoked with std::seq execute internally in sequential order in the calling thread.

Algorithms invoked with std::par are permitted to execute internally in an unordered fashion in unspecified threads. It is the caller’s responsibility to ensure that the invocation does not introduce data races or deadlocks.

Algorithms invoked with std::vec are permitted to execute internally in an unordered fashion in unspecified threads. In addition to the restrictions implied by std::par, it is the caller’s responsibility to ensure that a std::vec invocation does not throw exceptions or attempt to perform synchronization operations.

Algorithms invoked without an execution policy execute as if they were invoked with std::seq.

An implementation may provide additional execution policies besides std::seq, std::par, or std::vec.

This proposal is a pure addition to the existing C++ standard library; we do not believe it alters the semantics of any existing functionality.

2 Design Notes and Outstanding Questions

Before introducing the detailed specification of our proposal, we begin by outlining our rationale and by noting that we have identified a number of outstanding questions which require further work to resolve. ...