La desambiguación de memoria es un conjunto de técnicas empleadas por microprocesadores de alto rendimiento que ejecutan instrucciones de acceso a memoria (cargas y almacenamientos) fuera del orden del programa. Los mecanismos para realizar la desambiguación de memoria, implementados mediante lógica digital dentro del núcleo del microprocesador, detectan dependencias verdaderas entre operaciones de memoria en el momento de la ejecución y permiten que el procesador se recupere cuando se ha violado una dependencia. También eliminan dependencias de memoria falsas y permiten un mayor paralelismo a nivel de instrucción al permitir la ejecución segura fuera de orden de cargas y almacenamientos.
Al intentar ejecutar instrucciones fuera de orden, un microprocesador debe respetar las dependencias verdaderas entre instrucciones . Por ejemplo, considere una dependencia verdadera simple:
1: suma $1, $2, $3 # R1 <= R2 + R32: suma $5, $1, $4 # R5 <= R1 + R4 (depende de 1)
En este ejemplo, la addinstrucción en la línea 2 depende de la addinstrucción en la línea 1 porque el registro R1 es un operando fuente de la operación de adición en la línea 2. La instrucción adden la línea 2 no se puede ejecutar hasta que la addinstrucción en la línea 1 se complete. En este caso, la dependencia es estática y un microprocesador la determina fácilmente, porque las fuentes y los destinos son registros. El registro de destino de la addinstrucción en la línea 1 ( R1) es parte de la codificación de la instrucción, y por lo tanto el microprocesador puede determinarlo al principio, durante la etapa de decodificación de la secuencia de comandos. De manera similar, los registros fuente de la addinstrucción en la línea 2 ( R1y R4) también están codificados en la instrucción misma y se determinan en la decodificación. Para respetar esta verdadera dependencia, la lógica del programador 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 1 estén disponibles cuando la instrucción 2 los necesite.
Las complicaciones surgen cuando la dependencia no se puede determinar estáticamente. Estas dependencias no estáticas surgen 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 codificación de la instrucción.
1: almacenar $1, 2($2) # Mem[R2+2] <= R12: cargar $3, 4($4) # R3 <= Mem[R4+4] (posiblemente dependa 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 se pueden ejecutar correctamente fuera de orden. Sin embargo, si las ubicaciones son las mismas, entonces la instrucción de carga depende del almacenamiento para producir su valor. Esto se conoce como una 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 ensamblado MIPS :
1: mul $27, $27, $202: sw $27, 0 ($30)3: $08,0 ($31)4: sw $26, 0 ($30)5: $09,0 ($31)
Suponga que la lógica de programación emitirá una instrucción a la unidad de ejecución cuando todos sus operandos de registro estén listos. Además, suponga que los registros $30y $31están listos: los valores en $30y $31se calcularon hace mucho tiempo y no han cambiado. Sin embargo, suponga $27que no está listo: su valor aún está en proceso de ser calculado por la mulinstrucción. Finalmente, suponga 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 en la línea 2 no está lista para ejecutarse, pero la lw $08, 0($31)instrucción en la línea 3 sí lo está. Si el procesador permite que la lwinstrucción se ejecute antes de sw, la carga leerá un valor antiguo del sistema de memoria; sin embargo, debería haber leído el valor que acaba de escribir allí el sw. La carga y el almacenamiento se ejecutaron fuera del orden del programa, pero había una dependencia de memoria entre ellos que se violó.
De manera similar, supongamos que el registro $26 está listo. La sw $26, 0($30)instrucción en la línea 4 también está lista para ejecutarse y puede ejecutarse antes que la instrucción anterior lw $08, 0($31)en la línea 3. Si esto ocurre, la lw $08, 0($31)instrucción leerá el 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 vienen en tres formas:
Las tres dependencias se muestran en el segmento de código anterior (reproducido para mayor claridad):
1: división $27, $202: sw $27, 0 ($30)3: $08,0 ($31)4: sw $26, 0 ($30)5: $09,0 ($31)
lw $08, 0($31)instrucción en la línea 3 tiene una dependencia RAW de la sw $27, 0($30)instrucción en la línea 2, y la lw $09, 0($31)instrucción en la línea 5 tiene una dependencia RAW de la sw $26, 0($30)instrucción en la línea 4. Ambas instrucciones de carga leen la dirección de memoria que escribieron los almacenes anteriores. Los almacenes fueron los productores más recientes de esa dirección de memoria, y las cargas están leyendo el valor de esa dirección de memoria.sw $26, 0($30)instrucción en la línea 4 tiene una dependencia WAR de la lw $08, 0($31)instrucción en la línea 3 ya que escribe la dirección de memoria desde la cual lee la carga anterior.sw $26, 0($30)instrucción en la línea 4 tiene una dependencia WAW de la sw $27, 0($30)instrucción en la línea 2 ya que ambas tiendas escriben en la misma dirección de memoria.Los microprocesadores modernos utilizan los siguientes mecanismos, implementados en hardware , para resolver dependencias ambiguas y recuperarse cuando se viola una dependencia.
Los valores de las instrucciones de almacenamiento no se asignan al sistema de memoria (en los microprocesadores modernos, caché de CPU ) cuando se ejecutan. En cambio, las instrucciones de almacenamiento, incluida la dirección de memoria y los datos de almacenamiento, se almacenan en una cola de almacenamiento hasta que alcanzan el punto de retiro. Cuando un almacenamiento se retira, escribe su valor en el sistema de memoria. Esto evita los problemas de dependencia de WAR y WAW que se muestran en el fragmento de código anterior, donde una carga anterior recibe un valor incorrecto del sistema de memoria porque se permitió que un almacenamiento posterior se ejecutara antes de la carga anterior.
Además, el almacenamiento en búfer de los almacenes hasta su retiro permite a los procesadores ejecutar especulativamente instrucciones de almacenamiento que siguen a una instrucción que puede producir una excepción (como una carga de una dirección incorrecta, dividir por cero, etc.) o una instrucción de bifurcación 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 de la bifurcación 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 la bifurcación 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 incorrecta de la bifurcación. La complicación para los almacenes es que cualquier almacén en la ruta incorrecta o mal predicha no debería haber comprometido sus valores en el sistema de memoria; Si las tiendas hubieran comprometido sus valores, sería imposible "descartar" la confirmación y el estado de la memoria de la máquina se corrompería con los datos de una instrucción de almacenamiento que no debería haberse ejecutado.
Por lo tanto, sin el almacenamiento en búfer de almacenamiento, los almacenes no pueden ejecutarse hasta que se hayan ejecutado todas las instrucciones anteriores que posiblemente causaron excepciones (y no causaron una excepción) y se conozcan todas las direcciones de bifurcación anteriores. Forzar a los almacenes a esperar hasta que se conozcan las direcciones de bifurcación y las excepciones reduce significativamente la agresividad fuera de orden y limita el ILP ( paralelismo a nivel de instrucción ) y el rendimiento. Con el almacenamiento en búfer de almacenamiento, los almacenes pueden ejecutarse antes de las instrucciones de bifurcación que causan excepciones o no se resuelven, almacenando en búfer sus datos en la cola de almacenamiento pero sin confirmar sus valores hasta el retiro. Esto evita que los almacenes en rutas mal predichas o incorrectas confirmen sus valores en el sistema de memoria mientras siguen ofreciendo el ILP y el rendimiento aumentados de la ejecución completa fuera de orden de los almacenes.
El almacenamiento en búfer de los almacenes hasta su retiro evita las dependencias de WAW y WAR, pero introduce un nuevo problema. Considere el siguiente escenario: un almacén se ejecuta y almacena en búfer su dirección y sus datos en la cola de almacenes. Unas pocas instrucciones más tarde, se ejecuta una carga que lee desde la misma dirección de memoria en la que el almacén acaba de escribir. Si la carga lee sus datos desde el sistema de memoria, leerá un valor antiguo que habría sido sobrescrito por el almacén anterior. Los datos obtenidos por la carga serán incorrectos.
Para resolver este problema, los procesadores emplean una técnica llamada reenvío de almacenamiento a carga utilizando la cola de almacenamiento. Además de almacenar en búfer los almacenamientos hasta su retiro, la cola de almacenamiento cumple un segundo propósito: reenviar datos desde los almacenamientos completados pero aún no retirados ("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 utilizando la dirección de memoria. Cuando se ejecuta una carga, busca en la cola de almacenamiento los almacenamientos en tránsito en la misma dirección que estén lógicamente antes 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 ya debe haberse retirado y comprometido sus valores. Esta técnica permite que las cargas obtengan datos correctos si su almacenamiento productor se ha completado pero aún no se ha retirado.
Es posible que en la cola de almacenamiento haya varios almacenes en la dirección de memoria de la carga. Para manejar este caso, la cola de almacenamiento se codifica por prioridad para seleccionar el último almacén que sea lógicamente anterior a la carga en el orden del programa. La determinación de qué almacén es el "más reciente" se puede lograr adjuntando algún tipo de marca de tiempo a las instrucciones a medida que se obtienen y decodifican, o alternativamente conociendo la posición relativa (ranura) de la carga con respecto a los almacenes más antiguos y más nuevos dentro de la cola de almacenamiento.
Las CPU modernas fuera de servicio pueden utilizar una serie de técnicas para detectar una violación de dependencia RAW, pero todas las técnicas requieren el seguimiento de las cargas en curso desde su ejecución hasta su retiro. Cuando se ejecuta una carga, accede al sistema de memoria o a la cola de almacenamiento para obtener su valor de datos, y luego su dirección y datos se almacenan en una cola de carga hasta su retiro. La cola de carga es similar en estructura y función a la cola de almacenamiento y, de hecho, en algunos procesadores puede combinarse con la cola de almacenamiento en una única estructura denominada cola de carga-almacenamiento o LSQ . Las siguientes técnicas se utilizan o se han propuesto para detectar violaciones de dependencia RAW:
Con esta técnica, la cola de carga, al igual que la cola de almacenamiento, es una CAM que se busca utilizando la dirección de acceso a la memoria y mantiene un registro de todas las cargas en curso. Cuando se ejecuta un almacenamiento, busca en la cola de carga cargas completadas desde la misma dirección que estén lógicamente más adelante en el orden del programa. Si existe una carga coincidente, debe haberse ejecutado antes del almacenamiento y, por lo tanto, haber leído un valor incorrecto y antiguo del sistema de memoria/cola de almacenamiento. Cualquier instrucción que haya utilizado el valor de la carga también ha utilizado datos incorrectos. Para recuperarse si se detecta una violación de este tipo, la carga se marca como "violada" en el búfer de retiro. El almacenamiento permanece en la cola de almacenamiento y el búfer de retiro y se retira normalmente, comprometiendo su valor al sistema de memoria cuando se retira. Sin embargo, cuando la carga violada alcanza el punto de retiro, el procesador vacía la tubería y reinicia la ejecución desde la instrucción de carga. En este punto, todos los almacenamientos anteriores han comprometido sus valores en el sistema de memoria. La instrucción de carga leerá ahora el valor correcto del sistema de memoria y cualquier instrucción dependiente se volverá a ejecutar utilizando el valor correcto.
Esta técnica requiere una búsqueda asociativa de la cola de carga en cada ejecución de almacenamiento, lo que consume energía del circuito y puede resultar una ruta de sincronización difícil para colas de carga grandes. Sin embargo, no requiere puertos de memoria ( caché ) adicionales ni crea conflictos de recursos con otras cargas o almacenamientos que se estén ejecutando.
Con esta técnica, las instrucciones de carga que se han ejecutado fuera de orden se vuelven a ejecutar (acceden al sistema de memoria y leen el valor de su dirección una segunda vez) cuando llegan al punto de retiro. Dado que la carga es ahora la instrucción que se retira, no tiene dependencias de ninguna instrucción que aún esté en curso; todos los almacenamientos anteriores han comprometido sus valores en el sistema de memoria, por lo que se garantiza que cualquier valor leído desde el sistema de memoria sea correcto. El valor leído desde la memoria en el momento de la reejecución se compara con el valor obtenido cuando se ejecutó la carga por primera vez. Si los valores son los mismos, el valor original era correcto y no se ha producido ninguna violación. Si el valor de la reejecución difiere del valor original, se ha producido una violación RAW y se debe vaciar la tubería porque las instrucciones que dependen de la carga han utilizado un valor incorrecto.
Esta técnica es conceptualmente más simple que la búsqueda en cola de carga y elimina un segundo CAM y su búsqueda que consume mucha energía (la cola de carga ahora puede ser una cola FIFO simple). Dado que la carga debe volver a acceder al sistema de memoria justo antes del retiro, el acceso debe ser muy rápido, por lo que este esquema se basa en una caché rápida. Sin embargo, independientemente de lo rápida que sea la caché, el segundo acceso al sistema de memoria para cada instrucción de carga fuera de orden aumenta la latencia de retiro de instrucciones y aumenta el número total de accesos a la caché que debe realizar el procesador. El acceso adicional a la caché en el momento del retiro se puede satisfacer reutilizando un puerto de caché existente; sin embargo, esto crea una contención de recursos del puerto con otras cargas y almacenamientos en el procesador que intentan ejecutarse y, por lo tanto, puede causar una disminución en el rendimiento. Alternativamente, se puede agregar un puerto de caché adicional solo para la desambiguación de la carga, pero esto aumenta la complejidad, la potencia y el área de la caché. Algunos trabajos recientes (Roth 2005) han mostrado formas de filtrar muchas cargas para que no se vuelvan a ejecutar si se sabe que no podría haberse producido ninguna violación de la dependencia RAW; Esta técnica ayudaría a eliminar dicha latencia y contención de recursos.
Un beneficio menor de este esquema (en comparación con una búsqueda de cola de carga) es que no marcará una violación de dependencia de RAW ni activará un vaciado de la tubería si un almacenamiento que hubiera causado una violación de dependencia de RAW (la dirección del almacenamiento coincide con la dirección de una carga en curso) tiene un valor de datos que coincide con el valor de datos que ya se encuentra en la memoria caché. En el esquema de búsqueda de cola de carga, se necesitaría agregar una comparación de datos adicional al hardware de búsqueda de cola de carga para evitar dicho vaciado de la tubería.
Las CPU que admiten totalmente la ejecución fuera de orden de cargas y almacenamientos deben poder detectar violaciones de dependencia de RAW cuando ocurren. Sin embargo, muchas CPU evitan este problema al obligar a que todas las cargas y almacenamientos se ejecuten en orden, o al admitir solo una forma limitada de ejecución de carga/almacenamiento fuera de orden. Este enfoque ofrece un rendimiento menor en comparación con la compatibilidad total con la ejecución fuera de orden de carga/almacenamiento, pero puede reducir significativamente la complejidad del núcleo de ejecución y las memorias caché.
La primera opción, que consiste en hacer que las cargas y los almacenamientos se ejecuten en orden, evita las dependencias RAW porque no existe la posibilidad de que una carga se ejecute antes que su almacenamiento productor y obtenga datos incorrectos. Otra posibilidad es dividir de manera efectiva las cargas y los almacenamientos en dos operaciones: generación de direcciones y acceso a la caché. Con estas dos operaciones separadas pero vinculadas, la CPU puede permitir que las cargas y los almacenamientos accedan al sistema de memoria solo una vez que todas las cargas y almacenamientos anteriores hayan tenido su dirección generada y almacenada en el LSQ. Después de la generación de direcciones, ya no hay dependencias ambiguas ya que se conocen todas las direcciones y, por lo tanto, las cargas dependientes no se ejecutarán hasta que se completen sus almacenamientos correspondientes. Este esquema aún permite cierto "desorden": las operaciones de generación de direcciones para cualquier carga y almacenamiento en curso pueden ejecutarse fuera de orden y, una vez que se han generado las direcciones, los accesos a la caché para cada carga o almacenamiento pueden ocurrir en cualquier orden que respete las dependencias verdaderas (ahora conocidas).
Los procesadores que admiten totalmente la ejecución de cargas y almacenamientos fuera de orden pueden utilizar una técnica adicional relacionada, denominada predicción de dependencia de memoria , para intentar predecir las dependencias reales entre cargas y almacenamientos antes de que se conozcan sus direcciones. Con 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 ese almacenamiento se complete, lo que evita una violación de la dependencia RAW y, por lo tanto, evita el vaciado de la canalización y la penalización de rendimiento que se produce. Consulte el artículo sobre predicción de dependencia de memoria para obtener más detalles.