Как Reordering удаляет обратную L oop -Carried-Dependence - PullRequest
Новая
       80

Как Reordering удаляет обратную L oop -Carried-Dependence

3 голосов
/ 10 июля 2020

Учитывая следующий код, существует обратная зависимость. 

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 не имеют зависимостей в пределах l oop. 

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 S2, поскольку S1 сначала пишет, а 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 > ?? Может ли кто-нибудь прояснить, как определить обратные зависимости и почему именно переупорядочение больше не является обратной зависимостью (в лучшем случае с этим примером)? С моей точки зрения, мы все еще зависим от последней итерации l oop. Но мои ресурсы (лекция) говорят, что это больше не обратная зависимость, и мы можем векторизовать l oop.

...