stringtranslate.com

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:

dónde:

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

Existen tres casos:

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

Construcción del compilador

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

Véase también

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. ^ de 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 )