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 teoría de compiladores , la técnica utilizada para descubrir dependencias de datos entre instrucciones se denomina análisis de dependencias .

Descripción

Suponiendo una declaración $S_{1}$ y $S_{2}$ , $S_{2}$ depende de $S_{1}$ si:

\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:

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

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

Existen tres casos:

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

Tipos

Riesgos de datos

Los riesgos de datos se producen cuando las instrucciones que presentan dependencia de datos modifican los datos en diferentes etapas de una canalización. Ignorar los posibles riesgos de datos puede dar lugar a condiciones de carrera (también denominadas riesgos de carrera). Existen tres situaciones en las que puede producirse un riesgo de datos:

lectura después de escritura (RAW), una verdadera dependencia
escribir después de leer (WAR), una antidependencia
escritura tras escritura (WAW), una dependencia de salida
lectura tras lectura (RAR), una dependencia falsa

La lectura posterior a la lectura (RAR) no es un caso de riesgo.

Consideremos dos instrucciones i1 e i2 , donde i1 aparece antes que i2 en el orden del programa.

Lectura después de escritura (RAW)

( i2 intenta leer una fuente antes de que i1 escriba en ella). Un riesgo de lectura de datos después de la escritura (RAW) se refiere a una situación en la que una instrucción hace referencia a un resultado que aún no se ha calculado ni recuperado. Esto puede ocurrir porque, aunque una instrucción se ejecute después de una anterior, esta última solo se ha procesado parcialmente a través de la tubería de procesamiento.

Ejemplo

Por ejemplo:

i1. R2 <- R5 + R8 i2. R4 <- R2 + R8

La primera instrucción calcula un valor que se guardará en el registro R2 , y la segunda utiliza este valor para calcular un resultado para el registro R4 . Sin embargo, en una tubería , cuando se obtienen los operandos para la segunda operación, los resultados de la primera aún no se han guardado, lo que genera una dependencia de datos.

Se produce una dependencia de datos con la instrucción i2 , ya que depende de la finalización de la instrucción i1 .

Escribir después de leer (WAR)

( i2 intenta escribir en un destino antes de que i1 lo lea ) Un riesgo de datos de escritura después de la lectura (WAR, por sus siglas en inglés) representa un problema con la ejecución concurrente.

Ejemplo

Por ejemplo:

i1. R4 <- R1 + R5 i2. R5 <- R1 + R2

En cualquier situación en la que exista la posibilidad de que i2 termine antes que i1 (es decir, con ejecución concurrente), debe asegurarse que el resultado del registro R5 no se almacene antes de que i1 haya tenido la oportunidad de obtener los operandos.

Escritura tras escritura (WAW)

( i2 intenta escribir un operando antes de que i1 lo escriba ) Un riesgo de escritura después de la escritura (WAW) puede ocurrir en un entorno de ejecución concurrente .

Ejemplo

Por ejemplo:

i1. R5 <- R4 + R7 i2. R5 <- R1 + R3

La escritura diferida (WB) de i2 debe retrasarse hasta que i1 termine de ejecutarse.

Dependencia verdadera (lectura después de escritura)

Una dependencia verdadera, también conocida como dependencia de flujo o dependencia de datos , se produce cuando una instrucción depende del resultado de una instrucción anterior. La violación de una dependencia verdadera conlleva un riesgo de lectura después de la escritura (RAW) .

1. A = 3 2. B = A 3. C = B

La instrucción 3 depende realmente 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 realmente 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 realmente de la instrucción 2 y la instrucción 2 depende realmente de la instrucción 1, la instrucción 3 también depende realmente de la instrucción 1. Por lo tanto, el paralelismo a nivel de instrucción no es una opción en este ejemplo. ^{[ 2 ]}

Antidependencia (escribir después de leer)

Se produce una antidependencia cuando una instrucción requiere un valor que posteriormente se actualiza. La violación de una antidependencia conlleva un riesgo de escritura después de la lectura (WAR, por sus siglas en inglés) .

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

1. B = 3 2. A = B + 1 3. B = 7

Ejemplo:

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

Es evidente que existe una antidependencia entre estas dos instrucciones. Primero leemos R2 y luego, en la segunda instrucción, le asignamos un nuevo valor.

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 = 3 N. B2 = B 2. A = B² + 1 3. 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 pueden ejecutarse en paralelo.

Nótese que aún existe una dependencia de lectura después de escritura: la instrucción 2 depende realmente de la instrucción N, que a su vez depende realmente de la instrucción 1. Esta dependencia existía en la versión original, donde la instrucción 2 dependía realmente de la instrucción 1. Esta dependencia no se puede eliminar de forma segura. ^{[ 2 ]}

Dependencia de salida (escritura tras escritura)

Se produce una dependencia de salida cuando el orden de las instrucciones afecta al valor final de una variable. La violación de esta dependencia conlleva un riesgo de escritura tras escritura (WAW, por sus siglas en inglés) .

En el ejemplo siguiente, 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 = 3 2. A = B + 1 3. B = 7

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

1. B2 = 3 2. A = B² + 1 3. B = 7

Trascendencia

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

Sin embargo, las dependencias entre sentencias o instrucciones pueden dificultar el paralelismo (la ejecución paralela de múltiples instrucciones, ya sea mediante un compilador paralelizador o mediante un procesador que aprovecha el paralelismo a nivel de instrucción) . Ejecutar múltiples instrucciones de forma imprudente sin considerar las dependencias relacionadas puede generar el riesgo de obtener resultados erróneos, es decir, riesgos .

Relevancia en informática

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

Diseño de procesadores

Segmentación de instrucciones : En los procesadores segmentados, varias instrucciones se ejecutan en paralelo en múltiples etapas de la segmentación. Por lo tanto, las dependencias de datos entre los registros deben respetarse y gestionarse en la segmentación del procesador. Las dependencias más relevantes son las dependencias reales, que se resuelven, por ejemplo, deteniendo la segmentació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, deben respetarse las dependencias de nombres entre registros (además de las dependencias de datos), las cuales se resuelven, por ejemplo, mediante el cambio de nombre de registros o el uso de marcadores . Las dependencias de datos también son relevantes para los accesos a memoria y deben respetarse mediante técnicas de desambiguación de memoria que ejecutan las instrucciones de acceso a memoria (cargas y almacenamientos) fuera del orden del programa.

Construcción de compiladores

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

Planificación de instrucciones : Los compiladores deben planificar las instrucciones respetando las dependencias de datos. Esto es fundamental para optimizar los compiladores, que reorganizan el código para mejorar el rendimiento.
Transformaciones de bucles : Al optimizar bucles, los compiladores deben tener en cuenta las dependencias de datos para aplicar transformaciones como el desenrollado , la fusión o la segmentación 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.

Véase también

Referencias

↑ 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 .
1 2 John L. Hennessy ; David A. Patterson (2003). Arquitectura de computadoras: un enfoque cuantitativo (3.ª ed.) . Morgan Kaufmann . ISBN 1-55860-724-2.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )

[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 .

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

[ 1 ]

[ 2 ]