时间戳

首页 > 解决方案 > 重新排序如何消除反向循环携带依赖

c - 重新排序如何消除反向循环携带依赖

问题描述

给定以下代码，存在向后依赖。

for(int i=0; i<n; i++) {
  (S1): d[i] = a[i-1] * d[i];
  (S2): a[i] = b[i] + c[i];
}

我的问题是如何定义/识别这些向后依赖。因为我真的找不到自己的计划来做到这一点。

这就是我目前解决这个问题的方式：在这个例子S1 has a anti-dependency on S2中，S1 首先读取并且 S2 写入变量。

进一步我们学会了创建一个方向向量：

Iteration: read:  write
v1:
S1(9)      a[8]   
S2(9)      -      a[9]

v2:
S1(10)     a[9]   -
S2(10)     -      a[10]

这将导致方向矢量 D_v：D_v = v2 - v1 = (i - 1) - i = -1 = >

现在解决方案是重新排序语句，这是可能的，因为 S1 和 S2 在循环中没有依赖关系。

for(int i=0; i<n; i++) {
  (S1): a[i] = b[i] + c[i];
  (S2): d[i] = a[i-1] * d[i];
}

这将导致S1 has a true-dependency on S2S1 首先写入而 S2 读取变量。如果我重复创建方向向量：

Iteration: read:  write
v1:
S1(9)      -      a[9]
S2(9)      a[8]   -

v2:
S1(10)     -      a[10]
S2(10)     a[9]   -

现在将导致方向向量D_v: D_v = v2 - v1 = (i + 1) - i = +1 = <

现在的方向向量是< instead of > (or +1 instead of -1)

但我只是没有看到方向向量和向后依赖之间的联系？这是纯粹的< or > ?吗？有人可以澄清如何识别向后依赖关系以及为什么重新排序不再是向后依赖关系（在这个例子中充其量）？从我的角度来看，我们仍然依赖于循环的最后一次迭代。但是我的资源（讲座）说这不再是向后依赖，我们可以向量化循环。

标签： cloopsparallel-processingdependenciesopenmp

解决方案

推荐阅读