¿Por qué pueden cachés L3 sólo se mantienen los períodos compartida?

Question

En un artículo reciente CACM [1], los autores presentan una forma de mejorar la escalabilidad de las cachés compartidos y coherentes. El ingrediente núcleo está asumiendo las memorias caché son inclusive , es decir memorias caché de nivel superior (por ejemplo L3, una caché global) contienen todos los bloques que se almacenan en su descendiente cachés de nivel inferior (por ejemplo, L1, una memoria caché por núcleo).

Típicamente, las memorias caché de nivel superior son más grandes que sus respectivas memorias caché de descendientes juntos. Por ejemplo, algunos modelos de la serie Intel Core i7 con cuatro núcleos tienen un 8 MB de caché compartida (L3) y 256KB cachés privadas (L2), que es la memoria caché compartida puede contener ocho veces tantos bloques como los cachés privadas en total.

Esto parece sugerir que cada vez que la memoria caché compartida tiene que desalojar a un bloque (con el fin de cargar un nuevo bloque) se puede encontrar un bloque que se comparte con ninguna de las caches² privada (principio casillero). Sin embargo, los autores escriben:

[Nosotros] podemos eliminar potencialmente a todos los retiros, pero sólo si la asociatividad, o el número de lugares en los que un bloque específico se pueden almacenar en caché, la memoria caché compartida excede la asociatividad total de los almacenes privados. Con la suficiente asociatividad, [la memoria caché compartida] está garantizado para encontrar un bloque no compartido [...]. Sin esta peor de los casos asociatividad, un grupo patológico de fallos podría conducir a una situación en la que todos los bloques en un conjunto de la caché compartida se comparten de verdad.

¿Cómo es esto posible, es decir, ¿cómo puede, por ejemplo, 1 MB 8 MB portada? Es evidente que echo de menos algún detalle de cómo este tipo de trabajo jerarquías de caché. ¿Qué significa "asociatividad" aquí? "Número de lugares en los que un bloque específico puede tener una caché" no está claro; Sólo puedo llegar a la interpretación de que un bloque se puede almacenar varias veces en cada caché, pero que no tendría ningún sentido en absoluto. ¿Cómo sería un "cúmulo de fallos patológica" tal parece?

---

1. Por qué en chip de coherencia de caché está aquí para quedarse por MMK Martin, MD Hill, DJ Sorin (2012)
2. Suponiendo que las cachés compartidos sabe que bloquea cuando se comparten. Esto se puede lograr por notificaciones de desalojo explícitas y seguimiento de bits, que también se discute en [1].

Answer 1

Tal vez puede arrojar alguna luz sobre la asociatividad. Estos cachés no son simplemente bloques abiertos de la memoria, por lo que no pensar en ellos como una especie de contenedor genérico. Cada bloque de memoria tiene una dirección real (si esto es física o virtual, no importa, simplemente asumen que es una dirección fija). En cada nivel de caché de esta memoria sólo se puede almacenar en caché en lugares muy específicos en la memoria caché.

Por ejemplo, la memoria dirección X se puede almacenar en la caché L1 en la ubicación Y0. Este es un mapeo directo. Pero supongamos que también se puede almacenar en la ubicación Y1, entonces es asociativa de 2 vías (que es bastante común). Al ser almacenable en N-locations hace que sea N-manera asociativa. Cuando el chip elige una ubicación de caché comprueba solamente estos lugares N -. No explora toda la memoria caché (que sería complicado demasiado lento /)

Esto debería aclarar lo que significan diciendo la memoria caché compartida debe tener una mayor asociatividad agregado que los cachés más bajos. Así que si L1 es de 2 vías, L2 es de 4 vías, y hay 4 procesadores, compartieron caché debe ser> asociativa de 24 vías (no tengo el artículo, pero esto suena como lo que significan). Esto se deduce entonces, que al menos uno de estos lugares compartidos no debe ser en caché en cualquiera de los almacenes privados.

No se puede decir con certeza lo que su caso "patológico" es, pero me puede explicar muy común, que puede afectar a cosas como la búsqueda binaria. Digamos que el caché L1 es asociativa de 1 vía y 4 KB de tamaño. Los lugares donde la memoria se puede almacenar es probablemente un mod sencillo de la dirección (X mod 4K). Por ejemplo, entonces tiene un gran bloque de datos que es una potencia de 2 (que es común). En una búsqueda binaria que siempre picar el tamaño a la mitad, por lo que una búsqueda sobre un bloque de 256 K tendría que comprobar la dirección 128K, 64K, 32K, 16K, 8K, 4K, y la más baja. Pero debería ver un problema aquí. Esos primeros 6 direcciones de todos los mapas a la misma ubicación exacta caché. Por lo que cada acceso requiere un desalojo y la carga, a pesar de que el acceso a sólo una pequeña cantidad de memoria.