Dependencia de datos

En informática , una dependencia de datos es una situación en la que una instrucción de un programa hace referencia a los datos de una instrucción anterior. En la teoría de compiladores , la técnica utilizada para descubrir dependencias de datos entre instrucciones (o instrucciones) se denomina análisis de dependencia .

Descripción

Suponiendo que la declaración 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}}$
• Hay una ruta de ejecución en tiempo de ejecución factible desde hasta . ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

Estas condiciones se denominan Condiciones de Bernstein, en honor a Arthur J. Bernstein. ^[1]

Existen tres casos:

• Anti-dependencia: 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 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 después de escritura)

Una dependencia verdadera, 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 riesgo 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 la instrucción que actualiza B. La instrucción 2 depende verdaderamente de la instrucción 1, ya que el valor final de B depende de la instrucción que actualiza A. Dado que la instrucción 3 depende verdaderamente de 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. ^[2]

Anti-dependencia (escritura después de lectura)

Una antidependencia ocurre cuando una instrucción requiere un valor que se actualiza posteriormente. Una violación de una antidependencia genera un riesgo de escritura después de lectura (WAR) .

En el siguiente ejemplo, la instrucción 2 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:

Multiplicación R3, R1, R2 Sumar R2,R5,R6

Está claro que existe antidependencia entre estas dos instrucciones. Primero 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, el cambio de 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 ahora estas instrucciones se pueden ejecutar en paralelo. Sin embargo, la modificación ha introducido una nueva dependencia: la instrucción 2 ahora depende realmente 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. ^[2]

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 riesgo 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 tanto, 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 nombre . Es decir, se pueden eliminar mediante el cambio de 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, solo se ejecuta una instrucción) y en el orden especificado por el programa.

Sin embargo, las dependencias entre instrucciones o sentencias pueden obstaculizar el paralelismo (ejecución paralela de múltiples instrucciones, ya sea por un compilador paralelizador o por un procesador que explota el paralelismo a nivel de instrucción) . La ejecución imprudente de múltiples instrucciones sin considerar las dependencias relacionadas puede provocar el peligro de obtener resultados erróneos, es decir, peligros .

Relevancia en informática

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

Diseño del procesador

• Canalización de instrucciones : en los procesadores canalizados, se ejecutan varias instrucciones en paralelo en varias etapas de la 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. Por lo tanto, las dependencias de nombres entre registros deben respetarse (además de las dependencias de datos) y se resuelven, por ejemplo, mediante el cambio de nombre de los registros o el uso de marcadores . Las dependencias de datos también son relevantes para los accesos a la memoria y deben respetarse mediante técnicas de desambiguación de memoria que ejecutan instrucciones de acceso a la memoria (cargas y almacenamientos) 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 las instrucciones de manera que respeten las dependencias de los datos. Esto es fundamental para optimizar los compiladores que reorganizan el código para lograr un mejor rendimiento.
• Transformaciones de bucles : al optimizar bucles, los compiladores deben considerar las dependencias de datos para aplicar transformaciones como desenrollado de bucles, fusión o mosaico 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.

Véase también

• Análisis de dependencia
• Dependencia de control
• Análisis de dependencia de bucles § Dependencia de datos
• Peligro (arquitectura informática) § Peligros de los datos

Referencias

1. Bernstein, Arthur J. (1 de octubre de 1966). "Análisis de programas para procesamiento paralelo". IEEE Transactions on Electronic Computers . EC-15 (5): 757–763. doi :10.1109/PGEC.1966.264565.
2. John L. Hennessy ; David A. Patterson (2003). Arquitectura informática: un enfoque cuantitativo (3.ª ed.) . Morgan Kaufmann . ISBN 1-55860-724-2.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )