0

在一次讲座中，我的教授给了我们以下循环：

for (int i = 0; i < 100; i++) {
    a[i] = a[i] + b[i];
    b[i + 1] = c[i] + d[i];
}

他指出了循环迭代之间的依赖关系，因为第 3 行设置了一个值，该值将在第 2 行的下一次迭代中使用（设置在下一次迭代b[i+1]中成为b[i]）。因此，我们不能并行运行循环的每次迭代。

然后他给了我们这个展开的版本：

a[1] = a[1] + b[1];
for (int i = 0; i < 98; i++) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i] + b[i];
}
b[99] = c[99] + d[99];

他声称循环的每次迭代现在都可以并行运行。我看到的问题是第 3 行设置了b[i]第 4 行的下一次迭代中的内容，因此我们仍然不能并行运行每个迭代。

我这样说对吗？如果是这样，是否有第一个循环的正确展开版本，其中每次迭代都可以并行化？

4

1 回答 1

1

我猜你在写下你的教授给出的展开版本时犯了一个错误。为了等价于第一个算法，它应该是这样的：

a[0] = a[0] + b[0];
for (int i=0 ; i<99 ; ++i) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i+1] + b[i+1];
}
b[100] = c[100] + d[100];

在这个版本上，你可以看到依赖问题已经消失了。

于 2012-03-12T07:59:56.510 回答