我需要实现前缀和算法,并且需要它尽可能快.例如:
[3, 1, 7, 0, 4, 1, 6, 3]
有没有办法使用SSE/mmx/SIMD cpu指令执行此操作？
我的第一个想法是递归并行地对每一对求和,直到所有的总和都计算如下!
[3, 4, 11, 11, 15, 16, 22, 25]
为了使算法更清晰,"z"不是最终的输出
而是用来计算输出
//in parallel do
for (int i = 0; i < z.length; i++) {
z[i] = x[i << 1] + x[(i << 1) + 1];
}
假设我有一个f(i)依赖于索引的函数i（以及无法预先计算的其他值）。我想填充一个数组，a以便a[n] = sum(f(i)) from i=0 to n-1.
编辑：在 Hristo Iliev 发表评论后，我意识到我在做什么是一个累积/前缀总和。
这可以用代码编写为
float sum = 0;
for(int i=0; i<N; i++) {
sum += f(i);
a[i] = sum;
}
现在我想使用 OpenMP 并行执行此操作。我可以用 OpenMP 做到这一点的一种方法是f(i)并行写出 的值，然后串行处理依赖关系。如果f(i)是一个慢函数，那么这可以很好地工作，因为非并行循环很简单。
#pragma omp parallel for
for(int i=0; i<N; i++) {
a[i] = f(i);
}
for(int i=1; i<N; i++) {
a[i] += a[i-1];
}
但是可以在没有 OpenMP 的非并行循环的情况下做到这一点。然而，我想出的解决方案很复杂，而且可能是骇人听闻的。所以我的问题是，是否有一种更简单、更简单的方法来使用 OpenMP 做到这一点？
下面的代码基本上运行我为每个线程列出的第一个代码。结果是a给定线程中的值在一个常量内是正确的。我将每个线程的总和保存到一个suma …