Accueil🇫🇷Chercher

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 P1 et P2, P1 précédant P2 lors de l'exécution :

  • P1, ayant pour données d'entrée (inputs) I1 et pour données de sortie (outputs) O1 ;
  • P2, ayant pour données d'entrée (inputs) I2 et pour données de sortie (outputs) O2.

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

  • condition d'indépendance des flux : P2 n'a pas besoin des données fournies par P1 — pas de RAW (read after write) —, I2 ∩ O1 = {} ;
  • condition d'antidépendance : P2 ne modifie pas (n'écrase pas) les données déjà utilisées par P1 — pas de WAR (write after read) —, I1 ∩ O2 = {} ;
  • condition d'indépendance des sorties : P2 ne modifie pas (n'écrase pas) les données déjà modifiées par P1 — pas de WAW (write after write) —, O2 ∩ O1 = {}.

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 :

pour i allant de 1 à n
   a(f(i)) = fonction1(i);
   b(i) = fonction2(g(i));
fin

À 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

Il y a une antidépendance si

Par exemple, avec

pour i allant de 1 à n
   a(i + 9) = f1(i);
   b(i) = f2(i);
fin

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 :

pour i allant de 1 à n
   a(i) = fonction1(g(i));
   b(f(i)) = fonction2(i);
fin

À 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

Test de Banerji

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

ƒ(i) = a0 + a1·i ;
g(i) = b0 + b1·i.

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

Æ’(i) = g(j)

c'est-à-dire

a0 + a1·i = b0 + b1·j

ou encore

a1·i - b1·j = b0 - a0

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

limite supérieure (upper limit) : U = max{a1·i - b1·j}
limite inférieure (lower limit) : L = min{a1·i - b1·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 ?

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.

Voir aussi

Cet article est une traduction partielle de l'article en anglais.

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.