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

Тест на определение зависимости от компьютерной программы

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

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

Общая форма

Для цикла вида:

для ( i = 0 ; i < n ; i ++ ) { c [ f ( i )] = a [ i ] + b [ i ]; /* оператор s1 */ d [ i ] = c [ g ( i )] + e [ i ]; /* оператор s2 */ }               

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

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

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

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

Для цикла вида:

для ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ g ( i )] + b [ i ]; /* оператор s1 */ a [ f ( i )] = d [ i ] + e [ i ]; /* оператор s2 */ }               

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

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

Пример

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

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

для ( i = 0 ; i < 10 ; i ++ ) { c [ i + 9 ] = a [ i ] + b [ i ]; /*утверждение s1*/ d [ i ] = c [ i ] + e [ i ]; /*утверждение s2*/ }               

Позволять

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

Итак, поэтому,

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

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

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

Затем

${\displaystyle {\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}}}$

что дает

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

Теперь границы следующие : ${\displaystyle b_{0}-a_{0}}$ ${\displaystyle 1\leq -9\leq 9.}$

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

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

${\displaystyle {\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}}}$

Что дает:

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

Теперь границы следующие : ${\displaystyle b_{0}-a_{0}}$ ${\displaystyle -9\leq -9\leq 0.}$

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

Заключение

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

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

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

Смотрите также

• тест НОД

Ссылки

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

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