Hispanopedia Wiki
Articulo de referencia

Coherencia de caché

Si dos clientes tienen una copia en caché de un bloque de memoria específico y uno de ellos modifica dicho bloque, la copia del otro cliente debe invalidarse o actualizarse. De ...

Hispanopedia WikiContenido en espanolLectura gratuita
Si dos clientes tienen una copia en caché de un bloque de memoria específico y uno de ellos modifica dicho bloque, la copia del otro cliente debe invalidarse o actualizarse. De lo contrario, el sistema se encuentra en un estado incoherente: contiene dos registros diferentes del mismo bloque de memoria que afirman estar actualizados.
Cachés incoherentes: Las cachés tienen valores diferentes para una misma ubicación de dirección.

En arquitectura de computadoras , la coherencia de caché es la uniformidad de los datos de recursos compartidos que se almacenan en múltiples cachés locales . En un sistema con coherencia de caché, si varios clientes tienen una copia en caché de la misma región de un recurso de memoria compartida, todas las copias son idénticas. Sin coherencia de caché, un cambio realizado en la región por un cliente puede no ser visto por otros, y pueden producirse errores cuando los datos utilizados por diferentes clientes no coinciden. [ 1 ]

Se utiliza un protocolo de coherencia de caché para mantener la coherencia de la caché. Los dos tipos principales son los protocolos de inspección y los basados ​​en directorios .

La coherencia de la caché es de particular relevancia en los sistemas multiprocesador , donde cada CPU puede tener su propia caché local de un recurso de memoria compartida.

Cachés coherentes: El valor en todas las copias de las cachés es el mismo.

Descripción general

En un sistema multiprocesador de memoria compartida con una memoria caché independiente para cada procesador, es posible tener varias copias de datos compartidos: una en la memoria principal y otra en la caché local de cada procesador que los solicitó. Cuando se modifica una de las copias de datos, las demás deben reflejar dicho cambio. La coherencia de caché es el mecanismo que garantiza que los cambios en los valores de los operandos (datos) compartidos se propaguen por todo el sistema de forma oportuna. [ 2 ]

Los siguientes son los requisitos para la coherencia de caché: [ 3 ]

Escribir propagación
Los cambios realizados en los datos de cualquier caché deben propagarse a otras copias (de esa línea de caché) en las cachés pares.
Serialización de transacciones
Las operaciones de lectura/escritura en una única ubicación de memoria deben ser vistas por todos los procesadores en el mismo orden.

Teóricamente, la coherencia se puede realizar a nivel de carga/almacenamiento . Sin embargo, en la práctica, generalmente se realiza a nivel de bloques de caché. [ 4 ]

Definición

La coherencia define el comportamiento de las lecturas y escrituras en una única ubicación de dirección. [ 3 ]

En un sistema multiprocesador, considere que más de un procesador ha almacenado en caché una copia de la ubicación de memoria X. Las siguientes condiciones son necesarias para lograr la coherencia de caché: [ 5 ]

  1. En una lectura realizada por un procesador P a una ubicación X que sigue a una escritura del mismo procesador P a X, sin que se produzcan escrituras en X por parte de otro procesador entre las instrucciones de escritura y lectura realizadas por P, X siempre debe devolver el valor escrito por P.
  2. En una lectura realizada por el procesador P1 a la ubicación X, seguida de una escritura realizada por otro procesador P2 a X, sin que se produzcan otras escrituras en X por parte de ningún procesador entre ambos accesos y con una separación suficiente entre la lectura y la escritura, X siempre debe devolver el valor escrito por P2. Esta condición define el concepto de vista coherente de la memoria. La propagación de las escrituras a la ubicación de memoria compartida garantiza que todas las cachés tengan una vista coherente de la memoria. Si el procesador P1 lee el valor anterior de X, incluso después de la escritura de P2, decimos que la memoria es incoherente.

Las condiciones anteriores satisfacen los criterios de propagación de escritura necesarios para la coherencia de caché. Sin embargo, no son suficientes, ya que no satisfacen la condición de serialización de transacciones . Para ilustrar esto mejor, considere el siguiente ejemplo:

Un sistema multiprocesador consta de cuatro procesadores: P1, P2, P3 y P4, que contienen copias en caché de una variable compartida S cuyo valor inicial es 0. El procesador P1 cambia el valor de S (en su copia en caché) a 10, tras lo cual el procesador P2 cambia el valor de S en su propia copia en caché a 20. Si solo se garantiza la propagación de escritura, P3 y P4 verán los cambios realizados en S por P1 y P2. Sin embargo, P3 puede ver el cambio realizado por P1 después de ver el cambio realizado por P2 y, por lo tanto, devolver 10 al leer S. P4, por otro lado, puede ver los cambios realizados por P1 y P2 en el orden en que se realizan y, por lo tanto, devolver 20 al leer S. Los procesadores P3 y P4 ahora tienen una visión incoherente de la memoria.

Por lo tanto, para satisfacer la serialización de transacciones y, por consiguiente, lograr la coherencia de caché, se debe cumplir la siguiente condición junto con las dos anteriores mencionadas en esta sección:

  • Las escrituras en la misma ubicación deben ser secuenciadas. En otras palabras, si la ubicación X recibe dos valores diferentes, A y B, en este orden, de dos procesadores cualesquiera, los procesadores nunca pueden leer la ubicación X como B y luego leerla como A. La ubicación X debe ser vista con los valores A y B en ese orden. [ 6 ]

The alternative definition of a coherent system is via the definition of sequential consistency memory model: "the cache coherent system must appear to execute all threads’ loads and stores to a single memory location in a total order that respects the program order of each thread".[4] Thus, the only difference between the cache coherent system and sequentially consistent system is in the number of address locations the definition talks about (single memory location for a cache coherent system, and all memory locations for a sequentially consistent system).

Another definition is: "a multiprocessor is cache consistent if all writes to the same memory location are performed in some sequential order".[7]

Rarely, but especially in algorithms, coherence can instead refer to the locality of reference. Multiple copies of the same data can exist in different cache simultaneously and if processors are allowed to update their own copies freely, an inconsistent view of memory can result.

Coherence mechanisms

The two most common mechanisms of ensuring coherency are snooping and directory-based, each having their own benefits and drawbacks.[8] Snooping based protocols tend to be faster, if enough bandwidth is available, since all transactions are a request/response seen by all processors. The drawback is that snooping isn't scalable. Every request must be broadcast to all nodes in a system, meaning that as the system gets larger, the size of the (logical or physical) bus and the bandwidth it provides must grow. Directories, on the other hand, tend to have longer latency (with a 3 hop request-forward-respond) but use much less bandwidth since messages are point to point and not broadcast. For this reason, many of the larger systems (>64 processors) use this type of cache coherence.

Snooping

First introduced in 1983,[9] snooping is a process where the individual caches monitor address lines for accesses to memory locations that they have cached.[5] The write-invalidate protocols and write-update protocols make use of this mechanism.
Para el mecanismo de espionaje, un filtro de espionaje reduce el tráfico de espionaje manteniendo varias entradas, cada una de las cuales representa una línea de caché que puede pertenecer a uno o más nodos. Cuando se requiere reemplazar una de las entradas, el filtro de espionaje selecciona la entrada que representa la línea o líneas de caché que pertenecen al menor número de nodos, según lo determinado por un vector de presencia en cada una de las entradas. Se utiliza un algoritmo temporal u otro tipo de algoritmo para refinar la selección si más de una línea de caché pertenece al menor número de nodos. [ 10 ]

Basado en directorios

En un sistema basado en directorios, los datos compartidos se almacenan en un directorio común que mantiene la coherencia entre las cachés. Este directorio actúa como un filtro a través del cual el procesador debe solicitar permiso para cargar una entrada de la memoria principal a su caché. Cuando se modifica una entrada, el directorio actualiza o invalida las demás cachés que contienen dicha entrada.

Los sistemas de memoria compartida distribuida imitan estos mecanismos en un intento de mantener la coherencia entre bloques de memoria en sistemas débilmente acoplados. [ 11 ]

Protocolos de coherencia

Los protocolos de coherencia aplican coherencia de caché en sistemas multiprocesador. El objetivo es que dos clientes nunca vean valores diferentes para los mismos datos compartidos.

El protocolo debe implementar los requisitos básicos de coherencia. Puede diseñarse a medida para el sistema o la aplicación de destino.

Los protocolos también se pueden clasificar como de tipo "snoopy" o basados ​​en directorios. Por lo general, los primeros sistemas utilizaban protocolos basados ​​en directorios, donde un directorio registraba los datos compartidos y a los usuarios que los compartían. En los protocolos "snoopy", las solicitudes de transacción (de lectura, escritura o actualización) se envían a todos los procesadores. Todos los procesadores analizan la solicitud y responden adecuadamente.

La propagación de escritura en los protocolos snoopy se puede implementar mediante cualquiera de los siguientes métodos:

Invalidar escritura
Cuando se observa una operación de escritura en una ubicación de la que la caché tiene una copia, el controlador de caché invalida su propia copia de la ubicación de memoria monitorizada, lo que fuerza una lectura de la memoria principal del nuevo valor en su siguiente acceso. [ 5 ]
Escribir actualización
Cuando se detecta una operación de escritura en una ubicación de la que la caché tiene una copia, el controlador de caché actualiza su propia copia de la ubicación de memoria monitorizada con los nuevos datos.

Si el diseño del protocolo establece que, cada vez que se modifica una copia de los datos compartidos, todas las demás copias deben actualizarse para reflejar el cambio, entonces se trata de un protocolo de escritura-actualización. Si el diseño establece que una escritura en una copia en caché por parte de cualquier procesador requiere que los demás procesadores descarten o invaliden sus copias en caché, entonces se trata de un protocolo de escritura-invalidación.

Sin embargo, la escalabilidad es una de las limitaciones de los protocolos de difusión.

Se han ideado varios modelos y protocolos para mantener la coherencia, como MSI , MESI (también conocido como Illinois), MOSI , MOESI , MERSI , MESIF , write-once , Synapse, Berkeley, Firefly y el protocolo Dragon . [ 2 ] En 2011, ARM Ltd propuso AMBA 4 ACE [ 12 ] para manejar la coherencia en SoC . La especificación AMBA CHI (Coherent Hub Interface) [ 13 ] de ARM Ltd , que pertenece al grupo de especificaciones AMBA5, define las interfaces para la conexión de procesadores totalmente coherentes.

Véase también

Referencias

  1. ↑ Marowka, Ami (1 de enero de 2010). «Capítulo 2: Escollos y problemas de la programación multinúcleo». Advances in Computers . Vol.  79. Elsevier. pp. 71–117 . doi : 10.1016/s0065-2458(10)79002-1 . ISBN  978-0-12-381027-4.
  2. 1 2 E. Thomadakis, Michael (2011). La arquitectura del procesador Nehalem y las plataformas SMP Nehalem-EP (PDF) . Universidad de Texas A&M. pág. 30. Archivado del original (PDF) el 11 de agosto de 2014. 
  3. 1 2 Yan, Solihin. Fundamentos de la arquitectura multinúcleo paralela . OCLC 884540034 . 
  4. 1 2 Sorin, Daniel J.; Hill, Mark D.; Wood, David Allen (2011-01-01). Una introducción a la consistencia de la memoria y la coherencia de la caché . Morgan & Claypool Publishers. OCLC 726930429 . 
  5. 1 2 3 Patterson y Hennessy. Organización y diseño de computadoras - 4.ª edición . ISBN 978-0-12-374493-7.
  6. ↑ Neupane, Mahesh (16 de abril de 2004). "Coherencia de caché" (PDF). Archivado del original (PDF) el 20 de junio de 2010.
  7. ↑ Steinke, Robert C.; Nutt, Gary J. (1 de septiembre de 2004). "Una teoría unificada de la consistencia de la memoria compartida". J. ACM . 51 (5): 800– 849. arXiv : cs/0208027 . doi : 10.1145/1017460.1017464 . ISSN 0004-5411 . S2CID 3206071 .  
  8. ↑ Patterson, David A.; Hennessy, John L. (1990). Arquitectura de computadoras: Un enfoque cuantitativo . Morgan Kaufmann Publishers. págs. 467–468 . ISBN  1-55860-069-8.
  9. ↑ "Ravishankar, Chinya; Goodman, James (28 de febrero de 1983). "Implementación de caché para múltiples microprocesadores"" (PDF) . Actas de IEEE COMPCON: 346–350 .
  10. ↑ Rasmus Ulfsnes (junio de 2013). "Diseño de un filtro Snoop para protocolos de coherencia de caché basados ​​en Snoop". Archivado el 1 de febrero de 2014 en Wayback Machine (PDF). diva-portal.org . Universidad Noruega de Ciencia y Tecnología. Consultado el 20 de enero de 2014.
  11. ↑ "Lección 18: Espionaje vs. Coherencia basada en directorios" (PDF) . Berkeley.edu . Consultado el 14 de mayo de 2023 .
  12. ↑ Kriouile (16 de septiembre de 2013). Análisis formal de la especificación ACE para sistemas en chip con coherencia de caché. En Métodos formales para sistemas críticos industriales . Springer Berlin Heidelberg. ISBN 978-3-642-41010-9.
  13. ↑ Ltd, Arm. "AMBA | AMBA 5" . Desarrollador de Arm . Consultado el 27 de abril de 2021 .

Lecturas adicionales

  • Patterson, David ; Hennessy, John (2009). Organización y diseño de computadoras (4.ª  ed.). Morgan Kaufmann . ISBN 978-0-12-374493-7.
  • Handy, Jim (1998). El libro de la memoria caché (2.ª  ed.). Morgan Kaufmann . ISBN 9780123229809.
  • Sorin, Daniel; Hill, Mark; Wood, David (2011). Introducción a la consistencia de la memoria y la coherencia de la caché (PDF) . Morgan and Claypool . ISBN 978-1608455645Consultado el 20 de octubre de 2017 .
  • Steinke, Robert C.; Nutt, Gary J. (1 de septiembre de 2004). "Una teoría unificada de la consistencia de la memoria compartida". Journal of the ACM . 51 (5): 800– 849. arXiv : cs/0208027 . doi : 10.1145/1017460.1017464 . S2CID 3206071 .