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

169

Entiendo que el procesador trae datos al caché a través de líneas de caché, que, por ejemplo, en mi procesador Atom, trae aproximadamente 64 bytes a la vez, sea cual 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 llevarán al caché?

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

Cual es

Norswap
fuente
22
Lea esto: Lo que todo programador debe saber sobre la memoria . Luego léelo de nuevo. Mejor fuente (pdf) aquí .
andersoj

Respuestas:

129

Si la línea de caché que contiene el byte o la palabra que está cargando aún no está presente en el 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 desencadena una lectura o escritura de una línea de caché completa desde la memoria. (El tamaño de transferencia de ráfaga SDRAM DDR1 / 2/3/4 es configurable hasta 64B; las CPU seleccionarán el tamaño de transferencia de ráfaga para que coincida con su tamaño de línea de caché, pero 64B es común)

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

Por el contrario, un éxito en el 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 4 o 5 ciclos en las CPU modernas x86. Las cosas son similares en otras arquitecturas.

Más información: Ulrich Drepper es lo que todo programador debe saber sobre la memoria . El consejo de captación previa de software está un poco desactualizado: los captadores de captura de hardware modernos son más inteligentes y el hyperthreading es mucho mejor que en los días P4 (por lo que un subproceso de captación previa suele ser un desperdicio). También el tag wiki tiene muchos enlaces de rendimiento para esa arquitectura.

Eugene Smith
fuente
1
Esta respuesta no tiene absolutamente ningún sentido. ¿Qué tiene que ver el ancho de banda de la memoria de 64 bits (que también está mal en ese sentido) con el byte de 64 bits (!) Además, las 10 a 30 ns también están totalmente equivocadas si golpeas el Ram. Puede ser cierto para el caché L3 o L2, pero no para la RAM, donde se parece más a 90ns. Lo que quiere decir es el momento de la explosión - el tiempo para acceder a la siguiente cuádruple palabra en el modo de ráfaga (que en realidad es la respuesta correcta)
Martin Kersten
55
@MartinKersten: un canal de DDR1 / 2/3/4 SDRAM usa un ancho de bus de datos de 64 bits. Una transferencia de ráfaga de una línea de caché completa toma ocho transferencias de 8B cada una, y es lo que realmente sucede. Todavía podría ser correcto que el proceso se optimice transfiriendo primero el fragmento alineado con 8B que contiene el byte deseado, es decir, comenzando la ráfaga allí (y terminando si no fuera el primer 8B del tamaño de transferencia de ráfaga). Sin embargo, las CPU modernas con cachés de varios niveles probablemente ya no lo hagan, porque significaría retransmitir los primeros bloques de la ráfaga a caché L1 antes.
Peter Cordes
2
Haswell tiene una ruta de 64B entre el caché L2 y L1D (es decir, un ancho de línea de caché completo), por lo que transferir el 8B que contiene el byte solicitado haría que el bus sea ineficiente. @ Martin también tiene razón sobre el tiempo de acceso para una carga que debe ir a la memoria principal.
Peter Cordes
3
Buena pregunta acerca de si los datos ascienden por la jerarquía de la memoria a la vez, o si L3 espera una línea completa de la memoria antes de comenzar a enviarla a L2. Hay buffers de transferencia entre diferentes niveles de caché, y cada fallo pendiente reclama uno. Entonces ( conjetura total ) probablemente L3 coloca los bytes del controlador de memoria en su propio búfer de recepción al mismo tiempo que los coloca en el búfer de carga apropiado para el caché L2 que lo quería. Cuando la línea se transfiere completamente desde la memoria, L3 notifica a L2 que la línea está lista y la copia en su propia matriz.
Peter Cordes
2
@ Martin: Decidí seguir adelante y editar esta respuesta. Creo que ahora es más preciso y aún simple. Futuros lectores: vea también la pregunta de Mike76 y mi respuesta: stackoverflow.com/questions/39182060/…
Peter Cordes
22

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

Entonces, para cualquier byte dado, la línea de caché que debe buscarse se puede encontrar borrando los seis bits menos significativos de la dirección, lo 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 de macro 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)
Kaz
fuente
1
Me cuesta entender esto. Sé que es 2 años después, pero ¿puedes darme un código de ejemplo para esto? Una o dos líneas.
Nick
1
@Nick La razón por la que este método funciona radica en el sistema de números binarios. Cualquier potencia de 2 tiene un solo conjunto de bits y todos los bits restantes se borran, por lo que para 64, 0b1000000notará que los últimos 6 dígitos son ceros, por lo que incluso cuando tiene algún número con cualquiera de esos 6 conjuntos (que representan el número % 64), al borrarlos, obtendrá la dirección de memoria alineada de 64 bytes más cercana.
legends2k
21

En primer lugar, un acceso a la memoria principal es muy costoso. Actualmente, una CPU de 2 GHz (la más lenta una vez) tiene tics 2G (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 múltiples unidades de procesamiento (ALU - unidad lógica aritmética, FPU, etc.), puede procesar ciertas instrucciones en paralelo si es posible.

Un acceso a la memoria principal cuesta alrededor de 70ns a 100ns (DDR4 es un poco más rápido). Esta vez es básicamente buscar el 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 aproximadamente 200 garrapatas. Básicamente, si un programa siempre perdiera los cachés a los que accede cada memoria, la CPU pasaría aproximadamente el 99,5% de su tiempo (si solo lee la memoria) inactivo esperando la memoria.

Para acelerar las cosas hay cachés L1, L2, L3. Utilizan la memoria que se coloca directamente en el chip y utilizan 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 un fallo de producción en la memoria L1, L2, L3 tiene la posibilidad de hacer que la CPU no tenga valor (defecto) Los cachés grandes L1, L2, L3 aumentan la tasa de error, lo que disminuye el rendimiento, lo que disminuye directamente el ROI. Por lo tanto, hay una gran compensación en lo que respecta al 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 las áreas de memoria caché representa el defecto de la CPU en su conjunto).

Para dar una idea de tiempo (fuente: costos de acceso 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, estas son solo estimaciones, pero dan una buena idea de lo que realmente sucede cuando se recupera un valor de memoria y podríamos tener un acierto o una falla en cierta capa de caché.

Entonces, un caché básicamente acelera el acceso a la memoria en gran medida (60ns frente a 1ns).

Obtener un valor, almacenarlo en la memoria caché para tener la posibilidad de volver a leerlo es bueno para las variables a las que se accede con frecuencia, pero para las operaciones de copia de memoria aún 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 una ejecución fuera de orden).

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 controlado por el controlador de memoria directamente, por lo que una operación de copia de memoria no contaminó los cachés.

Pero aparte de una copia de memoria simple, otro acceso serie de 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 para encontrar un cierto valor (filtro / búsqueda) fue otra clase muy importante de algoritmos que se ejecuta 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 secuencialmente con mucha frecuencia. Había una alta probabilidad de que si un programa lee el valor en el índice i, 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.

Entonces, 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 cual hay un modo de impulso.

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

Otro problema era una dirección. Enviar una dirección lleva tiempo. Para direccionar 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 agregando más demora.

Una línea de caché de 64 bytes, por ejemplo, significa que la memoria está dividida en bloques de memoria distintos (no superpuestos) que tienen un tamaño de 64 bytes. 64 bytes significa que la dirección de inicio de cada bloque tiene los seis bits de dirección más bajos para ser siempre 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 direcciones (efecto de bienvenida).

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

Dado que una línea de caché es de 64 bytes y una CPU puede usar 64 bits - 6 bits = 58 bits (no es necesario almacenar los bits cero demasiado bien) significa que podemos almacenar en caché 64 bytes o 512 bits con una sobrecarga de 58 bits (sobrecarga del 11%). 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 ser reescrita en RAM, etc.).

Otro aspecto es que tenemos caché asociativo de conjunto. No todas las celdas de caché pueden almacenar una determinada dirección, 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 independientemente de los otros subconjuntos).

Hay más especialmente cuando se trata de sincronizar el acceso a la memoria 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 con anticipación es muy alto y el peor de los casos de leer un solo byte de una línea de caché y nunca leer el resto nuevamente es muy escaso, ya que la probabilidad es muy escasa.

El tamaño de la línea de caché (64) es una sabia compensación entre líneas de caché más grandes, lo que hace improbable que el último byte se lea también en un futuro próximo, la duración que toma obtener la línea de caché completa desde la memoria (y para volver a escribirlo) y también la sobrecarga en la organización de la memoria caché y la paralelización de la memoria caché y el acceso a la memoria.

Martin Kersten
fuente
1
Una caché asociativa de conjuntos utiliza algunos bits de dirección para seleccionar un conjunto, por lo que las etiquetas pueden ser incluso más cortas que su ejemplo. Por supuesto, la memoria caché también necesita realizar un seguimiento de qué etiqueta va con qué matriz de datos en el conjunto, pero generalmente hay más conjuntos que formas dentro de un conjunto. (p. ej., caché L1D asociativa de 8kB de 32kB, con líneas de 64B, en CPU Intel x86: desplazamiento de 6 bits, índice de 6 bits. Las etiquetas solo deben tener 48-12 bits de ancho, porque x86-64 (por ahora) solo tiene 48- direcciones físicas de bits. Como estoy seguro de que sabe, no es una coincidencia que los 12 bits bajos sean el desplazamiento de página, por lo que L1 puede ser VIPT sin alias.)
Peter Cordes
increíble respuesta amigo ... ¿hay un botón "me gusta" en alguna parte?
Edgard Lima
@EdgardLima, ¿no es el botón de votación?
Pacerier
6

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

Sin embargo, para comprender qué contiene exactamente 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.

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

Esta no es una tarea fácil. Si al final del día lo único que desea 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.

jweyrich
fuente
4

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

bramp
fuente
2
Yo puedo decir con certeza. Cualquier diseño de caché razonable tendrá líneas con tamaños que son una potencia de 2, y que están naturalmente alineadas. (por ejemplo, alineado con 64B). No solo es rápido y simple, es literalmente gratuito: simplemente ignoras los 6 bits bajos de la dirección, por ejemplo. Los cachés a menudo hacen cosas diferentes con diferentes rangos de direcciones. (p. ej., el caché se preocupa por la etiqueta y el índice para detectar aciertos frente a fallas, luego solo usa el desplazamiento dentro de una línea de caché para insertar / extraer datos)
Peter Cordes