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

ram (5)

Entiendo que el procesador trae datos al caché a través de líneas de caché, lo que, por ejemplo, en mi procesador Atom, aporta aproximadamente 64 bytes a la vez, cualquiera que sea el tamaño de los datos reales que se leen.

Mi pregunta es:

Imagine que necesita leer un byte de la memoria, ¿qué 64 bytes se introducirán en la memoria caché?

Las dos posibilidades que puedo ver es que los 64 bytes comienzan en el límite de 64 bytes más cercano por debajo del byte de interés, o los 64 bytes se reparten alrededor del byte de alguna manera predeterminada (por ejemplo, mitad debajo, mitad arriba o todo lo de arriba).

¿Cuál es?

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

El acceso a la memoria principal cuesta entre 70 y 100ns (DDR4 es ligeramente más rápido). Esta vez básicamente busca la caché L1, L2 y L3 y luego toca la memoria (envía el comando al controlador de memoria, que lo envía a los bancos de memoria), espera la respuesta y finaliza.

100ns significa aproximadamente 200 tics. Entonces, básicamente, si un programa siempre pierde los cachés a los que accede cada memoria, la CPU gastaría aproximadamente el 99,5% de su tiempo (si solo lee memoria) en espera para la memoria.

Para acelerar las cosas, hay cachés L1, L2, L3. Usan la memoria que se coloca directamente en el chip y el uso de un tipo diferente de circuitos de transistores para almacenar los bits dados. Esto requiere 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 una falla de producción en la memoria L1, L2, L3 tiene la posibilidad de inutilizar la CPU (defecto) grandes cachés L1, L2, L3 aumentan la tasa de error que disminuye el rendimiento que directamente disminuye el ROI. Entonces, hay una gran compensación cuando se trata del tamaño de caché disponible.

(actualmente, uno crea 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 la memoria caché dejen a la CPU defectuosa como un todo).

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

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

Debido a que mezclamos diferentes tipos de CPU, estas son solo estimaciones, pero dan una buena idea de lo que realmente sucede cuando se obtiene un valor de memoria y es posible que tengamos un error o fallo en cierta capa de caché.

Por lo tanto, una memoria caché básicamente acelera enormemente el acceso a la memoria (60ns frente a 1ns).

Obtener un valor, almacenarlo en la memoria 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 sería aún más lento ya que uno solo lee un valor, escribe el valor en alguna parte y nunca lee el valor de nuevo ... sin caché, lento (a parte de esto puede suceder en paralelo porque tenemos una ejecución fuera de servicio).

Esta copia de memoria es tan importante que existen diferentes medios para acelerarla. En los primeros días, la memoria a menudo podía copiar 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 memorias caché.

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

Entonces, al analizar el patrón de acceso a la memoria, fue evidente que los datos se leen de forma secuencial con mucha frecuencia. Hubo una alta probabilidad de que si un programa lee el valor en el índice i, el programa también lea 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 adelante y buscar valores adicionales. Esta es la razón por la cual hay un modo boost.

El acceso a la memoria en modo boost significa que se envía una dirección y se envían múltiples valores secuencialmente. Cada envío de valor adicional solo requiere 10ns adicionales (o incluso menos).

Otro problema fue una dirección. Enviar una dirección lleva tiempo. Para abordar una gran parte de la memoria, se deben enviar direcciones grandes. 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 (marca) y se necesitaba más de un ciclo para enviar la dirección y agregar más retraso.

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

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

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

Otro aspecto es que tenemos caché set-associative. 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 memoria caché (se puede acceder a cada subconjunto una vez, pero de forma independiente de los otros subconjuntos).

Hay más especialmente cuando se trata de sincronizar el acceso de caché / memoria entre los diferentes núcleos virtuales, sus múltiples unidades de procesamiento 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 de por qué 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 volver a leer el resto es muy pequeño ya que la probabilidad es muy pequeña.

El tamaño de la línea de caché (64) es un compromiso sabio entre las líneas de caché más grandes hace que sea poco probable que el último byte sea leído también en el futuro cercano, la duración que lleva obtener la línea de caché completa desde la memoria (y volver a escribirla) y también la sobrecarga en la organización del caché y la paralelización de la memoria caché y el acceso a la memoria.

Los procesadores pueden tener cachés de niveles múltiples (L1, L2, L3), y estos difieren en tamaño y velocidad.

Sin embargo, para comprender qué es exactamente lo que entra en cada caché, tendrá que estudiar el predictor de bifurcación utilizado por ese procesador específico y cómo se comportan las instrucciones / datos de su programa en su contra.

Lea sobre predictores de sucursales , caché de CPU y políticas de reemplazo .

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

No puedo decir con certeza, ya que cada hardware es diferente, pero por lo general es "64 bytes comienzan en el límite de 64 bytes más abajo", ya que es una operación muy rápida y sencilla para la CPU.

Si la línea de caché que contiene el byte o la palabra que está cargando no está presente en la caché, su CPU solicitará los 64 bytes que comienzan en el límite de la línea de caché (la dirección más grande debajo de la que necesita es múltiplo de 64) .

Los módulos de memoria de PC modernos transfieren 64 bits (8 bytes) a la vez, en una ráfaga de ocho transferencias , por lo que un comando activa una lectura o escritura de una línea de memoria caché completa. (DDR1 / 2/3/4 El tamaño de transferencia de ráfaga SDRAM es configurable hasta 64B; las CPU seleccionarán el tamaño de transferencia de ráfaga para que coincida con el tamaño de línea de caché, pero 64B es común)

Como regla general, si el procesador no puede pronosticar el acceso a la memoria (y recuperarla previamente), el proceso de recuperación puede tomar ~ 90 nanosegundos, o ~ 250 ciclos de reloj (desde que la CPU conoce la dirección a la CPU que recibe los datos).

Por el contrario, un hit en la memoria caché L1 tiene una latencia de uso de carga de 3 o 4 ciclos, y una recarga de tienda tiene una latencia de reenvío de almacenamiento de 4 o 5 ciclos en las CPU modernas x86. Las cosas son similares en otras arquitecturas.

Lectura adicional: Lo que todo programador debería saber sobre la memoria de Ulrich Drepper. El consejo de captación previa de software está un poco desactualizado: los precaptores HW modernos son más inteligentes, y el hyperthreading es mucho mejor que en los días P4 (por lo que un hilo de captación previa suele ser un desperdicio). Además, la wiki de la etiqueta x86 tiene muchos enlaces de rendimiento para esa arquitectura.

Si las líneas de caché tienen 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é.

Por lo tanto, para cualquier byte dado, la línea de caché que debe buscarse se puede encontrar al borrar los seis bits menos significativos de la dirección, que corresponde al redondeo a la dirección más cercana que es divisible por 64.

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

#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)