GCD test - для проверки зависимости между операторами цикла

Question

Я понимаю, как GCD работает на тривиальном примере, как показано ниже:

for(i=1; i<=100; i++)
{
        X[2*i+3] = X[2*i] + 50;
}

мы сначала преобразуем его в следующую форму: X[a*i + b] и X[c*i + d]

a=2b=3, c=2, d=0, GCD(a,c)=2 и (d-b) - -3.Поскольку 2 не делит -3, никакая зависимость невозможна.

Но как мы можем выполнить этот тест GCD на двухслойной петле?

Например,:

for (i=0; i<10; i++){
   for (j=0; j<10; j++){
       A[1+2*i + 20*j] = A[2+20*i + 2*j);
    }
}

Answer 1

Несмотря на то, что подписки могут быть разграничены, тест GCD прост в применении напрямую.В вашем примере пара индексов - [1+2*i + 20*j] и [2+20*i + 2*j], поэтому мы ищем целочисленное решение уравнения

1 + 2*i + 20*j = 2 + 20*i' + 2*j'

Переупорядочив, получим

2*i - 20*i' + 20*j - 2*j = 1

Вычислите GCD всех коэффициентов, 2, -20, 20 и -2, и посмотрите, делит ли она константу.В этом случае GCD равен 2. Поскольку 2 не делит 1, зависимости нет.

Answer 2

«Простой» способ применения GCD в случае вложенных циклов состоит в том, чтобы применять его только в тех случаях, когда сами массивы являются многомерными;исходный код использует несколько индексов, а не уже линеаризованные выражения.Конечно, если вы можете «обратно преобразовать» эти линеаризованные индексы, у вас будет эквивалент.

После того, как вы поставили задачу как проблему с множеством множителей, вы можете просто применить тест GCD «измерение за измерением».,Если какое-либо измерение не показывает никакой зависимости, то вы можете остановиться и объявить, что для всей последовательности многополюсной подписки не существует никакой зависимости.

Ключ, конечно, заключается в том, что приведение к задаче многомерного индексирования дает вам приятное свойство:сопоставление между отдельными значениями индекса и соответствующими кортежами выражений индекса.Без этого проблема сложнее.

Это подход, который я использовал в векторизованном компиляторе ASC Fortran еще в 70-х годах, и он работал довольно хорошо, особенно в сочетании с направленным анализом индексов для непересекающегося случая.Сам по себе GCD-тест действительно недостаточен, но он дает вам относительно недорогой способ раннего принятия решения в анализе в тех случаях, когда вы можете избежать более дорогостоящего анализа зависимостей.