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.
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
![{\displaystyle \exists \{i,j\}\in [1;n]^{2}/\ i\leqslant j{\text{ et }}f(i)=g(j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb94310312336658f318c89976913972ffa7952a)
Il y a une antidépendance si
![{\displaystyle \exists \{i,j\}\in [1;n]^{2}/\ i>j{\text{ et }}f(i)=g(j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b89cbff21a4374b0cdfc36ed1508ae567f01aa63)
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.
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
![{\displaystyle \exists \{i,j\}\in [1;n]^{2}/\ i<j{\text{ et }}f(i)=g(j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4f83d8e8c6513f130dc5e709c3f2f7a18adb2d8)
