Doc. No.: WG21/N4070
Date: 2014-06-20
Reply to: Hans-J. Boehm
Email: hboehm@google.com

N4070: Improving the specification of the vector execution policy in Parallelism TS

The Parallelism TS currently prohibits synchronization in functions called from vector algorithms, but says nothing about which standard library functions may invoke synchronization. Unfortunately, due to inline expansion, and the possibility of compiling nested functions in vector mode even if not inlined, this also applies to nested internal synchronization.

This is a very rough initial attempt at somewhat pinning this down. I expect this to generate PDTS comments. The reason to apply a rough fix now is to point out the issue, and hopefully generate much more relevant comments sooner rather than later.

Change:

Apply the following change to the Parallelism working paper, to 4.1.1p4:

The applications of function objects in parallel algorithms invoked with an execution policy of type parallel_vector_execution_policy are permitted to execute in an unordered fashion in unspecified threads, and unsequenced with respect to one another within each thread. [ Note: As a consequence, function objects governed by the parallel_vector_execution_policy policy must not synchronize with each other. Specifically, they must not acquire locks. -- end note ][Note: This overrides the usual guarantee from the C++ standard, Section 1.9 [intro.execution] that function executions do not interleave with one another.]

Since parallel_vector_execution_policy allows the execution of such function objects to be interleaved on a single thread, synchronization, including the use of mutexes, risks deadlock. Thus the use of synchronization with parallel_vector_execution_policy is restricted as follows:

A standard library function is vectorization-unsafe if it is specified to synchronize with another function invocation, or another function invocation is specified to synchronize with it, and if it is not a memory allocation or deallocation function. Vectorization-unsafe standard library functions may not be invoked by user code called from parallel_vector_execution_policy algorithms. [Note: Implementations must ensure that internal synchronization inside standard library routines does not induce deadlock.]