具有依赖性的数组中的并行操作

Question

我需要帮助来解决这个问题，我有一个代码，在数组的前一个元素上执行操作，我需要使用openmp任务并行化，但是我知道如何删除这个依赖项。我的老师说在这种情况下使用depend（in，out）并不感兴趣。我如何删除依赖于此呢？

void sum_sequential(float a[N]) {
        a[0] = 1.0;

    for (int i = 1; i < N; i++)
        a[i] = 2 * a[i-1] + 1;
}

Answer 1

你确实存在数据依赖性是完全正确的。要为每个元素计算的值用先前为前一个元素计算的值表示，因此该算法本质上是串行的。并行化并没有实际的优势，因为成功处理依赖关系不会留下任何并发的余地。

然而，如果你仔细研究计算，就有可能以一种没有这种依赖关系的代数等价方式重新表达它 - 一种完全不同的算法产生相同的结果并且可以简单地并行化。冒着提供过大提示的风险，尝试手工写出结果的前几个术语，看看你是否认识到一个简单的模式。