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

• P₁, ayant pour données d'entrée (inputs) I₁ et pour données de sortie (outputs) O₁ ;
• P₂, ayant pour données d'entrée (inputs) I₂ et pour données de sortie (outputs) O₂.

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

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

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

$\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

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

$\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₀ + a₁·i ;

g(i) = b₀ + b₁·i.

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

ƒ(i) = g(j)

c'est-à-dire

a₀ + a₁·i = b₀ + b₁·j

ou encore

a₁·i - b₁·j = b₀ - a₀

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

limite supérieure (upper limit) : U = max{a₁·i - b₁·j}

limite inférieure (lower limit) : L = min{a₁·i - b₁·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.

Voir aussi

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

Liens externes

• [(en) Compiling for Parallelism & Locality], Michelle Mills Strout, Colorado State University