Hispanopedia WikiEn informática , el análisis de dependencias de bucles es un proceso que permite encontrar dependencias dentro de las iteraciones de un bucle con el objetivo de determinar las diferentes relaciones entre las instrucciones. Estas relaciones de dependencia están ligadas al orden en que las diferentes instrucciones acceden a las ubicaciones de memoria. Mediante el análisis de estas relaciones, se puede organizar la ejecución del bucle para que varios procesadores trabajen en diferentes partes del mismo en paralelo. Esto se conoce como procesamiento paralelo . En general, los bucles pueden consumir mucho tiempo de procesamiento cuando se ejecutan como código secuencial. Mediante el procesamiento paralelo, es posible reducir el tiempo total de ejecución de un programa al distribuir la carga de procesamiento entre varios procesadores.
El proceso de organizar instrucciones para permitir que varios procesadores trabajen en diferentes partes de un bucle se conoce como paralelización . Para ver cómo podemos aprovechar la paralelización, primero debemos analizar las dependencias dentro de cada bucle. Estas dependencias ayudarán a determinar qué instrucciones del bucle deben completarse antes de que otras puedan comenzar, y qué instrucciones del bucle pueden ejecutarse en paralelo con respecto a las demás. Dos categorías generales de dependencias que se analizarán en el bucle son las dependencias de datos y las dependencias de control .
Descripción
El análisis de dependencia de bucles se realiza sobre un bucle normalizado de la forma:
para i 1 hasta U 1 hacer para i 2 hasta que U 2 haga ... para i n hasta que U n hacer cuerpo hecho ... hecho hecho
dóndecuerpopuede contener:
S1 a[f 1 (yo 1 , ..., yo n ), ..., f m (yo 1 , ..., yo n )] := ... ... S2 ... := a[h 1 (i 1 , ..., i n ), ..., h m (i 1 , ..., i n )]
Donde a es una matriz m-dimensional yf n,h n, etc. son funciones que asignan desde todos los índices de iteración (i n ) a un acceso a la memoria en una dimensión particular del arreglo.
Por ejemplo, en C:
para ( i = 0 ; i < U1 ; i ++ ) para ( j = 0 ; j < U2 ; j ++ ) a [ i + 4 - j ] = b [ 2 * i - j ] + i * j ;f 1 seríai+4-j, controlar la escritura en la primera dimensión de a y h 2 sería2*ij, controlando la lectura en la primera dimensión de b .
El objetivo del problema es encontrar todas las dependencias posibles entre S1 y S2 . Para ser conservadores, cualquier dependencia que no pueda demostrarse falsa debe asumirse como verdadera.
La independencia se demuestra al comprobar que no hay dos instancias de S1 y S2 que accedan o modifiquen el mismo punto en la matriz.aCuando se detecta una posible dependencia, el análisis de dependencias de bucles suele intentar caracterizar la relación entre las instancias dependientes, ya que aún pueden ser posibles algunas optimizaciones. También puede ser posible transformar el bucle para eliminar o modificar la dependencia.
En el curso de probar o refutar tales dependencias, una declaración S puede descomponerse según la iteración de la que proviene. Por ejemplo, S [1,3,5] se refiere a la iteración dondei1 = 1,i2 = 3yi3 = 5. Por supuesto, las referencias a iteraciones abstractas, como S [ d1 +1, d2 , d3 ], están permitidas y son comunes.
Dependencia de datos
Las dependencias de datos muestran las relaciones entre las variables en el código. Existen tres tipos diferentes de dependencias de datos:
- Dependencia verdadera (a veces denominada dependencia de flujo)
- Antidependencia
- Dependencia de la salida
Dependencia verdadera
Una dependencia verdadera se produce cuando se escribe en una ubicación de memoria antes de leerla. [ 1 ] [ 2 ] [ 3 ] Introduce riesgos de lectura después de escritura (RAW) porque la instrucción que lee de la ubicación de memoria tiene que esperar hasta que la instrucción anterior escriba en ella; de lo contrario, la instrucción de lectura leerá un valor incorrecto. [ 2 ] Un ejemplo de dependencia verdadera es:
S1 : a = 5 ; S2 : b = a ;En este ejemplo, existe una dependencia real entre S1 y S2, ya que la variable a se escribe primero en la instrucción S1 y luego se lee en la instrucción S2. Esta dependencia real se puede representar como S1 → T S2. También se observa una dependencia real al leer y escribir entre diferentes iteraciones en un bucle. El siguiente ejemplo muestra una dependencia real entre diferentes iteraciones.
para ( j = 1 ; j < n ; j ++ ) S1 : a [ j ] = a [ j -1 ];En este ejemplo, existe una dependencia real entre la instrucción S1 en la iteración j y S1 en la iteración j+1. Esta dependencia se debe a que se escribe un valor en a[j] en una iteración y luego a[j-1] lo lee en la siguiente. Esta dependencia real se puede representar como S1[j] → T S1[j+1].
Antidependencia
Una antidependencia ocurre cuando se lee una ubicación de memoria antes de que se escriba en esa misma ubicación. [ 1 ] [ 2 ] [ 3 ] Esto introduce riesgos de escritura después de la lectura (WAR, por sus siglas en inglés) porque la instrucción que escribe los datos en una ubicación de memoria tiene que esperar hasta que esa ubicación de memoria haya sido leída por la instrucción anterior; de lo contrario, la instrucción de lectura leería un valor incorrecto. [ 2 ] Un ejemplo de una antidependencia es:
S1 : a = b ; S2 : b = 5 ;En este ejemplo, existe una antidependencia entre las instrucciones S1 y S2. Esto se debe a que la variable b se lee primero en la instrucción S1 y luego se modifica en la instrucción S2. Esto se puede representar como S1 → A S2. Una antidependencia se observa en diferentes iteraciones de un bucle. El siguiente ejemplo ilustra este caso:
para ( j = 0 ; j < n -1 ; j ++ ) S1 : b [ j ] = b [ j + 1 ];En este ejemplo, existe una antidependencia entre la j-ésima iteración de S1 y el j+1-ésimo elemento de S1. Aquí, el j+1-ésimo elemento se lee antes de que ese mismo elemento se escriba en la siguiente iteración de j. Esta antidependencia se puede representar como S1[j] → A S1[j+1].
Dependencia de la salida
An output dependence occurs when a location in memory is written to before that same location is written to again in another statement.[1][2][3] This introduces write-after-write (WAW) hazards because the second instruction to write the value to a memory location needs to wait until the first instruction finishes writing data to the same memory location or else when the memory location is read at a later time it will contain the wrong value.[2] An example of an output dependence is:
S1:c=8;S2:c=15;In this example, there is an output dependence between statements S1 and S2. Here, the variable c is first written to in S1 and then variable c is written to again in statement S2. This output dependence can be represented by S1 →O S2. An output dependence can be seen by different iterations in a loop. The following code snippet shows an example of this case:
for(j=0;j<n;j++){S1:c[j]=j;S2:c[j+1]=5;}In this example, there is an output dependence between the jth element in S1 and the j+1th element in S2. Here, c[j+1] in statement S2 is written to in one iteration. In the next iteration, c[j] in statement S2, which is the same memory location as c[j+1] in the previous iteration, is written to again. This output dependence can be represented as S1[j] →O S2[j+1].
Control dependence
Control dependencies must also be considered when analyzing dependencies between different statements in a loop. Control dependencies are dependencies introduced by the code or the programming algorithm itself. They control the order in which instructions occur within the execution of code.[4] One common example is an "if" statement. "if" statements create branches in a program. The "then" portion of the "if" statement explicitly directs or controls actions to be taken.[3]
En este ejemplo, se ilustran las restricciones del flujo de control. El bloque de código 1 muestra el orden correcto al usar una instrucción `if` en el lenguaje de programación C. El bloque de código 2 ilustra un problema en el que una instrucción que debería estar controlada por la instrucción `if` ya no lo está. El bloque de código 3 ilustra un problema en el que una instrucción que no debería estar controlada por la instrucción `if` ahora está bajo su control. Ambas posibilidades podrían provocar una ejecución incorrecta del programa y deben tenerse en cuenta al paralelizar estas instrucciones dentro de un bucle.
Dependencia transmitida por el bucle frente a dependencia independiente del bucle
Las dependencias inherentes al bucle y las dependencias independientes del bucle se determinan por las relaciones entre las instrucciones en las iteraciones de un bucle. Cuando una instrucción en una iteración de un bucle depende de alguna manera de una instrucción en una iteración diferente del mismo bucle, existe una dependencia inherente al bucle. [ 1 ] [ 2 ] [ 3 ] Sin embargo, si una instrucción en una iteración de un bucle depende solo de una instrucción en la misma iteración del bucle, esto crea una dependencia independiente del bucle. [ 1 ] [ 2 ] [ 3 ]
En este ejemplo, el bloque de código 1 muestra una dependencia de bucle entre la instrucción S2 (iteración i) y la instrucción S1 (iteración i-1). Esto significa que la instrucción S2 no puede continuar hasta que la instrucción S1 de la iteración anterior haya finalizado. El bloque de código 2 muestra una dependencia independiente del bucle entre las instrucciones S1 y S2 en la misma iteración.
Grafos de recorrido del espacio de iteración y dependencia con bucles
Los grafos de recorrido del espacio de iteración (ITG) muestran la ruta que toma el código al recorrer las iteraciones del bucle. [ 1 ] Cada iteración se representa con un nodo. Los grafos de dependencia transportada por el bucle (LDG) proporcionan una representación visual de todas las dependencias verdaderas, antidependencias y dependencias de salida que existen entre diferentes iteraciones en un bucle. [ 1 ] Cada iteración se representa con un nodo.
Es más fácil mostrar la diferencia entre los dos gráficos con un bucle for anidado.
para ( i = 0 ; i < 4 ; i ++ ) para ( j = 0 ; j < 4 ; j ++ ) S1 : a [ i ][ j ] = a [ i ][ j -1 ] * x ;En este ejemplo, existe una dependencia real entre la j-ésima iteración de la instrucción S1 y la j+1-ésima instrucción de S1. Esto se puede representar como S1[i,j] →T S1[i,j+1]. El grafo de recorrido del espacio de iteración y el grafo de dependencias de bucle son: Grafo de recorrido del espacio de iteración: Grafo de dependencias de bucle:
Técnicas de análisis de dependencias de la ICC
El trabajo de Moyen, Rubiano y Seiller introdujo un nuevo análisis de dependencia del flujo de datos [ 5 ] inspirado en técnicas de complejidad computacional implícita . Lo utilizan para detectar no solo comandos invariantes en bucles, sino también fragmentos de código más grandes, como un bucle interno. El análisis también detecta cuasi-invariantes de grados arbitrarios, es decir, comandos o fragmentos de código que se vuelven invariantes después de un número fijo de iteraciones del cuerpo del bucle. La técnica fue utilizada posteriormente por Aubert, Rubiano, Rusch y Seiller [ 6 ] para paralelizar automáticamente bucles en código C y para certificar el crecimiento polinomial de variables. [ 7 ]
Véase también
Referencias
- 1 2 3 4 5 6 7 Solihin, Yan (2016). Fundamentos de la arquitectura de computadoras paralelas : sistemas multichip y multinúcleo . [Estados Unidos?]: Solihin Pub. ISBN 978-1-4822-1118-4.
- 1 2 3 4 5 6 7 8 Devan, Pradip; Kamat, RK (2014). "Una revisión: análisis de dependencia de bucles para compiladores de paralelización". Revista internacional de informática y tecnologías de la información . 5 .
- 1 2 3 4 5 6 John, Hennessy; Patterson, David (2012). «Capítulo tres: Paralelismo a nivel de instrucción y su explotación». Arquitectura de computadoras: Un enfoque cuantitativo . Morgan Kaufmann Publishers. págs. 152–156 . ISBN 978-0-12-383872-8.
- ↑ Allen, JR; Kennedy, Ken; Porterfield, Carrie; Warren, Joe (1983-01-01). "Conversión de la dependencia de control a la dependencia de datos". Actas del 10.º simposio ACM SIGACT-SIGPLAN sobre Principios de los lenguajes de programación - POPL '83 . POPL '83. Nueva York, NY, EE. UU.: ACM. págs. 177–189 . doi : 10.1145/567067.567085 . ISBN 0897910907. S2CID 39279813 .
- ↑ Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Detección de fragmentos cuasi-invariantes de bucle". Tecnología automatizada para verificación y análisis . Notas de clase en informática. Vol. 10482. págs. 91–108 . doi : 10.1007/978-3-319-68167-2_7 . ISBN 978-3-319-68166-5.
- ↑ Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2023). "Distribución y paralelización de bucles no canónicos". Verificación, comprobación de modelos e interpretación abstracta . Lecture Notes in Computer Science. Vol. 13881. pp. 91– 108. doi : 10.1007/978-3-031-24950-1_1 .
- ↑ Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2023). "pymwp: Un analizador estático que determina los límites de crecimiento polinomial". Tecnología automatizada para verificación y análisis . Notas de clase en ciencias de la computación. Vol. 14216. pp. 263– 275. doi : 10.1007/978-3-031-45332-8_14 .
- Computación paralela
