Desambiguación de la memoria

Al intentar ejecutar instrucciones fuera de orden, un microprocesador debe respetar las dependencias reales entre las instrucciones . Por ejemplo, consideremos una dependencia real simple:

1: sumar $1, $2, $3 # R1 <= R2 + R3 2: sumar $5, $1, $4 # R5 <= R1 + R4 (depende de 1)

En este ejemplo, la addinstrucción de la línea 2 depende de la addinstrucción de la línea 1 porque el registro R1 es un operando fuente de la operación de suma en la línea 2. La addinstrucción de la línea 2 no puede ejecutarse hasta que la addde la línea 1 se complete. En este caso, la dependencia es estática y fácilmente determinable por un microprocesador, ya que las fuentes y los destinos son registros. El registro de destino de la addinstrucción de la línea 1 ( R1) forma parte de la codificación de la instrucción, por lo que el microprocesador puede determinarlo al principio, durante la etapa de decodificación de la tubería. De manera similar, los registros fuente de la addinstrucción de la línea 2 ( R1y R4) también están codificados en la propia instrucción y se determinan durante la decodificación. Para respetar esta dependencia real, la lógica del planificador del microprocesador emitirá estas instrucciones en el orden correcto (primero la instrucción 1, seguida de la instrucción 2) de modo que los resultados de la instrucción 1 estén disponibles cuando la instrucción 2 los necesite.

Surgen complicaciones cuando la dependencia no se puede determinar estáticamente. Estas dependencias no estáticas aparecen con las instrucciones de memoria (cargas y almacenamientos) porque la ubicación del operando puede especificarse indirectamente como un operando de registro en lugar de especificarse directamente en la propia codificación de la instrucción.

1: almacenar $1, 2($2) # Mem[R2+2] <= R1 2: cargar $3, 4($4) # R3 <= Mem[R4+4] (posiblemente dependiente de 1, posible misma dirección que la anterior)

Aquí, la instrucción de almacenamiento escribe un valor en la ubicación de memoria especificada por el valor en la dirección (R2+2), y la instrucción de carga lee el valor en la ubicación de memoria especificada por el valor en la dirección (R4+4). El microprocesador no puede determinar estáticamente, antes de la ejecución, si las ubicaciones de memoria especificadas en estas dos instrucciones son diferentes o son la misma ubicación, porque las ubicaciones dependen de los valores en R2 y R4. Si las ubicaciones son diferentes, las instrucciones son independientes y pueden ejecutarse correctamente fuera de orden. Sin embargo, si las ubicaciones son la misma, entonces la instrucción de carga depende de la de almacenamiento para producir su valor. Esto se conoce como dependencia ambigua .

La ejecución de cargas y almacenamientos fuera de orden puede producir resultados incorrectos si un par de carga/almacenamiento dependiente se ejecutó fuera de orden. Considere el siguiente fragmento de código, dado en lenguaje ensamblador MIPS :

1: mul $27, $27, $20 2: sw $27, 0 ($30) 3: lw $08, 0 ($31) 4: sw $26, 0 ($30) 5: lw $09, 0 ($31)

Supongamos que la lógica de planificación emitirá una instrucción a la unidad de ejecución cuando todos sus operandos de registro estén listos. Además, supongamos que los registros $30y $31están listos: los valores en $30y $31se calcularon hace mucho tiempo y no han cambiado. Sin embargo, supongamos $27que no está listo: su valor aún se está calculando mediante la mulinstrucción. Finalmente, supongamos que los registros $30y $31contienen el mismo valor, y por lo tanto, todas las cargas y almacenamientos en el fragmento acceden a la misma palabra de memoria.

En esta situación, la sw $27, 0($30)instrucción de la línea 2 no está lista para ejecutarse, pero la lw $08, 0($31)de la línea 3 sí. Si el procesador permite que la lwinstrucción se ejecute antes que la de la línea 3 sw, la instrucción de carga leerá un valor antiguo del sistema de memoria; sin embargo, debería haber leído el valor que la instrucción swde carga y almacenamiento acababa de escribir. Las instrucciones de carga y almacenamiento se ejecutaron fuera de orden, pero existía una dependencia de memoria entre ellas que se violó.

De igual forma, supongamos que el registro $26está listo. La sw $26, 0($30)instrucción de la línea 4 también está lista para ejecutarse y podría ejecutarse antes que la lw $08, 0($31)de la línea 3. Si esto ocurre, la lw $08, 0($31)instrucción leerá un valor incorrecto del sistema de memoria, ya que una instrucción de almacenamiento posterior escribió su valor allí antes de que se ejecutara la carga.

Las dependencias de memoria se presentan en tres variantes:

• Dependencias de lectura después de escritura (RAW): También conocidas como dependencias verdaderas, las dependencias RAW surgen cuando una operación de carga lee un valor de la memoria que fue producido por la operación de escritura anterior más reciente en esa misma dirección.
• Dependencias de escritura después de lectura (WAR, por sus siglas en inglés): También conocidas como antidependencias, las dependencias WAR surgen cuando una operación de almacenamiento escribe en la memoria un valor que una carga anterior lee.
• Dependencias de escritura después de escritura (WAW): También conocidas como dependencias de salida, las dependencias WAW surgen cuando dos operaciones de almacenamiento escriben valores en la misma dirección de memoria .

Las tres dependencias se muestran en el segmento de código anterior (reproducido para mayor claridad):

1: div $27, $20 2: sw $27, 0 ($30) 3: lw $08, 0 ($31) 4: sw $26, 0 ($30) 5: lw $09, 0 ($31)

• La lw $08, 0($31)instrucción de la línea 3 tiene una dependencia directa (RAW) de la sw $27, 0($30)instrucción de la línea 2, y la lw $09, 0($31)instrucción de la línea 5 tiene una dependencia directa (RAW) de la sw $26, 0($30)instrucción de la línea 4. Ambas instrucciones de carga leen la dirección de memoria que escribieron las instrucciones de escritura anteriores. Las instrucciones de escritura fueron las más recientes en acceder a esa dirección de memoria, y las instrucciones de carga leen el valor de esa dirección.
• La sw $26, 0($30)instrucción de la línea 4 tiene una dependencia WAR con respecto a la lw $08, 0($31)instrucción de la línea 3, ya que escribe la dirección de memoria de la que lee la carga anterior.
• La sw $26, 0($30)instrucción de la línea 4 tiene una dependencia WAW con respecto a la sw $27, 0($30)instrucción de la línea 2, ya que ambas escrituras se realizan en la misma dirección de memoria.

Los valores de las instrucciones de almacenamiento no se guardan en la memoria (en los microprocesadores modernos, en la caché de la CPU ) durante su ejecución. En su lugar, las instrucciones de almacenamiento, incluyendo la dirección de memoria y los datos, se almacenan temporalmente en una cola hasta que finalizan su ejecución. Cuando una instrucción de almacenamiento finaliza su ejecución, escribe su valor en la memoria. Esto evita los problemas de dependencia WAR y WAW que se muestran en el fragmento de código anterior, donde una carga anterior recibe un valor incorrecto de la memoria porque se permitió que una instrucción de almacenamiento posterior se ejecutara antes que la anterior.

Además, el almacenamiento en búfer de escrituras hasta su retiro permite a los procesadores ejecutar especulativamente instrucciones de escritura que siguen a una instrucción que puede producir una excepción (como una carga de una dirección incorrecta, división por cero, etc.) o una instrucción de salto condicional cuya dirección (tomada o no tomada) aún no se conoce. Si la instrucción que produce la excepción no se ha ejecutado o la dirección del salto se predijo incorrectamente, el procesador habrá obtenido y ejecutado instrucciones en una "ruta incorrecta". Estas instrucciones no deberían haberse ejecutado en absoluto; la condición de excepción debería haber ocurrido antes de que se ejecutara cualquiera de las instrucciones especulativas, o el salto debería haber ido en la otra dirección y haber provocado que se obtuvieran y ejecutaran instrucciones diferentes. El procesador debe "descartar" cualquier resultado de las instrucciones ejecutadas especulativamente en la ruta incorrecta cuando descubre la excepción o la predicción errónea del salto. La complicación para las escrituras es que cualquier escritura en la ruta incorrecta o predicha erróneamente no debería haber confirmado sus valores en el sistema de memoria; Si los almacenes hubieran confirmado sus valores, sería imposible "desechar" la confirmación, y el estado de la memoria de la máquina se corrompería con datos de una instrucción de almacenamiento que no debería haberse ejecutado.

Por lo tanto, sin almacenamiento en búfer de escritura, las escrituras no pueden ejecutarse hasta que se hayan ejecutado todas las instrucciones previas que pudieran causar excepciones (y no hayan causado ninguna excepción) y se conozcan todas las direcciones de bifurcación previas. Obligar a las escrituras a esperar hasta que se conozcan las direcciones de bifurcación y las excepciones reduce significativamente la agresividad de la ejecución fuera de orden y limita el paralelismo a nivel de instrucción (ILP ) y el rendimiento. Con el almacenamiento en búfer de escritura, las escrituras pueden ejecutarse antes que las instrucciones de bifurcación que causan excepciones o que no se han resuelto, almacenando sus datos en la cola de escritura pero sin confirmar sus valores hasta su finalización. Esto evita que las escrituras en rutas erróneas o incorrectas confirmen sus valores en el sistema de memoria, al tiempo que ofrece el mayor ILP y rendimiento que proporciona la ejecución fuera de orden completa de las escrituras.

Almacenar en búfer las operaciones de escritura hasta su retiro evita las dependencias de WAW y WAR, pero introduce un nuevo problema. Consideremos el siguiente escenario: una operación de escritura se ejecuta y almacena en búfer su dirección y datos en la cola de escritura. Unas instrucciones después, se ejecuta una operación de carga que lee de la misma dirección de memoria en la que la operación de escritura acaba de escribir. Si la carga lee sus datos del sistema de memoria, leerá un valor antiguo que habría sido sobrescrito por la operación de escritura anterior. Los datos obtenidos por la carga serán incorrectos.

Para resolver este problema, los procesadores emplean una técnica denominada reenvío de almacenamiento a carga mediante la cola de almacenamiento. Además de almacenar temporalmente los datos almacenados hasta su finalización, la cola de almacenamiento cumple una segunda función: reenviar datos de almacenamientos completados pero aún no finalizados ("en tránsito") a cargas posteriores. En lugar de una simple cola FIFO , la cola de almacenamiento es en realidad una memoria direccionable por contenido (CAM) que se busca mediante la dirección de memoria. Cuando se ejecuta una carga, busca en la cola de almacenamiento almacenamientos en tránsito dirigidos a la misma dirección que sean lógicamente anteriores en el orden del programa. Si existe un almacenamiento coincidente, la carga obtiene su valor de datos de ese almacenamiento en lugar del sistema de memoria. Si no hay un almacenamiento coincidente, la carga accede al sistema de memoria como de costumbre; cualquier almacenamiento coincidente anterior debe haber finalizado y confirmado sus valores. Esta técnica permite que las cargas obtengan los datos correctos si su almacenamiento productor ha finalizado pero aún no se ha finalizado.

En la cola de almacenamiento pueden existir múltiples escrituras dirigidas a la dirección de memoria de la carga. Para gestionar este caso, la cola de almacenamiento se codifica por prioridad para seleccionar la escritura más reciente que sea lógicamente anterior a la carga en el orden del programa. La determinación de cuál es la escritura más reciente se puede lograr adjuntando una marca de tiempo a las instrucciones a medida que se obtienen y decodifican, o bien conociendo la posición relativa (ranura) de la carga con respecto a las escrituras más antiguas y más recientes dentro de la cola.

Los procesadores que admiten completamente la ejecución de cargas y almacenamientos fuera de orden pueden usar una técnica adicional relacionada, llamada predicción de dependencias de memoria , para intentar predecir las dependencias reales entre cargas y almacenamientos antes de que se conozcan sus direcciones. Mediante esta técnica, el procesador puede evitar que las cargas que se prevé que dependan de un almacenamiento en curso se ejecuten antes de que este finalice, evitando así una violación de dependencia RAW y, por lo tanto, evitando el vaciado de la tubería y la penalización de rendimiento que esto conlleva. Consulte el artículo sobre predicción de dependencias de memoria para obtener más detalles.