НОД тест

В теории компиляторов наибольшего общего делителя тест ( НОД ) — это тест, используемый при изучении оптимизации цикла и анализе зависимостей цикла для проверки зависимости между операторами цикла.

Описание

Тест наибольшего общего делителя информатики (НОД) — это тест, используемый в теории компиляторов для изучения оптимизации цикла и анализа зависимостей цикла для проверки зависимости между операторами цикла.

Использовать

Всякий раз, когда последовательный цикл, такой как цикл for, делается параллельным, чтобы его можно было выполнять более чем на одном процессоре (как в случае грид-вычислений или кластерных вычислений ), тогда определенные зависимости (например, проверка потоковой (истинной) зависимости оператора ) проверяются, чтобы узнать, можно ли распараллелить цикл . Согласно этому тесту, сравнивая индексы двух массивов, присутствующих в двух или более операторах , можно вычислить, законно ли распараллеливать цикл или нет.

Обоснование

Теорема

Линейное диофантово уравнение

 a1*x1 + a2*x2 +... + an*xn =c

имеет целочисленное решение x1, x2,..., xn тогда и только тогда, когда НОД (a1,a2,.., an) делит c.

Например

 2*x1 -2*x2 =1

НОД(2,-2) =2, 2 не может делить 1. Таким образом, для приведенного выше уравнения не существует целочисленного решения.

Анализ зависимостей

Трудно анализировать ссылки на массивы во время компиляции, чтобы определить зависимость данных (указывают ли они на один и тот же адрес или нет). Простым и достаточным тестом на отсутствие зависимости является тест наибольшего общего делителя (НОД). Он основан на наблюдении, что если между X[a*i + b] и X[c*i + d] существует зависимость, переносимая циклом (где X — массив; a, b, c и d — целые числа, а i – переменная цикла), то НОД (c, a) должен делить (d – b). Предполагается, что цикл должен быть нормализован – написан так, чтобы индекс/переменная цикла начиналась с 1 и увеличивалась на 1 на каждой итерации. Например, в следующем цикле a=2, b=3, c=2, d=0, НОД(a,c)=2 и (db) равно -3. Поскольку 2 не делит -3, никакая зависимость невозможна.

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

Процесс

Код цикла в целом:

for (int i=0; i<n; i++)
{
  s1   a[x*i+k] = ...;
  s2   ... = a[y*i+m];               
}

Чтобы решить, существует ли зависимость, переносимая в цикле (две ссылки на массив обращаются к одной и той же ячейке памяти, и одна из них является операцией записи) между a[x*i+k] и a[y*i+m], обычно ^{[ ласковые слова ]} нужно решить уравнение ^{[ почему? ]}

x*i1 +k = y*i2+m   (Or x*i1 -y*i2 = m -k)

Где 0<=i1, i2 <n и i1 != i2.

Если НОД(x,y) делит (mk), то в операторах цикла s1 и s2 может существовать некоторая зависимость. Если НОД(x,y) не делит (mk), то оба оператора независимы и могут выполняться параллельно. Аналогично этот тест проводится для всех операторов, присутствующих в данном цикле.

Конкретный пример исходного кода на C будет выглядеть так:

for (int i=0; i<100; i++)
{
  s1 a[2*i] = b[i];
  s2 c[i] = a[4*i+1];
}

НОД (2,4) равен 2, а делимое равно 1. Поскольку 2 не может правильно разделить 1 (оставляя нулевой остаток), между s1 и s2 нет зависимости, и преобразования цикла можно применять различные другие методы .

См. также

Ссылки

Продвинутый дизайн и реализация компилятора Стивена Мучника