В теории компиляторов тест наибольшего общего делителя ( тест НОД ) — это тест, используемый при изучении оптимизации циклов и анализе зависимостей циклов для проверки зависимости между операторами цикла.
Тест наибольшего общего делителя (GCD) — это тест, используемый в теории компиляторов информатики для изучения оптимизации цикла и анализа зависимости цикла для проверки зависимости между операторами цикла.
Всякий раз, когда последовательный цикл, такой как цикл for , делается параллельным, чтобы его можно было выполнять более чем на одном процессоре — как в случае распределенных вычислений или кластерных вычислений — тогда определенные зависимости (например, проверка потоковой (истинной) зависимости оператора ) проверяются, чтобы узнать, можно ли распараллелить цикл . Согласно этому тесту, сравнивая индексы двух массивов , присутствующих в двух или более операторах , можно вычислить, допустимо ли распараллеливать цикл или нет.
Трудно анализировать ссылки на массивы во время компиляции, чтобы определить зависимость данных (указывают ли они на один и тот же адрес или нет). Простым и достаточным тестом на отсутствие зависимости является тест наибольшего общего делителя (НОД). Он основан на наблюдении, что если существует петлевая зависимость между 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 и GCD(a,c)=2, а (db) равно -3. Поскольку 2 не делит -3, никакая зависимость невозможна.
Чтобы решить, существует ли циклическая зависимость (две ссылки на массив обращаются к одной и той же ячейке памяти, и одна из них является операцией записи) между a[x*i+k] и a[y*i+m], обычно используется [ слова ласки ] нужно решить уравнение [ почему? ]
Если GCD(x,y) делит (mk), то может существовать некоторая зависимость в операторе цикла s1 и s2. Если GCD(x,y) не делится на (mk), то оба оператора независимы и могут выполняться параллельно. Точно так же этот тест проводится для всех операторов, присутствующих в данном цикле.