Dependencia de datos

Una dependencia de datos en informática es una situación en la que una declaración de programa (instrucción) se refiere a los datos de una declaración anterior. En la teoría del compilador , la técnica utilizada para descubrir dependencias de datos entre declaraciones (o instrucciones) se llama análisis de dependencia .

Descripción

Suponiendo enunciado y , depende de si: ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle S_{2}}$ ${\displaystyle S_{1}}$

${\displaystyle \left[I(S_{1})\cap O(S_{2})\right]\cup \left[O(S_{1})\cap I(S_{2})\right]\cup \left[O(S_{1})\cap O(S_{2})\right]\neq \varnothing }$

dónde:

• ${\displaystyle I(S_{i})}$es el conjunto de ubicaciones de memoria leídas por , ${\displaystyle S_{i}}$
• ${\displaystyle O(S_{j})}$es el conjunto de ubicaciones de memoria escritas por , y ${\displaystyle S_{j}}$
• existe una ruta de ejecución factible en tiempo de ejecución desde hasta . ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

Esta condición se llama condición de Bernstein, nombrada por AJ Bernstein.

Existen tres casos:

• Antidependencia: y lee algo antes de sobrescribirlo ${\displaystyle I(S_{1})\cap O(S_{2})\neq \varnothing }$ ${\displaystyle S_{1}\rightarrow S_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$
• Dependencia de flujo (datos): y escribe antes de algo leído por ${\displaystyle O(S_{1})\cap I(S_{2})\neq \varnothing }$ ${\displaystyle S_{1}\rightarrow S_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$
• Dependencia de salida: y ambos escriben en la misma ubicación de memoria. ${\displaystyle O(S_{1})\cap O(S_{2})\neq \varnothing }$ ${\displaystyle S_{1}\rightarrow S_{2}}$

Tipos

Dependencia verdadera (lectura tras escritura)

Una verdadera dependencia, también conocida como dependencia de flujo o dependencia de datos , ocurre cuando una instrucción depende del resultado de una instrucción anterior. Una violación de una dependencia verdadera genera un peligro de lectura después de escritura (RAW) .

1.A = 32. B = A3. C = B

La instrucción 3 depende verdaderamente de la instrucción 2, ya que el valor final de C depende de que la instrucción actualice B. La instrucción 2 depende verdaderamente de la instrucción 1, ya que el valor final de B depende de que la instrucción actualice A. Dado que la instrucción 3 es verdaderamente dependiente sobre la instrucción 2 y la instrucción 2 depende verdaderamente de la instrucción 1, la instrucción 3 también depende verdaderamente de la instrucción 1. Por lo tanto , el paralelismo a nivel de instrucción no es una opción en este ejemplo. ^[1]

Antidependencia (escritura tras lectura)

Una antidependencia ocurre cuando una instrucción requiere un valor que luego se actualiza. Una violación de una antidependencia genera un peligro de escritura tras lectura (WAR) .

En el siguiente ejemplo, la instrucción 2 no depende de la instrucción 3: el orden de estas instrucciones no se puede cambiar ni se pueden ejecutar en paralelo (posiblemente cambiando el orden de las instrucciones), ya que esto afectaría el valor final de A.

1. B = 32. A = B + 13. B = 7

Ejemplo:

MUL R3,R1,R2 AÑADIR R2,R5,R6

Está claro que existe una antidependencia entre estas 2 instrucciones. Al principio leemos R2 y luego, en la segunda instrucción, escribimos un nuevo valor para él.

Una antidependencia es un ejemplo de dependencia de nombre . Es decir, cambiar el nombre de las variables podría eliminar la dependencia, como en el siguiente ejemplo:

1. B = 3N. B2 = B2. A = B2 + 13. B = 7

Se ha declarado una nueva variable, B2, como copia de B en una nueva instrucción, la instrucción N. Se ha eliminado la antidependencia entre 2 y 3, lo que significa que estas instrucciones ahora se pueden ejecutar en paralelo. Sin embargo, la modificación ha introducido una nueva dependencia: la instrucción 2 ahora depende verdaderamente de la instrucción N, que a su vez depende realmente de la instrucción 1. Como dependencias de flujo, estas nuevas dependencias son imposibles de eliminar de forma segura. ^[1]

Dependencia de salida (escritura tras escritura)

Una dependencia de salida ocurre cuando el orden de las instrucciones afectará el valor de salida final de una variable. Una violación de una dependencia de salida genera un peligro de escritura tras escritura (WAW) .

En el siguiente ejemplo, existe una dependencia de salida entre las instrucciones 3 y 1; cambiar el orden de las instrucciones en este ejemplo cambiará el valor final de A, por lo que estas instrucciones no se pueden ejecutar en paralelo.

1. B = 32. A = B + 13. B = 7

Al igual que con las antidependencias, las dependencias de salida son dependencias de nombres . Es decir, se pueden eliminar cambiando el nombre de las variables, como en la siguiente modificación del ejemplo anterior:

1. B2 = 32. A = B2 + 13. B = 7

Trascendencia

Los programas convencionales se escriben asumiendo el modelo de ejecución secuencial . Según este modelo, las instrucciones se ejecutan una tras otra, de forma atómica (es decir, en un momento dado, sólo se ejecuta una instrucción) y en el orden especificado por el programa.

Sin embargo, las dependencias entre declaraciones o instrucciones pueden obstaculizar el paralelismo: ejecución paralela de múltiples instrucciones, ya sea mediante un compilador paralelizador o mediante un procesador que explota el paralelismo a nivel de instrucciones . La ejecución imprudente de múltiples instrucciones sin considerar las dependencias relacionadas puede causar el peligro de obtener resultados incorrectos, es decir, peligros .

Relevancia en informática

Las dependencias de datos son relevantes en diversas áreas de la informática, particularmente en el diseño de procesadores, la construcción de compiladores, la informática paralela y la programación concurrente.

Diseño de procesador

• Canalización de instrucciones : en los procesadores canalizados, se ejecutan múltiples instrucciones en paralelo en múltiples etapas de canalización. Por lo tanto, las dependencias de datos entre registros deben respetarse y manejarse en la canalización del procesador. Las más relevantes son las dependencias verdaderas que se resuelven, por ejemplo, deteniendo la canalización o reenviando operandos .
• Ejecución fuera de orden : los procesadores modernos suelen ejecutar instrucciones fuera de su orden original para mejorar el rendimiento. De este modo, se deben respetar las dependencias de nombres entre registros (además de las dependencias de datos) y se resuelven, por ejemplo, cambiando el nombre de los registros o mediante marcadores . Las dependencias de datos también son relevantes para los accesos a la memoria y deben ser respetadas mediante técnicas de desambiguación de la memoria que ejecutan instrucciones de acceso a la memoria (cargas y tiendas) fuera del orden del programa.

Construcción del compilador

Las dependencias de datos son relevantes para varias optimizaciones del compilador , por ejemplo

• Programación de instrucciones : los compiladores deben programar instrucciones de manera que respeten las dependencias de los datos. Esto es crucial para optimizar los compiladores que reorganizan el código para obtener un mejor rendimiento.
• Transformaciones de bucle : al optimizar bucles, los compiladores deben considerar las dependencias de datos para aplicar transformaciones como desenrollado, fusión o mosaico de bucles sin cambiar la semántica del programa.
• Movimiento de código : cuando un compilador considera mover un fragmento de código, debe asegurarse de que no se violen las dependencias de datos.

Ver también

• Análisis de dependencia
• Controlar la dependencia
• Análisis de dependencia de bucle § Dependencia de datos
• Peligro (arquitectura de computadora) § Peligros de datos

Referencias

1. John L. Hennessy ; David A. Patterson (2003). Arquitectura de Computadores: un enfoque cuantitativo (3ª ed.) . Morgan Kaufman . ISBN 1-55860-724-2.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )