Hispanopedia Wiki
Articulo de referencia

Prueba de Banerjee

En teoría de compiladores , la prueba de Banerjee es una prueba de dependencia . Esta prueba presupone que todos los índices de los bucles son independientes; sin embargo, en la...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de compiladores , la prueba de Banerjee es una prueba de dependencia . Esta prueba presupone que todos los índices de los bucles son independientes; sin embargo, en la práctica, esto suele ser falso. La prueba de Banerjee es conservadora, es decir, no romperá una dependencia inexistente.

Esto significa que lo único que la prueba puede garantizar es la ausencia de dependencia.

Forma general

Para un bucle de la forma:

for ( i = 0 ; i < n ; i ++ ) { c [ f ( i )] = a [ i ] + b [ i ]; /* instrucción s1 */ d [ i ] = c [ g ( i )] + e [ i ]; /* instrucción s2 */ }

Existe una verdadera dependencia entre la afirmación s1 y la afirmación s2 si y solo si  :

∃i,j∈[0,norte−1]:i≤j  y  F(i)=gramo(j){\displaystyle \exists i,j\in \left[0,n-1\right]:i\leq j~~{\textrm {y}}~~f\left(i\right)=g\left(j\right)\!}

Existe una antidependencia entre la afirmación s1 y la afirmación s2 si y solo si  :

∃i,j∈[0,norte−1]:i>j  y  F(i)=gramo(j){\displaystyle \exists i,j\in \left[0,n-1\right]:i>j~~{\textrm {y}}~~f\left(i\right)=g\left(j\right)\!}

Para un bucle de la forma:

for ( i = 0 ; i < n ; i ++ ) { c [ i ] = a [ g ( i )] + b [ i ]; /* instrucción s1 */ a [ f ( i )] = d [ i ] + e [ i ]; /* instrucción s2 */ }

Existe una verdadera dependencia entre la afirmación s1 y la afirmación s2 si y solo si  :

∃i,j∈[0,norte−1]:i<j  y  F(i)=gramo(j){\displaystyle \exists i,j\in \left[0,n-1\right]:i<j~~{\textrm {y}}~~f\left(i\right)=g\left(j\right)\!}

Ejemplo

A continuación se muestra un ejemplo de la prueba de Banerjee.

El bucle que se va a comprobar para detectar dependencias es:

for ( i = 0 ; i < 10 ; i ++ ) { c [ i + 9 ] = a [ i ] + b [ i ]; /*instrucción s1*/ d [ i ] = c [ i ] + e [ i ]; /*instrucción s2*/ }

Dejar

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

Por lo tanto,

a0=9 , a1=1,b0=0 , b1=1.{\displaystyle {\begin{array}{lcr}a_{0}=9\ ,\ a_{1}=1,\\b_{0}=0\ ,\ b_{1}=1.\\\end{array}}}

yb0−a0=−9.{\displaystyle b_{0}-a_{0}=-9.}

Pruebas de antidependencia

Entonces

Umáximo = máximo{a1×i−b1×j}  cuando  0≤j<i<norteLmin = min{a1×i−b1×j}  cuando  0≤j<i<norte,{\displaystyle {\begin{array}{lcr}U_{\max }\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {cuando}}~~0\leq j<i<n\\L_{\min }\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {cuando}}~~0\leq j<i<n,\\\end{array}}}

lo cual da

Umáximo = 9−0=9Lmin = 1−0=1.{\displaystyle {\begin{array}{lcr}U_{\max }\ =\ 9-0=9\\L_{\min }\ =\ 1-0=1.\\\end{array}}}

Ahora, los límites enb0−a0{\displaystyle b_{0}-a_{0}}son1≤−9≤9.{\displaystyle 1\leq -9\leq 9.}

Claramente, -9 no está dentro de los límites, por lo que la antidependencia se rompe.

Pruebas de dependencia verdadera

Umetroaincógnita = máximo{a1×i−b1×j}  cuando  ≤i≤j<norteLmetroinorte = min{a1×i−b1×j}  cuando  ≤i≤j<norte.{\displaystyle {\begin{array}{lcr}U_{max}\ =\ \max \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {cuando}}~~\leq i\leq j<n\\L_{min}\ =\ \min \left\{a_{1}\times i-b_{1}\times j\right\}~~{\textrm {cuando}}~~\leq i\leq j<n.\\\end{array}}}

Lo que da como resultado:

Umetroaincógnita = 9−9=0Lmetroinorte = 0−9=−9.{\displaystyle {\begin{array}{lcr}U_{max}\ =\ 9-9=0\\L_{min}\ =\ 0-9=-9.\\\end{array}}}

Ahora, los límites enb0−a0{\displaystyle b_{0}-a_{0}}son−9≤−9≤0.{\displaystyle -9\leq -9\leq 0.}

Claramente, -9 está dentro de los límites, por lo que la dependencia verdadera no se rompe.

Conclusión

Dado que la antidependencia se rompió, podemos afirmar que no existe antidependencia entre las afirmaciones.

Dado que la dependencia real no se rompió, no sabemos si existe una dependencia real entre las afirmaciones.

Por lo tanto, el bucle se puede paralelizar, pero las instrucciones deben ejecutarse en el orden de su (potencial) dependencia real.

Véase también

Referencias

  • Randy Allen y Ken Kennedy. Optimización de compiladores para arquitecturas modernas: un enfoque basado en dependencias.
  • Lastovetsky, Alex. Computación paralela en redes heterogéneas.