Test de Banerji (informatique)
# Test de Banerji (informatique)

Le test de Banerji, ou en anglais Banerjee test, est un test d'analyse de dépendance des données utilisé en théorie de la compilation. Il permet de déterminer si, au sein d'une boucle, deux jeux d'instructions peuvent être exécutés en parallèle.

## Forme générale

Soient deux fragments de programme $P_1$ et $P_2,$ $P_1$ précédant $P_2$ lors de l'exécution :

* $P_1,$ ayant pour données d'entrée (inputs) $I_1$ et pour données de sortie (outputs) $O_1$ ;
* $P_2,$ ayant pour données d'entrée (inputs) $I_2$ et pour données de sortie (outputs) $O_2.$

Ces fragments sont dits indépendant si les conditions suivantes sont satisfaites :

* condition d'indépendance des flux : $P_2$ n'a pas besoin des données fournies par $P_1$ — pas de RAW (read after write) —, $I_2$ ∩ $O_1$ = ;
* condition d'antidépendance : $P_2$ ne modifie pas (n'écrase pas) les données déjà utilisées par $P_1$ — pas de WAR (write after read) —, $I_1$ ∩ $O_2$ = ;
* condition d'indépendance des sorties : $P_2$ ne modifie pas (n'écrase pas) les données déjà modifiées par $P_1$ — pas de WAW (write after write) —, $O_2$ ∩ $O_1$ =.

Le test de Banerji vérifie si les deux premières conditions sont rompues. C'est un test « prudent » (conservative) : il ne peut que garantir l'absence de dépendance.

Résultat du test :

| | Test de dépendance des flux | Test d'antidépendance |
| - | - | - |
| Vrai | Il n'y a pas de dépendance des flux | Il n'y a pas d'antidépendance |
| Faux | Il peut y avoir, ou pas, de dépendance des flux | Il peut y avoir, ou pas d'antidépendance |

Ce test vérifie l'indépendance de deux jeux d'instructions au sein d'une boucle.

### Première forme

La première forme est :

À l'étape i, on définit

* l'indice ƒ(i) du tableau a (ƒ étant une fonction entière), qui dépend de la valeur de i ;
* et l'on définit l'indice i de b, qui dépend de la valeur de g(i) (g étant une fonction entière).

Il y a une dépendance de flux si

    $\exists \{i,j\}\in [1;n]^{2}/\ i\leqslant j{\text{ et }}f(i)=g(j)$

Il y a une antidépendance si

    $\exists \{i,j\}\in [1;n]^{2}/\ i>j{\text{ et }}f(i)=g(j)$

Par exemple, avec

on a

    ƒ(i) = i + 9
    g(i) = i

Si l'on prend i = 10 et j = 1, on a

    i > j et ƒ(i) = g(j)

donc il n'y a pas antidépendance. Par contre, on ne peut pas trouver de cas où la dépendance de flux est rompue.

### Deuxième forme

La première forme est le symétrique de la première :

À l'étape i, on définit

* l'indice i du tableau a, qui dépend de la valeur de g(i) ;
* et l'on définit l'indice ƒ(i) de b, qui dépend de la valeur de i.

Il y a une dépendance de flux si

    $\exists \{i,j\}\in [1;n]^{2}/\ i<j{\text{ et }}f(i)=g(j)$

## Test de Banerji

Le test de Banerji se restreint au cas où ƒ et g sont des fonctions affines : on pose

    ƒ(i) = $a_0$ + $a_1·i$ ;
    g(i) = $b_0$ + $b_1·i.$

On veut savoir s'il existe des situations (i, j) pour lesquelles

    ƒ(i) = g(j)

c'est-à-dire

    $a_0$ + $a_1·i$ = $b_0$ + $b_1·j$

ou encore

    $a_1·i$ - $b_1·j$ = $b_0$ - $a_0$

Le test consiste à regarder si le second terme, $b_0$ - $a_0,$ se trouve dans les limites [L ; U] du premier terme :

    limite supérieure (upper limit) : U = $max{a_1·i$ - $b_1·j}$
    limite inférieure (lower limit) : L = $min{a_1·i$ - $b_1·j}$

Selon la forme de la boucle, et selon que l'on teste l'indépendance de flux ou l'antidépendance, on calcule les limites pour i ≥ j ou bien pour i ≤ j. La question posée par le test est donc

    a-t-on $\mathrm {L} \leqslant b_{0}-a_{0}\leqslant \mathrm {U}$ ?

Si c'est le cas, alors il est possible que l'on ait une dépendance ou une antidépendance. Si par contre le second terme est hors limite, alors on est sûr que l'on n'a pas de dépendance ni d'antidépendance.

