实际上，使用递归分而治之的方法来干净地实现任务是非常简单的。这几乎是textbook https://en.wikibooks.org/wiki/OpenMP/Tasks code.
void operation(int* p1, int* p2, size_t bins)
{
for (int i = 0; i < bins; i++)
p1[i] += p2[i];
}
void reduce(int** arrs, size_t bins, int begin, int end)
{
assert(begin < end);
if (end - begin == 1) {
return;
}
int pivot = (begin + end) / 2;
/* Moving the termination condition here will avoid very short tasks,
* but make the code less nice. */
#pragma omp task
reduce(arrs, bins, begin, pivot);
#pragma omp task
reduce(arrs, bins, pivot, end);
#pragma omp taskwait
/* now begin and pivot contain the partial sums. */
operation(arrs[begin], arrs[pivot], bins);
}
/* call this within a parallel region */
#pragma omp single
reduce(at, bins, 0, n);
据我所知，没有不必要的同步，也没有对关键部分进行奇怪的轮询。它也可以自然地处理与您的排名数不同的数据大小。我发现它非常干净且易于理解。所以我确实认为这是better比你的两个解决方案。
但让我们看看它在实践中的表现*。为此我们可以使用Score-p http://www.vi-hps.org/projects/score-p/ and Vampir http://vampir.eu:
*bins=10000 so the reduction actually takes a little bit of time. Executed on a 24-core Haswell system w/o turbo. gcc 4.8.4, -O3. I added some buffer around the actual execution to hide initialization/post-processing
该图显示了水平时间轴上应用程序内任何线程所发生的情况。树的实现从上到下：
-
omp for loop
-
omp critical一种任务分配。
omp task
这很好地展示了具体的实现是如何实际执行的。现在看来，尽管存在不必要的同步，但 for 循环实际上是最快的。但这种性能分析仍然存在一些缺陷。例如，我没有固定线程。在实践中，NUMA（非均匀内存访问）非常重要：核心是否在其自己的缓存/其自己的套接字内存中拥有此数据？这就是任务解决方案变得不确定的地方。在简单比较中没有考虑重复之间非常显着的差异。
如果归约操作在运行时变得可变，那么任务解决方案将变得比同步 for 循环更好。
The critical解决方案有一些有趣的方面，被动线程不会持续等待，因此它们更有可能消耗 CPU 资源。这可能对性能不利，例如在涡轮模式的情况下。
请记住，task通过避免生成立即返回的任务，解决方案具有更大的优化潜力。这些解决方案的执行方式也很大程度上取决于特定的 OpenMP 运行时。英特尔的运行时似乎在任务方面表现更差。
我的建议是：
- 用最优算法实现最可维护的解决方案
复杂
- 衡量代码的哪些部分对运行时真正重要
- 根据实际测量分析瓶颈是什么。根据我的经验，这更多的是关于 NUMA 和调度，而不是一些不必要的障碍。
- 根据您的实际测量进行微观优化
线性解
这是线性时间线proccess_data_v1 from 这个问题 https://stackoverflow.com/q/16789242/620382.
OpenMP 4 缩减
所以我想到了OpenMP缩减。棘手的部分似乎是从at循环内的数组没有副本。我用以下方法初始化工作数组NULL第一次只需移动指针：
void meta_op(int** pp1, int* p2, size_t bins)
{
if (*pp1 == NULL) {
*pp1 = p2;
return;
}
operation(*pp1, p2, bins);
}
// ...
// declare before parallel region as global
int* awork = NULL;
#pragma omp declare reduction(merge : int* : meta_op(&omp_out, omp_in, 100000)) initializer (omp_priv=NULL)
#pragma omp for reduction(merge : awork)
for (int t = 0; t < n; t++) {
meta_op(&awork, at[t], bins);
}
令人惊讶的是，这看起来不太好：
top is icc 16.0.2, bottom is gcc 5.3.0, both with -O3.
两者似乎都实现了串行化的减少。我试着调查一下gcc / libgomp，但我并不能立即明白发生了什么。从中间代码/反汇编来看，他们似乎将最终合并包装在一个GOMP_atomic_start/end- 这似乎是一个全局互斥体。相似地icc将调用包装到operation in a kmpc_critical。我认为成本高昂的定制缩减操作没有太多优化。传统的缩减可以通过硬件支持的原子操作来完成。
注意每个operation速度更快，因为输入是在本地缓存的，但由于序列化，整体速度较慢。同样，由于差异很大，这并不是一个完美的比较，并且早期的屏幕截图使用了不同的gcc版本。但趋势很明显，而且我也有缓存效果的数据。
