执行策略与何时使用它们之间的区别

Question

我注意到大多数(如果不是全部)函数都会<algorithm>获得一个或多个额外的重载.所有这些额外的重载都会添加一个特定的新参数,例如,std::for_each来自:

template< class InputIt, class UnaryFunction >
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

至:

template< class ExecutionPolicy, class InputIt, class UnaryFunction2 >
void for_each( ExecutionPolicy&& policy, InputIt first, InputIt last, UnaryFunction2 f );

这个额外ExecutionPolicy对这些功能有什么影响？

有什么区别:

• std::execution::seq
• std::execution::par
• std::execution::par_unseq

何时使用其中一个？

Answer 1

seq 表示"按顺序执行",与没有执行策略的版本完全相同.

par表示"并行执行",它允许实现在多个线程上并行执行.您有责任确保内部不会发生任何数据争用f.

par_unseq意味着除了允许在多个线程中执行之外,还允许实现在单个线程内交错各个循环迭代,即加载多个元素并且f仅在之后执行所有这些元素.这是允许矢量化实现所必需的.

Answer 2

有什么区别seq和par/ par_unseq？

std::for_each(std::execution::seq, std::begin(v), std::end(v), function_call);

std::execution::seq代表顺序执行.如果您根本没有指定执行策略,那么它是默认值.它将强制实现按顺序执行所有函数调用.它还保证所有内容都由调用线程执行.

相反,std::execution::par并std::execution::par_unseq暗示并行执行.这意味着您承诺可以并行安全地执行给定函数的所有调用,而不会违反任何数据依赖性.允许实现使用并行实现,但不是强制执行.

par和之间有什么区别par_unseq？

par_unseq需要更强的保证par,但允许额外的优化.具体来说,par_unseq需要选项在同一个线程中交错执行多个函数调用.

让我们用一个例子说明不同之处.假设您要并行化此循环:

std::vector<int> v = { 1, 2, 3 };
int sum = 0;
std::for_each(std::execution::seq, std::begin(v), std::end(v), [&](int i) {
  sum += i*i;
});

您不能直接并行化上面的代码,因为它会为sum变量引入数据依赖性.为避免这种情况,您可以引入一个锁:

int sum = 0;
std::mutex m;
std::for_each(std::execution::par, std::begin(v), std::end(v), [&](int i) {
  std::lock_guard<std::mutex> lock{m};
  sum += i*i;
});

现在所有函数调用都可以安全地并行执行,并且切换时代码不会中断par.但是,如果您使用par_unseq相反的情况会发生什么,其中一个线程可能潜在地执行多个函数调用而不是按顺序但同时执行？

例如,如果代码重新排序,它可能会导致死锁:

 m.lock();    // iteration 1 (constructor of std::lock_guard)
 m.lock();    // iteration 2
 sum += ...;  // iteration 1
 sum += ...;  // iteration 2
 m.unlock();  // iteration 1 (destructor of std::lock_guard)
 m.unlock();  // iteration 2

在标准中,术语是矢量化 - 不安全的.引用P0024R2:

如果指定标准库函数与另一个函数调用同步,或指定另一个函数调用与其同步,并且它不是内存分配或释放函数,则标准库函数是矢量化不安全的.从parallel_vector_execution_policy算法调用的用户代码可能无法调用矢量化不安全的标准库函数.

使代码在矢量化安全之上的一种方法是用原子替换互斥锁:

std::atomic<int> sum{0};
std::for_each(std::execution::par_unseq, std::begin(v), std::end(v), [&](int i) {
  sum.fetch_add(i*i, std::memory_order_relaxed);
});

使用par_unseq过有par什么好处？

实现可以在par_unseq模式中使用的其他优化包括矢量化执行和跨线程的工作迁移(如果任务并行与父级窃取调度程序一起使用,则后者是相关的).

如果允许矢量化,则实现可以在内部使用SIMD并行(单指令,多数据).例如,OpenMP通过#pragma omp simd注释支持它,这可以帮助编译器生成更好的代码.

我应该什么时候喜欢std::execution::seq？

1. 正确性(避免数据竞争)
2. 避免并行开销(启动成本和同步)
3. 简单(调试)

数据依赖性将强制执行顺序执行并不罕见.换句话说,如果并行执行会添加数据竞争,则使用顺序执行.

重写和调整代码以实现并行执行并不总是微不足道的.除非它是您的应用程序的关键部分,否则您可以从顺序版本开始并稍后进行优化.如果要在共享环境中执行代码,并且需要保守资源使用,则还可能希望避免并行执行.

并行性也不是免费的.如果循环的预期总执行时间非常短,即使从纯粹的性能角度来看,顺序执行也很可能是最好的.数据越大,每个计算步骤的成本越高,同步开销就越不重要.

例如,在上面的例子中使用并行性是没有意义的,因为向量只包含三个元素,并且操作非常便宜.另请注意,原始版本 - 在引入互斥锁或原子之前 - 不包含同步开销.测量并行算法加速的一个常见错误是使用在一个CPU上运行的并行版本作为基线.相反,您应始终与优化的顺序实现进行比较,而不会产生同步开销.

我应该什么时候喜欢std::execution::par_unseq？

首先,确保它不会牺牲正确性:

• 如果在由不同线程并行执行步骤时存在数据争用,par_unseq则不是一种选择.
• 例如,如果代码是vectorization-unsafe,因为它获取了一个锁,par_unseq则不是一个选项(但par可能是).

否则,使用par_unseq它是否是性能关键部分并par_unseq提高性能seq.

我应该什么时候喜欢std::execution::par？

如果这些步骤可以安全地并行执行,但par_unseq由于它是矢量化不安全而无法使用,它是一个候选者par.

比如seq_unseq,验证它是性能关键部分,并且par是性能改进seq.

资料来源:

• cppreference.com(执行政策)
• P0024R2:并行TS应该是标准化的