¿Cómo funcionan las líneas de caché?

Si las líneas de caché son de 64 bytes de ancho, entonces corresponden a bloques de memoria que comienzan en direcciones que son divisibles por 64. Los 6 bits menos significativos de cualquier dirección son un desplazamiento en la línea de caché.

Así que para cualquier byte dado, la línea de caché que tiene que ser recuperada se puede encontrar borrando los seis bits menos significativos de la dirección, lo que corresponde a redondear hacia abajo a la dirección más cercana que es divisible por 64.

Aunque esto se hace por hardware, podemos mostrar los cálculos utilizando algunas definiciones macro de referencia C:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

En primer lugar, un acceso a la memoria principal es muy caro. Actualmente una CPU de 2GHz (la más lenta una vez) tiene 2G ticks (ciclos) por segundo. Una CPU (núcleo virtual hoy en día) puede obtener un valor de sus registros una vez por tick. Dado que un núcleo virtual consta de varias unidades de procesamiento (unidad de lógica aritmética ALU, FPU, etc.), en realidad puede procesar ciertas instrucciones en paralelo si es posible.

Un acceso a la memoria principal cuesta alrededor de 70ns a 100ns (DDR4 es ligeramente más rápido). Esta vez es básicamente buscando la caché L1, L2 y L3 y luego golpear la memoria (enviar comando al controlador de memoria, que lo envía a los bancos de memoria), esperar la respuesta y listo.

100ns significa alrededor de 200 garrapatas. Así que básicamente si un programa siempre perdería las cachés a las que accede cada memoria, la CPU pasaría aproximadamente el 99,5% de su tiempo (si solo lee memoria) inactivo esperando la memoria.

Para acelerar las cosas hay los cachés L1, L2, L3. Usan la memoria siendo directamente colocado en el chip y utilizando un tipo diferente de circuitos de transistor para almacenar los bits dados. Esto toma más espacio, más energía y es más costoso que la memoria principal, ya que una CPU generalmente se produce utilizando una tecnología más avanzada y un fallo de producción en la memoria L1, L2, L3 tiene la oportunidad de hacer que la CPU no tenga valor (defecto), por lo que las cachés L1, L2, L3 grandes aumentan la tasa de error, lo que disminuye el rendimiento, lo que disminuye directamente el ROI. Así que hay una gran compensación cuando se trata de disponible tamaño de caché.

(actualmente se crean más cachés L1, L2, L3 para poder desactivar ciertas porciones para disminuir la posibilidad de que un defecto de producción real sea que las áreas de memoria caché rendericen el defecto de CPU como un todo).

Para dar una idea de tiempo (fuente: costos para acceder a cachés y memoria)

• Caché L1: 1ns a 2ns (2-4 ciclos)
• Caché L2: 3ns a 5ns (6-10 ciclos)
• Caché L3: 12ns a 20ns (24-40 ciclos)
• RAM: 60ns (120 ciclos)

Dado que mezclamos diferentes tipos de CPU, estos son solo estimaciones, pero dan una buena idea de lo que realmente va cuando se obtiene un valor de memoria y es posible que tengamos un éxito o un error en cierta capa de caché.

Así que una caché básicamente acelera el acceso a la memoria en gran medida (60ns vs.1ns).

Obtener un valor, almacenarlo en la caché para la posibilidad de volver a leerlo es bueno para las variables a las que se accede a menudo, pero para las operaciones de copia de memoria todavía sería lento ya que uno solo lee un valor, escribe el valor en algún lugar y nunca lee el valor de nuevo... no hay aciertos de caché, muy lento (además de esto puede suceder en paralelo, ya que tenemos la ejecución fuera de orden).

Esta copia de memoria es tan importante que hay diferentes medios para acelerarla. En los primeros días la memoria a menudo era capaz de copiar la memoria fuera de la CPU. Fue manejado por el controlador de memoria directamente, por lo que una operación de copia de memoria no contaminó las cachés.

Pero al lado de una simple memoria copiar otro acceso serial de la memoria era bastante común. Un ejemplo es analizar una serie de información. Tener una matriz de enteros y calcular la suma, la media, el promedio o incluso más simple encontrar un cierto valor (filtro/búsqueda) eran otra clase muy importante de algoritmos que se ejecutan cada vez en cualquier CPU de propósito general.

Así que al analizar el patrón de acceso a la memoria era evidente que los datos se leen secuencialmente muy a menudo. Había una alta probabilidad de que si un programa lee el valor en el índice i, que el programa también leerá el valor i + 1. Esta probabilidad es ligeramente mayor que la probabilidad de que el mismo programa también lea el valor i+2 y así sucesivamente.

Así que dada una dirección de memoria, era (y sigue siendo) una buena idea leer con anticipación y obtener valores adicionales. Esta es la razón por la que hay un modo boost.

El acceso a la memoria en modo boost significa que una dirección se envía y varios valores se envían secuencialmente. Cada valor adicional enviado solo toma alrededor de adicional 10ns (o incluso por debajo).

Otro problema era una dirección. Enviar una dirección lleva tiempo. Con el fin de abordar una gran parte de la memoria grandes direcciones tiene que ser enviado. En los primeros días significaba que el bus de direcciones no era lo suficientemente grande como para enviar la dirección en un solo ciclo (tick) y se necesitaba más de un ciclo para enviar la dirección añadiendo más retraso.

Una línea de caché de 64 bytes, por ejemplo, significa que la memoria está dividida en bloques distintos (no superpuestos) de memoria de 64 bytes en tamaño. 64bytes significa que la dirección de inicio de cada bloque tiene los seis bits de dirección más bajos para ser siempre ceros. Así que el envío de estos seis bits cero cada vez no es necesario aumentar el espacio de direcciones 64 veces para cualquier número de ancho de bus de direcciones (efecto de bienvenida).

Otro problema que la línea de caché resuelve (además de leer con anticipación y guardar / liberar seis bits en el bus de direcciones) es la forma en que se organiza la caché. Por ejemplo, si una caché se divide en bloques (celdas) de 8 bytes (64 bits), se necesita para almacenar la dirección de la celda de memoria, esta celda de caché contiene el valor para junto con ella. Si la dirección también sería de 64 bits, esto significa que la mitad del tamaño de la caché es consumida por la dirección, lo que resulta en una sobrecarga del 100%.

Dado que una línea de caché es de 64bytes y una CPU puede usar 64bit - 6bit = 58bit (no es necesario almacenar los cero bits demasiado bien) significa que podemos almacenar en caché 64bytes o 512bits con una sobrecarga de 58bit (sobrecarga del 11%). En realidad, las direcciones almacenadas son incluso más pequeñas que esto, pero hay son información de estado (como es la línea de caché válida y precisa, sucia y necesita escribirse en ram, etc.).

Otro aspecto es que tenemos caché set-asociativa. No todas las celdas de caché pueden almacenar una dirección determinada, sino solo un subconjunto de ellas. Esto hace que los bits de dirección almacenados necesarios sean aún más pequeños, permite el acceso paralelo de la caché (cada subconjunto se puede acceder una vez, pero independiente de los otros subconjuntos).

Hay más especialmente cuando se trata de sincronizar acceso a caché / memoria entre los diferentes núcleos virtuales, sus unidades de procesamiento múltiples independientes por núcleo y, finalmente, múltiples procesadores en una placa base (que hay placas que albergan hasta 48 procesadores y más).

Esta es básicamente la idea actual por la que tenemos líneas de caché. El beneficio de leer por adelantado es muy alto y el peor caso de leer un solo byte de una línea de caché y nunca leer el resto de nuevo es muy delgado ya que la probabilidad es muy delgado.

El tamaño de la línea de caché (64) es una sabia elección entre líneas de caché más grandes, lo que hace poco probable que el último byte de la misma se lea también en un futuro cercano, la duración que se necesita para obtener la línea de caché completa de la memoria (y escribirla de nuevo) y también la sobrecarga en la organización de la caché y la paralelización de la caché y el acceso a la memoria.

Los procesadores pueden tener cachés multinivel (L1, L2, L3), y estos difieren en tamaño y velocidad.

Sin embargo, para entender qué va exactamente en cada caché, tendrá que estudiar el predictor de rama utilizado por ese procesador específico, y cómo se comportan las instrucciones/datos de su programa en contra de él.

Lea acerca de predictor de ramas, Políticas de reemplazo de caché de CPU y .

Esta no es una tarea fácil. Si al final del día todo lo que quieres es una actuación prueba, puedes usar una herramienta como Cachegrind. Sin embargo, como se trata de una simulación, su resultado puede diferir en algún grado.

No puedo decirlo con certeza, ya que cada hardware es diferente, pero normalmente es "64 bytes comienzan en el límite de 64 bytes más cercano debajo", ya que es una operación muy rápida y simple para la CPU.