parallel-processing - 摆脱数据依赖

Question

我有这个代码：

for(i=0; i<size; i++)
{
    d[i] = d[i-1] + v[i];
}

当我对此循环进行并行处理时，我有数据依赖性并且启动间隔变为 2 含义我有：

启动间隔：2

|load v[i-1]|load d[i-2]|    add    |store d[i-1]|
|           |           |  load v[i]|load d[i-1] |     add    | store d[i] |

我不想在两者之间拖延。

启动间隔：1

|load v[i-1]|load d[i-2]|    add    |store d[i-1]|
|           |load v[i]  |load d[i-1]|     add    | store d[i] |

这是不可能的，因为 d[i-1] 尚未存储。

我们如何通过更改代码将启动间隔设为 1？

Answer 1

你无法缩小这个差距。

此外，这（循环展开）不是这种循环的并行处理的最有效方式。您的循环看起来像一个前缀和操作。有可用于前缀和的快速并行算法和实现。例如，这个问题