тест Банерджи

В теории компиляторов тест Банерджи является тестом зависимости . Тест Банерджи предполагает, что все индексы цикла независимы, однако на самом деле это часто не так. Тест Банерджи является консервативным тестом. То есть не сломает зависимость, которой нет.

Это значит, что единственное, что может гарантировать тест – это отсутствие зависимости.

	Антизависимость сломана	Истинная зависимость разрушена
Истинный	Нет антизависимости	Нет истинные зависимости
ЛОЖЬ	Может быть, а может и не быть антизависимости	Может быть, а может и не быть истинные зависимости

Общая форма

Для цикла формы:

for(i=0; i<n; i++) {
    c[f(i)] = a[i] + b[i]; /* statement s1 */
    d[i] = c[g(i)] + e[i];    /* statement s2 */
}

Истинная зависимость существует между утверждением s1 и утверждением s2 тогда и только тогда, когда:

$\exists i,j\in \left[0,n-1\right]:i\leq j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!$

Антизависимость существует между утверждениями s1 и утверждениями s2 тогда и только тогда, когда:

$\exists i,j\in \left[0,n-1\right]:i>j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!$

Для цикла формы:

for(i=0; i<n; i++) {
    c[i] = a[g(i)] + b[i]; /* statement s1 */
    a[f(i)] = d[i] + e[i];    /* statement s2 */
}

Истинная зависимость существует между утверждением s1 и утверждением s2 тогда и только тогда, когда:

$\exists i,j\in \left[0,n-1\right]:i<j~~{\textrm {and}}~~f\left(i\right)=g\left(j\right)\!$

Пример

Ниже приведен пример теста Банерджи.

Цикл, который необходимо проверить на зависимость:

for(i=0; i<10; i++)  {
    c[i+9] = a[i] + b[i]; /*statement s1*/
    d[i] = c[i] + e[i];    /*statement s2*/
}

Позволять

${\begin{array}{lcr}f(i)\ =\ i+9\\g(j)\ =\ j+0.\end{array}}$

Поэтому,

${\begin{array}{lcr}a_{0}=9\ ,\ a_{1}=1,\\b_{0}=0\ ,\ b_{1}=1.\\\end{array}}$

и $b_{0}-a_{0}=-9.$

Тестирование на антизависимость

Затем

${\begin{array}{lcr}U_{\max }\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~0\leq j<i<n\\L_{\min }\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~0\leq j<i<n,\\\end{array}}$

что дает

${\begin{array}{lcr}U_{\max }\ =\ 9-0=9\\L_{\min }\ =\ 1-0=1.\\\end{array}}$

Теперь границы $b_{0}-a_{0}$ являются $1\leq -9\leq 9.$

Очевидно, что -9 выходит за эти пределы, поэтому антизависимость нарушена.

Тестирование на истинную зависимость

${\begin{array}{lcr}U_{max}\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~\leq i\leq j<n\\L_{min}\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {when}}~~\leq i\leq j<n.\\\end{array}}$

Что дает:

${\begin{array}{lcr}U_{max}\ =\ 9-9=0\\L_{min}\ =\ 0-9=-9.\\\end{array}}$

Теперь границы $b_{0}-a_{0}$ являются $-9\leq -9\leq 0.$

Очевидно, что -9 находится внутри границ, поэтому истинная зависимость не нарушается.

Заключение

Поскольку антизависимость нарушена, мы можем утверждать, что между утверждениями не существует антизависимости.

Поскольку истинная зависимость не была нарушена, мы не знаем, существует ли истинная зависимость между утверждениями.

Следовательно, цикл можно распараллеливать, но операторы должны выполняться в порядке их (потенциальной) истинной зависимости.

См. также

НОД тест

Ссылки

Рэнди Аллен и Кен Кеннеди. Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях

Ластовецкий, Алекс. Параллельные вычисления в гетерогенных сетях