Análisis de dependencia de bucle

Proceso para determinar relaciones entre declaraciones

El análisis de dependencia de bucle es un proceso que se puede utilizar para encontrar dependencias dentro de las iteraciones de un bucle con el objetivo de determinar diferentes relaciones entre declaraciones. Estas relaciones dependientes están ligadas al orden en el que las diferentes declaraciones acceden a las ubicaciones de la memoria. Usando el análisis de estas relaciones, la ejecución del ciclo se puede organizar para permitir que múltiples procesadores trabajen en diferentes partes del ciclo en paralelo. Esto se conoce como procesamiento paralelo . En general, los bucles pueden consumir mucho tiempo de procesamiento cuando se ejecutan como código de serie . Mediante el procesamiento en paralelo, es posible reducir el tiempo total de ejecución de un programa al compartir la carga de procesamiento entre múltiples procesadores.

El proceso de organizar declaraciones para permitir que varios procesadores trabajen en diferentes partes de un bucle se denomina a menudo paralelización . Para ver cómo podemos aprovechar la paralelización, primero tenemos que analizar las dependencias dentro de los bucles individuales. Estas dependencias ayudarán a determinar qué declaraciones en el ciclo deben completarse antes de que puedan comenzar otras declaraciones, y qué declaraciones en el ciclo se pueden ejecutar en paralelo con respecto a las otras declaraciones en el ciclo. Dos categorías generales de dependencias que se analizarán en el ciclo son las dependencias de datos y las dependencias de control.

Descripción

El análisis de dependencia de bucle se produce en un bucle normalizado de la forma:

para i 1 hasta que U 1 lo haga para i 2 hasta que U 2 lo haga ... por i n hasta U n do body hecho ... hecho
hecho

dónde cuerpo puede contener:

S1 a [f 1 (i 1 , ..., i n ), ..., f m (i 1 , ..., i n )]: = ... ...
S2 ...: = a [h 1 (i 1 , ..., i n ), ..., h m (i 1 , ..., i n )]

Donde a es una matriz de dimensiones m yf _n, h _n, etc. son funciones que mapean desde todos los índices de iteración (i _n ) a un acceso a la memoria en una dimensión particular de la matriz.

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 ₁ seríai + 4-j, controlar la escritura en la primera dimensión de a y h ₂ sería2 * ij, controlando la lectura en la primera dimensión de b .

El alcance del problema es encontrar todas las posibles dependencias entre S1 y S2 . Para ser conservador, cualquier dependencia que no pueda probarse como falsa debe asumirse como verdadera.

La independencia se muestra demostrando que no hay dos instancias de S1 y S2 que accedan o modifiquen el mismo lugar en la matriz.a. Cuando se encuentra una posible dependencia, el análisis de dependencia de bucle generalmente hace todo lo posible por caracterizar la relación entre instancias dependientes, ya que algunas optimizaciones aún pueden ser posibles. También es posible transformar el bucle para eliminar o modificar la dependencia.

En el curso de probar o refutar tales dependencias, un enunciado 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 = 3 y i3 = 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. Hay tres tipos diferentes de dependencias de datos:

• Verdadera dependencia (a veces denominada dependencia del flujo)
• Anti-dependencia
• Dependencia de la producción

Verdadera dependencia

Una verdadera dependencia se produce cuando se escribe en una ubicación de la memoria antes de leerla. ^{[1] [2] [3]} Introduce peligros de lectura después de escritura (RAW) porque la instrucción que lee desde la ubicación en la memoria tiene que esperar hasta que la instrucción anterior escriba en ella o de lo contrario la instrucción de lectura leerá el valor incorrecto. ^[2] Un ejemplo de dependencia verdadera es:

 S1 : a = 5 ;    S2 : b = a ;   

En este ejemplo, existe una verdadera dependencia entre S1 y S2 porque la variable a se escribe primero en el enunciado S1 y luego la variable a se lee en el enunciado S2. Esta verdadera dependencia se puede representar por S1 → T S2.

También se puede ver una verdadera dependencia al leer y escribir entre diferentes iteraciones en un bucle. El siguiente ejemplo muestra una verdadera dependencia entre diferentes iteraciones.

 para ( j = 1 ; j < n ; j ++ )       S1 : a [ j ] = a [ j -1 ];   

En este ejemplo, existe una verdadera dependencia entre el enunciado S1 en la j-ésima iteración y S1 en la j + 1ª iteración. Existe una verdadera dependencia porque un valor se escribirá en a [j] en una iteración y luego se leerá a [j-1] en la siguiente iteración. Esta verdadera dependencia se puede representar por S1 [j] → T S1 [j + 1].

Anti dependencia

Una anti-dependencia ocurre cuando se lee una ubicación en la memoria antes de que se escriba en esa misma ubicación. ^{[1] [2] [3]} Esto introduce peligros de escritura tras lectura (WAR) porque la instrucción que escribe los datos en una ubicación de memoria tiene que esperar hasta que la instrucción anterior o la instrucción de lectura haya leído esa ubicación de memoria. leería el valor incorrecto. ^[2] Un ejemplo de anti-dependencia es:

 S1 : a = b ;    S2 : b = 5 ;   

En este ejemplo, existe una anti-dependencia entre las declaraciones S1 y S2. Ésta es una anti-dependencia porque la variable b se lee primero en el enunciado S1 y luego se escribe en la variable b en el enunciado S2. Esto se puede representar por S1 → A S2. Una anti-dependencia se puede ver mediante diferentes iteraciones en un bucle. El siguiente ejemplo muestra un ejemplo de este caso:

 para ( j = 0 ; j < n ; j ++ )       S1 : b [ j ] = b [ j + 1 ];   

En este ejemplo, existe una anti-dependencia entre la j-ésima iteración de S1 y el j + 1º elemento de S1. Aquí, el j + 1º elemento se lee antes de que ese mismo elemento se escriba en la siguiente iteración de j. Esta anti-dependencia puede ser representada por S1 [j] → A S1 [j + 1].

Dependencia de la producción

Una dependencia de salida ocurre cuando se escribe en una ubicación en la memoria antes de que esa misma ubicación se escriba nuevamente en otra instrucción. ^{[1] [2] [3]} Esto presenta peligros de escritura tras escritura (WAW) porque la segunda instrucción para escribir el valor en una ubicación de memoria necesita esperar hasta que la primera instrucción termine de escribir datos en la misma ubicación de memoria o cuando la ubicación de la memoria se lee en un momento posterior, contendrá el 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 declaraciones S1 y S2. Aquí, la variable c se escribe primero en S1 y luego se escribe de nuevo en la variable c en el enunciado S2. Esta dependencia de la salida se puede representar mediante S1 → O S2. Una dependencia de la salida se puede ver mediante diferentes iteraciones en 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, hay una dependencia de salida entre el elemento j en S1 y el elemento j + 1 en S2. Aquí, c [j + 1] en el enunciado S2 se escribe en una iteración. En la siguiente iteración, c [j] en el enunciado S2, que es la misma ubicación de memoria que c [j + 1] en la iteración anterior, se escribe nuevamente. Esta dependencia de la salida se puede representar como S1 [j] → O S2 [j + 1].

Dependencia del control

Las dependencias de control también deben tenerse en cuenta al analizar las dependencias entre diferentes declaraciones en un bucle. Las dependencias de control son dependencias introducidas por el código o el algoritmo de programación en sí. Controlan el orden en el que ocurren las instrucciones dentro de la ejecución del código. ^[4] Un ejemplo común es una declaración "si". Las sentencias "si" crean ramas en un programa. La parte "entonces" de la declaración "si" dirige o controla explícitamente las acciones que se deben tomar. ^[3]

 // Bloque de código 1 (CORRECTO) // Bloque de código 2 (INCORRECTO) // Bloque de código 3 (INCORRECTO) if ( a == b ) then { if ( a == b ) then { if ( a == b ) then { c = "controlado" ; } c = "controlado" ;                           } c = "controlado" ; d = "no controlado" ;       d = "no controlado" ; d = "no controlado" ; }      

En este ejemplo, se ilustran las limitaciones del flujo de control. El bloque de código 1 muestra el orden correcto cuando se usa 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 se supone que está controlada por la instrucción if ya no está controlada por ella. El bloque de código 3 ilustra un problema en el que una instrucción que se supone que no está controlada por la instrucción "if" ahora se ha movido bajo su control. Ambas de estas dos posibilidades podrían conducir a una ejecución incorrecta del programa y deben tenerse en cuenta al paralelizar estas declaraciones dentro de un bucle.

Dependencia transportada por bucle frente a dependencia independiente de bucle

Las dependencias transportadas por el bucle y las dependencias independientes del bucle están determinadas por las relaciones entre las declaraciones en las iteraciones de un bucle. Cuando una declaración en una iteración de un bucle depende de alguna manera de una declaración en una iteración diferente del mismo bucle, existe una dependencia llevada por el bucle. ^{[1] [2] [3]} Sin embargo, si una declaración en una iteración de un ciclo depende sólo de una declaración en la misma iteración del ciclo, esto crea una dependencia independiente del ciclo. ^{[1] [2] [3]}

 // Bloque de código 1 // Bloque de código 2 para ( i = 1 ; i <= 4 ; i ++ ) para ( i = 0 ; i < 4 ; i ++ )                 S1 : b [ i ] = 8 ; S1 : b [ i ] = 8 ;        S2 : a [ i ] = b [ i -1 ] + 10 ; S2 : a [ i ] = b [ i ] + 10 ;           

En este ejemplo, el bloque de código 1 muestra una dependencia dependiente del bucle entre la iteración i-1 del enunciado S2 y la iteración i-1 del enunciado S1. Esto quiere decir que el enunciado S2 no puede continuar hasta que finalice el enunciado S1 en la iteración anterior. El bloque de código 2 muestra la dependencia independiente del bucle entre los enunciados S1 y S2 en la misma iteración.

Gráficos transversales de espacio de iteración y dependencia de bucle

Los gráficos transversales del espacio de iteración (ITG) muestran la ruta que toma el código al atravesar las iteraciones del bucle. ^[1] Cada iteración se representa con un nodo. Los gráficos de dependencia transportados por bucle (LDG) brindan una representación visual de todas las dependencias verdaderas, anti dependencias y dependencias de salida que existen entre las 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 verdadera dependencia entre la j iteración del enunciado S1 y el j + 1º enunciado de S1. Esto se puede representar como S1 [i, j] → T S1 [i, j + 1] El gráfico de recorrido de espacio de iteración y el gráfico de dependencia de transporte de bucle es: Gráfico de recorrido de espacio de iteración: Gráfico de dependencia de transporte de bucle:

Gráfico de dependencia en bucle (LDG)

Gráfico transversal del espacio de iteración (ITG)

Ver también

• Análisis de dependencia
• Análisis de alias
• DOPIPE
• Paralelismo a nivel de bucle
• Transformación de bucle
• División de bucle
• Fusión de bucle
• Intercambio de bucle
• Bucle sesgado
• Paralelización automática
• Vectorización automática

Referencias

1. Solihin, Yan (2016). Fundamentos de la arquitectura informática paralela: sistemas multichip y multinúcleo . [¿Estados Unidos?]: Solihin Pub. ISBN 978-1-4822-1118-4.
2. Devan, Pradip; Kamat, RK (2014). "Una revisión - Análisis de dependencia de LOOP para el compilador de paralelización". Revista Internacional de Ciencias de la Computación y Tecnologías de la Información . 5 .
3. John, Hennessy; Patterson, David (2012). Arquitectura informática: un enfoque cuantitativo . 225 Wyman Street, Waltham, MA 02451, EE. UU .: Morgan Kaufmann Publishers. págs. 152-156. doi : 10.1016 / B978-0-12-383872-8.00003-3 (inactivo el 31 de octubre de 2021). ISBN 978-0-12-383872-8.
4. Allen, JR; Kennedy, Ken; Porterfield, Carrie; Warren, Joe (1 de enero de 1983). "Conversión de la dependencia de control a la dependencia de datos". Actas del X Simposio ACM SIGACT-SIGPLAN sobre Principios de Lenguajes de Programación . POPL '83. Nueva York, NY, EE. UU .: ACM: 177–189. doi : 10.1145 / 567067.567085 . ISBN 0897910907. S2CID  39279813 .