Coherencia y sincronización de caché
En este capítulo, discutiremos los protocolos de coherencia de caché para hacer frente a los problemas de inconsistencia de múltiples cachés.
El problema de la coherencia de la caché
En un sistema multiprocesador, la inconsistencia de datos puede ocurrir entre niveles adyacentes o dentro del mismo nivel de la jerarquía de memoria. Por ejemplo, la caché y la memoria principal pueden tener copias inconsistentes del mismo objeto.
Como varios procesadores operan en paralelo, y de forma independiente, múltiples cachés pueden poseer diferentes copias del mismo bloque de memoria, esto crea cache coherence problem. Cache coherence schemes Ayude a evitar este problema manteniendo un estado uniforme para cada bloque de datos en caché.
Sea X un elemento de datos compartidos que ha sido referenciado por dos procesadores, P1 y P2. Al principio, tres copias de X son consistentes. Si el procesador P1 escribe un nuevo dato X1 en la caché, usandowrite-through policy, la misma copia se escribirá inmediatamente en la memoria compartida. En este caso, se produce una incoherencia entre la memoria caché y la memoria principal. Cuando unawrite-back policy se utiliza, la memoria principal se actualizará cuando los datos modificados en la caché sean reemplazados o invalidados.
En general, hay tres fuentes de problemas de inconsistencia:
- Compartir datos grabables
- Migración de procesos
- Actividad de E / S
Protocolos de bus de Snoopy
Los protocolos de Snoopy logran la coherencia de datos entre la memoria caché y la memoria compartida a través de un sistema de memoria basado en bus. Write-invalidate y write-update Las políticas se utilizan para mantener la coherencia de la caché.
En este caso, tenemos tres procesadores P1, P2 y P3 que tienen una copia consistente del elemento de datos 'X' en su memoria caché local y en la memoria compartida (Figura-a). El procesador P1 escribe X1 en su memoria caché usandowrite-invalidate protocol. Por lo tanto, todas las demás copias se invalidan a través del bus. Se denota por 'I' (Figura-b). Los bloques invalidados también se conocen comodirty, es decir, no deben utilizarse. loswrite-update protocolactualiza todas las copias de la caché a través del bus. Mediante el usowrite back cache, la copia de la memoria también se actualiza (Figura-c).
Caché de eventos y acciones
Los siguientes eventos y acciones ocurren en la ejecución de comandos de invalidación y acceso a la memoria:
Read-miss- Cuando un procesador quiere leer un bloque y no está en la caché, se produce un error de lectura. Esto inicia unbus-readoperación. Si no existe una copia sucia, la memoria principal que tiene una copia coherente proporciona una copia a la memoria caché solicitante. Si existe una copia sucia en una memoria caché remota, esa caché restringirá la memoria principal y enviará una copia a la memoria caché solicitante. En ambos casos, la copia de caché entrará en el estado válido después de un error de lectura.
Write-hit - Si la copia está sucia o reservedestado, la escritura se realiza localmente y el nuevo estado está sucio. Si el nuevo estado es válido, el comando de invalidación de escritura se transmite a todas las cachés, invalidando sus copias. Cuando se escribe en la memoria compartida, el estado resultante se reserva después de esta primera escritura.
Write-miss- Si un procesador no puede escribir en la memoria caché local, la copia debe provenir de la memoria principal o de una memoria caché remota con un bloque sucio. Esto se hace enviando unread-invalidatecomando, que invalidará todas las copias de caché. Luego, la copia local se actualiza con el estado sucio.
Read-hit - Read-hit siempre se realiza en la memoria caché local sin causar una transición de estado o usar el bus snoopy para invalidación.
Block replacement- Cuando una copia está sucia, se debe volver a escribir en la memoria principal mediante el método de reemplazo de bloques. Sin embargo, cuando la copia está en estado válido, reservado o inválido, no se realizará ningún reemplazo.
Protocolos basados en directorios
Al utilizar una red de varias etapas para construir un multiprocesador grande con cientos de procesadores, los protocolos de caché de Snoopy deben modificarse para adaptarse a las capacidades de la red. Dado que la transmisión es muy costosa de realizar en una red de varias etapas, los comandos de coherencia se envían solo a los cachés que guardan una copia del bloque. Esta es la razón del desarrollo de protocolos basados en directorios para multiprocesadores conectados a la red.
En un sistema de protocolos basado en directorios, los datos que se van a compartir se colocan en un directorio común que mantiene la coherencia entre los cachés. Aquí, el directorio actúa como un filtro donde los procesadores piden permiso para cargar una entrada desde la memoria primaria a su memoria caché. Si se cambia una entrada, el directorio la actualiza o invalida las otras cachés con esa entrada.
Mecanismos de sincronización de hardware
La sincronización es una forma especial de comunicación en la que, en lugar del control de datos, se intercambia información entre procesos de comunicación que residen en el mismo o en diferentes procesadores.
Los sistemas multiprocesador utilizan mecanismos de hardware para implementar operaciones de sincronización de bajo nivel. La mayoría de los multiprocesadores tienen mecanismos de hardware para imponer operaciones atómicas tales como operaciones de lectura, escritura o lectura-modificación-escritura de memoria para implementar algunas primitivas de sincronización. Aparte de las operaciones de memoria atómica, algunas interrupciones entre procesadores también se utilizan con fines de sincronización.
Coherencia de caché en máquinas de memoria compartida
Mantener la coherencia de la caché es un problema en el sistema multiprocesador cuando los procesadores contienen memoria caché local. La inconsistencia de datos entre diferentes cachés se produce fácilmente en este sistema.
Las áreas de mayor preocupación son:
- Compartir datos grabables
- Migración de procesos
- Actividad de E / S
Compartir datos grabables
Cuando dos procesadores (P1 y P2) tienen el mismo elemento de datos (X) en sus cachés locales y un proceso (P1) escribe en el elemento de datos (X), ya que los cachés son caché local de escritura directa de P1, la memoria principal es también actualizado. Ahora, cuando P2 intenta leer el elemento de datos (X), no encuentra X porque el elemento de datos en la caché de P2 se ha quedado obsoleto.
Migración de procesos
En la primera etapa, la caché de P1 tiene el elemento de datos X, mientras que P2 no tiene nada. Un proceso en P2 escribe primero en X y luego migra a P1. Ahora, el proceso comienza a leer el elemento de datos X, pero como el procesador P1 tiene datos desactualizados, el proceso no puede leerlos. Entonces, un proceso en P1 escribe en el elemento de datos X y luego migra a P2. Después de la migración, un proceso en P2 comienza a leer el elemento de datos X pero encuentra una versión desactualizada de X en la memoria principal.
Actividad de E / S
Como se ilustra en la figura, se agrega un dispositivo de E / S al bus en una arquitectura multiprocesador de dos procesadores. Al principio, ambos cachés contienen el elemento de datos X. Cuando el dispositivo de E / S recibe un nuevo elemento X, almacena el nuevo elemento directamente en la memoria principal. Ahora, cuando P1 o P2 (suponga que P1) intenta leer el elemento X, obtiene una copia desactualizada. Entonces, P1 escribe en el elemento X. Ahora, si el dispositivo de E / S intenta transmitir X, obtiene una copia desactualizada.
Acceso uniforme a la memoria (UMA)
La arquitectura Uniform Memory Access (UMA) significa que la memoria compartida es la misma para todos los procesadores del sistema. Las clases populares de máquinas UMA, que se utilizan comúnmente para (archivos) servidores, son los denominados multiprocesadores simétricos (SMP). En un SMP, todos los recursos del sistema como la memoria, los discos, otros dispositivos de E / S, etc. son accesibles por los procesadores de manera uniforme.
Acceso a memoria no uniforme (NUMA)
En la arquitectura NUMA, hay varios clústeres SMP que tienen una red interna indirecta / compartida, que están conectados en una red de paso de mensajes escalable. Por lo tanto, la arquitectura NUMA es una arquitectura de memoria distribuida físicamente compartida lógicamente.
En una máquina NUMA, el controlador de caché de un procesador determina si una referencia de memoria es local a la memoria del SMP o es remota. Para reducir el número de accesos a memoria remota, las arquitecturas NUMA generalmente aplican procesadores de almacenamiento en caché que pueden almacenar en caché los datos remotos. Pero cuando se trata de cachés, es necesario mantener la coherencia del caché. Por tanto, estos sistemas también se conocen como CC-NUMA (Cache Coherent NUMA).
Arquitectura de memoria caché únicamente (COMA)
Las máquinas COMA son similares a las máquinas NUMA, con la única diferencia de que las memorias principales de las máquinas COMA actúan como cachés asociativos de mapas directos o conjuntos. Los bloques de datos se transfieren a una ubicación en la caché de DRAM de acuerdo con sus direcciones. Los datos que se obtienen de forma remota se almacenan en la memoria principal local. Además, los bloques de datos no tienen una ubicación de inicio fija, pueden moverse libremente por todo el sistema.
Las arquitecturas COMA tienen en su mayoría una red jerárquica de paso de mensajes. Un conmutador en un árbol de este tipo contiene un directorio con elementos de datos como subárbol. Dado que los datos no tienen una ubicación de inicio, deben buscarse explícitamente. Esto significa que un acceso remoto requiere un recorrido a lo largo de los conmutadores del árbol para buscar en sus directorios los datos necesarios. Entonces, si un conmutador en la red recibe múltiples solicitudes de su subárbol para los mismos datos, los combina en una sola solicitud que se envía al padre del conmutador. Cuando los datos solicitados regresan, el conmutador envía múltiples copias de ellos por su subárbol.
COMA versus CC-NUMA
A continuación se muestran las diferencias entre COMA y CC-NUMA.
COMA tiende a ser más flexible que CC-NUMA porque COMA apoya de manera transparente la migración y replicación de datos sin la necesidad del sistema operativo.
Las máquinas COMA son caras y complejas de construir porque necesitan hardware de gestión de memoria no estándar y el protocolo de coherencia es más difícil de implementar.
Los accesos remotos en COMA suelen ser más lentos que los de CC-NUMA, ya que es necesario atravesar la red del árbol para encontrar los datos.