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
Una dependencia de salida ocurre cuando se escribe en una ubicación de memoria antes de que se vuelva a escribir en esa misma ubicación en otra instrucción. [ 1 ] [ 2 ] [ 3 ] Esto introduce riesgos de escritura después de escritura (WAW) porque la segunda instrucción para escribir el valor en una ubicación de memoria debe esperar hasta que la primera instrucción termine de escribir datos en la misma ubicación de memoria; de lo contrario, cuando se lea la ubicación de memoria más tarde, contendrá un valor incorrecto. [ 2 ] Un ejemplo de dependencia de salida es:
S1 : c = 8 ; S2 : c = 15 ;En este ejemplo, existe una dependencia de salida entre las instrucciones S1 y S2. Aquí, la variable c se modifica primero en S1 y luego se modifica nuevamente en la instrucción S2. Esta dependencia de salida se puede representar como S1 → S2. Una dependencia de salida se puede observar en diferentes iteraciones de un bucle. El siguiente fragmento de código muestra un ejemplo de este caso:
para ( j = 0 ; j < n ; j ++ ) { S1 : c [ j ] = j ; S2 : c [ j + 1 ] = 5 ; }En este ejemplo, existe una dependencia de salida entre el j-ésimo elemento de S1 y el j+1-ésimo elemento de S2. Aquí, en una iteración, se escribe en c[j+1] de la instrucción S2. En la siguiente iteración, se vuelve a escribir en c[j] de la instrucción S2, que se encuentra en la misma ubicación de memoria que c[j+1] en la iteración anterior. Esta dependencia de salida se puede representar como S1[j] → S2[j+1].
Dependencia del control
También deben considerarse las dependencias de control al analizar las dependencias entre diferentes instrucciones en un bucle. Las dependencias de control son dependencias introducidas por el propio código o el algoritmo de programación. Controlan el orden en que se ejecutan las instrucciones. [ 4 ] Un ejemplo común es una instrucción "if". Las instrucciones "if" crean bifurcaciones en un programa. La parte "then" de la instrucción "if" dirige o controla explícitamente las acciones que se deben realizar. [ 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
