Jerarquía de memoria y cachés

Una caché funciona porque el siguiente acceso a memoria suele estar relacionado con uno reciente. Durante un intervalo breve, la mayoría de los programas usan solo una pequeña parte de su espacio de direcciones. Este patrón es la localidad. Una caché mantiene esa parte activa cerca del procesador, donde puede atender los accesos rápidamente.

Reutilización en el tiempo y el espacio

La localidad temporal significa reutilizar un elemento poco después de acceder a él. Un bucle busca repetidamente las instrucciones de su cuerpo. Un total acumulado se lee y actualiza muchas veces. Mantener esos elementos disponibles evita buscarlos de nuevo en un nivel más lento.

La localidad espacial significa acceder a elementos en direcciones cercanas. Un recorrido de un arreglo lee elementos adyacentes y el código de ejecución secuencial busca instrucciones sucesivas. Una caché aprovecha esto buscando un bloque completo, también llamado línea de caché, cuando se produce un fallo. Los bytes cercanos llegan antes de que el programa los solicite.

Estos patrones pueden darse juntos. Las instrucciones de un bucle son adyacentes y se ejecutan repetidamente, por lo que el flujo de instrucciones tiene localidad tanto espacial como temporal. Un elemento de un arreglo que se lee exactamente una vez no tiene reutilización temporal, aunque el recorrido del arreglo que lo rodea tenga localidad espacial.

Cuenta los bloques en un recorrido de un arreglo

Considera este bucle de C con enteros de 4 bytes y bloques de caché de 64 bytes:

for (int i = 0; i < 1000; i++) {
    sum += a[i];
}

Un bloque contiene $64\mathrm{/}4=16$ enteros. El arreglo ocupa $1000\times 4=4000$ bytes. Si su primer elemento está alineado con un bloque, el recorrido toca $\lceil 4000\mathrm{/}64\rceil =63$ bloques: 62 bloques completos y uno parcial.

En una caché inicialmente vacía, sin precarga ni interferencias, el primer acceso a cada bloque falla. Los elementos restantes de ese bloque aciertan. Así, el arreglo causa 63 fallos en 1000 accesos, aproximadamente el 6,3 %. Contar un fallo por elemento pasaría por alto todos los datos vecinos útiles que se traen con cada fallo.

Las variables del código fuente sum e i se reutilizan con frecuencia. Sin embargo, un compilador suele mantenerlas en registros, por lo que su reutilización en el código fuente no tiene por qué producir accesos a la caché de datos. Analiza los accesos a memoria que ejecuta el programa compilado al estimar el tráfico de caché.

El conjunto de trabajo debe caber y coexistir

El conjunto de trabajo es la colección de bloques usados durante un intervalo de tiempo elegido. Si caben en la caché y las reglas de ubicación permiten que coexistan, los accesos repetidos aciertan en su mayoría después de las cargas iniciales. El intervalo de tiempo importa: un programa completo puede ser enorme mientras que un bucle activo usa solo unos pocos bloques.

La capacidad por sí sola no basta. Dos bloques muy usados pueden asignarse a una misma entrada de correspondencia directa y expulsarse entre sí mientras otras entradas permanecen vacías. Por tanto, un conjunto de trabajo puede caber por número de bytes y, aun así, no permanecer en caché.

Los nodos dispersos de una lista enlazada y las consultas aleatorias de una tabla hash grande suelen tener poca localidad espacial. Un recorrido por columnas de un arreglo almacenado por filas también salta muchos elementos cercanos. Estos patrones traen bytes que pueden quedar sin usar antes de la expulsión. El hardware aprovecha la localidad que aporta el patrón de acceso; cambiar la organización o el recorrido del programa puede hacer que se aproveche una mayor parte de cada bloque buscado.

Las tecnologías de memoria implican compromisos entre velocidad, densidad, coste y persistencia. El procesador necesita acceso rápido a una pequeña cantidad de datos y espacio asequible para muchos más. La SRAM, la DRAM y la memoria flash satisfacen distintas partes de esa necesidad.

Compara las celdas

Una celda de SRAM es rápida, pero ocupa una superficie considerable, lo que hace que la SRAM sea relativamente cara por bit. Las celdas de DRAM son más pequeñas, por lo que la DRAM ofrece más capacidad a un menor coste por bit. Su carga se pierde. El refresco lee y restaura las filas dentro de un intervalo fijo; DDR4 a temperatura normal usa un intervalo de 64 ms. «Estática» en SRAM significa que no necesita refresco, no que conserve los datos tras perder la alimentación.

Por qué varía el tiempo de acceso a la DRAM

La DRAM se organiza en bancos, con filas y columnas en cada banco. Activar una fila la copia a un búfer de fila. Las lecturas y escrituras seleccionan después columnas de esa fila abierta. Para abrir una fila diferente en el mismo banco, primero debe precargarse el banco. Un acceso a una fila ya abierta evita ese trabajo de cambio de fila.

Las columnas consecutivas pueden transferirse en una ráfaga, lo que favorece la búsqueda de un bloque de caché. Distribuir las solicitudes entre bancos y canales permite solapar las transferencias. La memoria DDR transfiere datos en ambos flancos del reloj. Estas características aumentan la tasa de entrega de datos sin eliminar la espera por los primeros datos.

Distingue la latencia del ancho de banda

La latencia es la demora hasta que llegan los primeros datos. El ancho de banda es la cantidad transferida por unidad de tiempo. Una interfaz de gran ancho de banda puede seguir teniendo una larga demora inicial.

Por ejemplo, un canal DDR5-4800 con un camino de datos agregado de 64 bits transporta 8 bytes por transferencia. Su tasa máxima teórica es $4800\times {10}^6\times 8=\mathrm{38,4}\times {10}^9$ bytes/s, o 38,4 GB/s. El ancho de banda sostenido de una aplicación puede ser menor porque los comandos, los cambios de fila y otras tareas consumen tiempo.

Si una solicitud espera 60 ns y después recibe un bloque de 64 bytes a 16 GB/s, la tasa de transferencia es de 16 bytes/ns. La transferencia tarda $64\mathrm{/}16=4$ ns, lo que da unos 64 ns en total. Mejorar solo el ancho de banda reduce la parte de 4 ns, no los 60 ns iniciales.

La memoria flash conserva los datos, pero gestiona las escrituras de otra manera

La memoria flash NAND lee y programa páginas de varios KiB. Para reutilizar una página programada es necesario borrar su bloque de borrado más grande, que contiene muchas páginas. Las lecturas de páginas suelen tardar decenas de microsegundos, la programación desde cientos de microsegundos hasta unos pocos milisegundos y el borrado milisegundos.

Los ciclos de programación y borrado desgastan las celdas. La memoria flash densa de varios bits suele soportar unos pocos miles de ciclos, mientras que las celdas de un solo bit pueden soportar alrededor de 100 000. Los controladores usan la nivelación del desgaste para repartir las escrituras entre los bloques.

Como referencia, el acceso a la SRAM tarda aproximadamente 1 ns; a la DRAM, aproximadamente 50–100 ns; las lecturas de memoria flash NAND, aproximadamente 25–100 µs; y el acceso a disco, aproximadamente 5–10 ms. Los dispositivos reales varían. La jerarquía combina estas tecnologías porque una sola no puede ofrecer a la vez sus ventajas de velocidad, capacidad y precio.

La jerarquía de memoria sitúa el almacenamiento pequeño y rápido cerca del procesador y el almacenamiento progresivamente más grande, más lejos. La localidad permite que los niveles pequeños atiendan una gran fracción de las solicitudes, mientras que los niveles inferiores proporcionan capacidad.

Niveles y unidades de transferencia

Un recorrido típico pasa por los registros, L1, L2, L3, la memoria principal y el almacenamiento. L1 suele tener cachés separadas de instrucciones y datos de alrededor de 32–64 KiB cada una por núcleo. L2 suele tener de cientos de KiB a unos pocos MiB por núcleo, mientras que L3 suele ser compartida y contener de varios a decenas de MiB. La memoria principal contiene muchos GiB y el almacenamiento contiene cientos de GB o más. Los diseños difieren en tamaño y en cómo se comparten.

En un procesador cercano a 3 GHz, las latencias de carga representativas son de unos 4–5 ciclos para L1, 12–15 para L2, 30–50 para L3 y 200–300 para la DRAM. Una L1 puede aceptar una nueva solicitud en cada ciclo aunque una solicitud necesite varios ciclos para completarse: la productividad y la latencia describen propiedades diferentes.

Los datos viajan por las cachés en bloques, normalmente de 64 bytes. La memoria virtual usa páginas, normalmente de 4 KiB, al mover el contenido de las páginas entre la memoria y el almacenamiento. Una línea de caché y una página cumplen funciones de agrupación similares a diferentes escalas; no son la misma unidad de transferencia.

Aciertos, fallos y tiempos

Un acierto significa que un nivel contiene los datos solicitados. Un fallo significa que debe obtener los datos de un nivel inferior. Ambas palabras se refieren al nivel que se comprueba: un fallo de L1 todavía puede ser un acierto de L2.

La tasa de aciertos es el número de aciertos dividido entre el número de accesos, y la tasa de fallos es uno menos la tasa de aciertos. El tiempo de acierto incluye la comprobación del nivel y la decisión de si la solicitud acierta. La penalización por fallo es el tiempo adicional necesario en un fallo para obtener y entregar el bloque.

Supón que una caché simplificada tiene un tiempo de acierto de 1 ciclo, una tasa de aciertos del 97 % y una penalización adicional por fallo de 100 ciclos. Cada acceso paga 1 ciclo, mientras que el 3 % paga otros 100:

Un fallo tarda 101 ciclos en este ejemplo. Usar 100 como tiempo completo del fallo contabilizaría de forma incoherente la búsqueda inicial. Incluso una tasa de aciertos alta deja que los fallos costosos se reflejen en el promedio.

¿Quién gestiona cada nivel?

El compilador asigna valores adecuados a los registros. El hardware de caché mueve bloques automáticamente durante las cargas, los almacenamientos y las búsquedas de instrucciones. Los programas usan direcciones; no seleccionan entradas de caché. El sistema operativo gestiona las correspondencias de memoria virtual con apoyo del hardware y se ocupa de las páginas que deben llevarse a la memoria principal.

Separar las instrucciones de los datos en L1 permite que un cauce de segmentación busque una instrucción y acceda a datos a la vez sin competir por un mismo puerto de caché. Las cachés inferiores suelen estar unificadas y almacenan bloques tanto de instrucciones como de datos.

Algunas jerarquías son inclusivas: un bloque presente en un nivel superior también tiene una copia en el inferior. Otras son exclusivas o no inclusivas, por lo que no se garantiza una copia en cada caché inferior. Dibuja una jerarquía como un recorrido de búsqueda y transferencia, no como una garantía de que todos los niveles contienen subconjuntos idénticos.

Hacer L1 más grande puede reducir los fallos, pero aumentar el retardo de acceso y la energía. Añadir cachés inferiores más grandes permite mantener rápida L1 y atender muchos de sus fallos antes de llegar a la DRAM. Evalúa ese compromiso mediante el tiempo de acceso, no solo mediante la capacidad.

Una dirección de byte identifica un byte de la memoria. Una caché busca un bloque completo, por lo que la búsqueda primero identifica ese bloque y después selecciona los bytes solicitados dentro de él. En una caché de correspondencia directa, cada bloque tiene exactamente una entrada posible.

Divide la dirección según la función

Para un tamaño de bloque de $2^b$ bytes, los $b$ bits menos significativos de la dirección forman el desplazamiento. Dividir la dirección de byte entre el tamaño de bloque y descartar el resto da la dirección de bloque. El resto es el desplazamiento.

Si la caché tiene $E$ entradas, el índice de entrada es

Cuando el número de entradas es una potencia de dos, el índice es el grupo de bits de la dirección situado inmediatamente por encima del desplazamiento. Los bits más significativos restantes forman la etiqueta, que indica a la caché cuál de los muchos bloques que comparten un índice está presente.

El orden de los campos, de los bits más significativos a los menos significativos, es etiqueta | índice | desplazamiento. Para una anchura de dirección de $A$ bits:

Usa el número de entradas para calcular el índice. Tomar el logaritmo de la capacidad en bytes contaría los bits de desplazamiento por segunda vez.

Resuelve un ejemplo de 16 KiB

Una caché de correspondencia directa de 16 KiB con bloques de 64 bytes tiene $16384\mathrm{/}64=256$ entradas. El desplazamiento ocupa 6 bits, el índice 8 bits y la etiqueta $32-8-6=18$ bits para direcciones de 32 bits.

Para la dirección de byte 0x1234ABCD, los 6 bits menos significativos dan el desplazamiento 13, o 0x0D. Al quitar esos bits se obtiene la dirección de bloque 0x48D2AF. Sus 8 bits menos significativos son 0xAF, por lo que el índice es 175. Los bits restantes dan la etiqueta 0x48D2.

La dirección de byte puede reconstruirse a partir de estos campos: concatena la etiqueta, el índice de 8 bits y el desplazamiento de 6 bits. Las anchuras de los campos importan porque un dígito hexadecimal representa 4 bits; los límites no tienen por qué quedar entre dígitos hexadecimales.

Una etiqueta coincidente necesita una entrada válida

Cada entrada almacena datos, una etiqueta y un bit de validez. El índice selecciona la entrada. Un acierto requiere tanto un bit de validez activado como la igualdad entre la etiqueta almacenada y la etiqueta solicitada. Al inicio, una entrada puede contener bits arbitrarios; el bit de validez impide que esos bits se confundan con un bloque cargado.

Una vez que el bloque está presente, los accesos a otros bytes de ese bloque también aciertan. Un acierto no requiere la misma dirección de byte que se usó para buscar el bloque.

Cuenta los metadatos por separado

La capacidad indicada de la caché normalmente cuenta solo los datos. Aquí cada entrada contiene 512 bits de datos, 18 bits de etiqueta y 1 bit de validez, es decir, 531 bits. El almacenamiento total es

Solo los datos usan 131 072 bits. Las etiquetas y la validez añaden 4864 bits, aproximadamente el 3,7 % del almacenamiento de datos. Un diseño de escritura diferida también necesita bits de modificación; los diseños más complejos necesitan más información de control.

El índice usa los bits menos significativos de la dirección de bloque para que los bloques sucesivos se distribuyan en entradas sucesivas. Una dirección más ancha deja sin cambios las anchuras del desplazamiento y del índice cuando la capacidad y el tamaño de bloque se mantienen fijos; los bits adicionales amplían la etiqueta.

Una traza de caché registra cómo cambia cada acceso los bloques almacenados. Mantén un estado separado para cada entrada y actualízalo inmediatamente después de cada fallo. La siguiente solicitud usa la caché actualizada, no la caché tal como estaba al principio.

Prepara la traza

Toma una caché de correspondencia directa de 64 bytes con cuatro entradas de 16 bytes. Comienza vacía. Para cada dirección de byte, divide entre 16 para hallar el bloque y después calcula el bloque módulo 4 para obtener el índice. La etiqueta es el número de bloque dividido entre 4, con la parte fraccionaria descartada. Hay 4 bits de desplazamiento y 2 bits de índice.

En una lectura, examina la entrada seleccionada. Si es válida y la etiqueta coincide, registra un acierto. En caso contrario, registra un fallo, reemplaza el bloque y la etiqueta de esa entrada y activa su bit de validez. En una caché de correspondencia directa no hay opción de reemplazo.

Sigue los ocho accesos

El primer acceso llena la entrada 0 con el bloque 0. La dirección siguiente, 0x04, sigue dentro de ese bloque de 16 bytes, por lo que acierta pese a señalar un byte diferente. 0x40 pertenece al bloque 4. Tiene el mismo índice que el bloque 0, pero una etiqueta diferente, por lo que reemplaza al bloque 0.

Por tanto, el segundo 0x00 falla. El uso anterior por sí solo no puede garantizar un acierto: el bloque debe seguir presente. La solicitud a 0x14 carga el bloque 1 en la entrada 1 y deja la entrada 0 sin cambios.

A continuación, 0x44 vuelve a cargar el bloque 4 en la entrada 0. 0x08 necesita el bloque 0 y expulsa al bloque 4. Por último, 0x84 carga el bloque 8 en esa misma entrada. Al final, la entrada 0 contiene el bloque 8 y la entrada 1 contiene el bloque 1; las entradas 2 y 3 siguen siendo inválidas.

Interpreta el comportamiento

Hay un acierto y siete fallos, por lo que la tasa de aciertos es $1\mathrm{/}8=\mathrm{12,5}\mathrm{\%}$. Los bloques 0, 4 y 8 compiten por la entrada 0. La caché tiene cuatro entradas, pero este patrón de acceso usa solo dos de ellas. Las expulsiones repetidas se deben a conflictos de asignación, no a una falta de almacenamiento total para los cuatro bloques distintos.

La carga de un bloque pone a disposición todos sus bytes. Por tanto, en un recorrido secuencial, un fallo puede servir para muchos de los elementos siguientes. Aquí los accesos en conflicto eliminan repetidamente ese beneficio antes de que se solicite el siguiente byte cercano.

Para obtener trazas fiables, identifica explícitamente las direcciones de byte y los números de bloque. Aplicar módulo 4 directamente a la dirección de byte omite la división entre el tamaño de bloque y envía las solicitudes a entradas equivocadas. Registra el reemplazo incluso cuando el nuevo bloque se haya cargado antes: cada fallo instala el bloque solicitado y su etiqueta en la entrada seleccionada.

Una caché asociativa por conjuntos ofrece a un bloque varias entradas posibles sin buscar en toda la caché. El índice selecciona un conjunto y el bloque puede ocupar cualquier vía de ese conjunto. Esto reduce los conflictos entre bloques que comparten un índice.

Calcula los conjuntos y los campos

Para una capacidad de datos $C$, un tamaño de bloque $B$ y una asociatividad $n$:

El índice de conjunto es la dirección de bloque módulo el número de conjuntos. El desplazamiento sigue dependiendo solo del tamaño de bloque. La etiqueta contiene los bits más significativos restantes.

Una caché de 32 KiB y 8 vías con bloques de 64 bytes tiene 512 bloques y 64 conjuntos. Con direcciones de 32 bits, las anchuras del desplazamiento, el índice y la etiqueta son de 6, 6 y 20 bits. La dirección 0x1234ABCD tiene desplazamiento 13, conjunto 47 y etiqueta 0x1234A.

Con capacidad y tamaño de bloque fijos, duplicar la asociatividad reduce a la mitad el número de conjuntos. Un bit de índice se convierte en un bit de etiqueta; no se añade capacidad de datos.

La búsqueda compara la etiqueta en paralelo con todas las etiquetas válidas del conjunto elegido. Una vía coincidente suministra los datos mediante un selector. Más vías requieren más comparaciones y hardware de selección, lo que puede aumentar el tiempo de acierto y la energía.

Reemplaza un bloque solo cuando el conjunto está lleno

Usa primero una vía inválida. Cuando todas las vías están ocupadas, LRU, o reemplazo del bloque usado menos recientemente, expulsa el bloque cuyo acceso más reciente es el más antiguo. Actualiza la información de uso reciente tanto en los aciertos como en las cargas. Un conjunto de 2 vías solo necesita un bit para registrar su vía LRU; los conjuntos más grandes suelen usar aproximaciones pseudo-LRU.

FIFO expulsa el bloque cargado antes, aunque se haya accedido a él recientemente. El reemplazo aleatorio elige una víctima sin mantener toda la información de uso reciente. Es sencillo y puede rendir de forma similar a LRU en cachés grandes.

Revisa la traza pequeña con dos vías

La caché de 64 bytes con bloques de 16 bytes tiene ahora dos conjuntos de dos vías. Los bloques 0, 4 y 8 se asignan al conjunto 0, mientras que el bloque 1 se asigna al conjunto 1. Para 0x00, 0x04, 0x40, 0x00, 0x14, 0x44, 0x08, 0x84, los resultados son fallo, acierto, fallo, acierto, fallo, acierto, acierto, fallo.

Los bloques 0 y 4 pueden coexistir, por lo que los accesos repetidos a ellos aciertan. Justo antes del último acceso, el bloque 0 se usó más recientemente que el bloque 4. Al cargar el bloque 8, LRU expulsa el bloque 4. Cuatro de ocho accesos aciertan, frente a uno en la versión de correspondencia directa.

La asociatividad no puede eliminar los fallos obligatorios ni hacer que quepa un conjunto de trabajo mayor que la capacidad. Tampoco puede evitar los conflictos cuando más de n bloques muy usados compiten por un conjunto de n vías. Un ciclo repetido de n+1 bloques de este tipo puede hacer que LRU falle cada vez. Añadir relleno a los arreglos puede cambiar su asignación a conjuntos; elegir más vías es solo una posible respuesta a un problema de conflictos.

Un fallo de caché es un evento que tiene tanto un mecanismo como una causa. El mecanismo describe cómo se atiende la solicitud. La causa explica por qué faltaba el bloque necesario y qué cambio de diseño podría ayudar.

Gestiona un fallo de lectura

En un cauce de segmentación sencillo con ejecución en orden, la caché detecta una entrada inválida o una etiqueta que no coincide y el procesador se detiene. La caché solicita el bloque al nivel siguiente. Si la víctima elegida está modificada, sus datos cambiados deben conservarse escribiéndolos en el nivel inferior. El bloque que llega se instala con su etiqueta y bit de validez, y se completa el acceso pendiente. Un fallo de la caché de instrucciones también espera el bloque de la instrucción y después busca de nuevo la instrucción.

La transferencia de la palabra crítica primero solicita primero la palabra necesaria del bloque que se devuelve. La reanudación anticipada permite reanudar la ejecución en cuanto llega esa palabra. Una caché no bloqueante puede atender otros aciertos y llevar el seguimiento de los fallos pendientes mientras un procesador con ejecución fuera de orden realiza trabajo independiente. Estos mecanismos reducen la espera; no hacen desaparecer la dependencia de datos original.

Usa las tres C

Aplica primero la prueba del primer acceso. El primer acceso a un bloque es obligatorio aunque su entrada de destino ya esté ocupada. Para los fallos posteriores, compara la caché real con una caché LRU completamente asociativa de igual capacidad de datos y tamaño de bloque, ambas con el mismo historial de accesos.

En la traza anterior de cuatro entradas, los bloques 0, 4, 1 y 8 causan cada uno un fallo obligatorio. La caché de correspondencia directa también falla en los accesos repetidos a los bloques 0 y 4. Una caché completamente asociativa de cuatro entradas puede conservar los cuatro bloques distintos, por lo que esos tres fallos repetidos son de conflicto. No hay fallos de capacidad.

Elige un cambio que aborde la causa

Aumentar la capacidad puede permitir conservar un conjunto de trabajo mayor. Aumentar la asociatividad puede permitir que coexistan bloques en conflicto. Aumentar el tamaño de bloque puede aprovechar la localidad espacial al traer más elementos vecinos útiles con cada carga.

El tamaño de bloque tiene efectos contrapuestos. Con una capacidad de datos fija, los bloques más grandes implican menos bloques presentes. Los bytes no utilizados consumen espacio de caché, pueden desplazarse bloques útiles no relacionados y cada transferencia puede tardar más. La tasa de fallos suele bajar inicialmente al crecer el tamaño de bloque y después subir cuando estos costes superan el beneficio de la localidad espacial.

Una caché más grande también puede tener una búsqueda más larga, y las vías adicionales requieren más hardware de comparación. Evalúa los cambios mediante el tiempo medio de acceso, incluidos el tiempo de acierto y la penalización por fallo, en vez de suponer que una menor tasa de fallos garantiza un diseño más rápido.

En sistemas multinúcleo, la invalidación tras una escritura de otro núcleo puede causar fallos de coherencia. La precarga puede traer un bloque antes de su primer acceso por demanda, ocultando un fallo por demanda que la capacidad adicional por sí sola no puede evitar.

Una instrucción de almacenamiento cambia un valor, por lo que la jerarquía necesita una regla para transmitir ese cambio hacia abajo. Hay dos decisiones separadas: qué hacer cuando un almacenamiento acierta y qué hacer cuando falla.

Escritura directa y escritura diferida

Un bit de modificación registra que un bloque de escritura diferida contiene cambios que aún no se han escrito en el nivel siguiente. Una víctima limpia no necesita escritura diferida al nivel inferior. Los datos modificados de una víctima deben conservarse antes de poder reutilizar su entrada. Las cargas del procesador obtienen el valor nuevo de la caché incluso mientras la copia inferior es más antigua.

Para 100 almacenamientos en una variable de 4 bytes alojada en caché, la escritura directa sin combinar envía 100 escrituras, o 400 bytes de datos útiles. La escritura diferida puede combinar esos cambios en una escritura de un bloque de 64 bytes al expulsarlo. Esta comparación cuenta los datos útiles de actualización y excluye la carga inicial y la sobrecarga del protocolo.

El beneficio depende de la reutilización. Las escrituras repetidas en un bloque dan a la escritura diferida la oportunidad de combinar actualizaciones; las escrituras dispersas en muchos bloques pueden provocar muchas expulsiones de bloques modificados. Las cachés inferiores suelen usar escritura diferida para limitar el tráfico hacia la DRAM. Las cachés de datos L1 pueden usar cualquiera de las dos políticas.

Un búfer de escritura oculta la espera, no el tráfico

Un búfer de escritura pone en cola las escrituras pendientes hacia el nivel inferior. Con escritura directa, el procesador puede continuar en cuanto un almacenamiento entra en el búfer, en vez de esperar a que termine la escritura en la memoria inferior. El nivel inferior se pone al día a medida que se vacían los almacenamientos del búfer; puede quedar temporalmente por detrás del valor de la caché.

El búfer tiene capacidad finita. Si los almacenamientos llegan más rápido de lo que el nivel inferior los acepta durante suficiente tiempo, se llena y el procesador se detiene. Un búfer cambia cuándo espera el procesador, no el ancho de banda sostenido del destino.

Sin búfer ni solapamiento, si el 10 % de las instrucciones son almacenamientos y cada almacenamiento añade 100 ciclos de espera, un CPI base de 1 pasa a ser $1+\mathrm{0,1}\times 100=11$. El uso de un búfer puede ocultar gran parte de esta demora cuando el destino mantiene el ritmo en promedio.

Trata por separado un fallo de escritura

La asignación en escritura busca el bloque ausente y lo lleva a la caché; después aplica el almacenamiento. Combina de forma natural con la escritura diferida porque los accesos y escrituras posteriores pueden reutilizar ese bloque. La política sin asignación en escritura, también llamada escritura alrededor de la caché (write-around), envía el almacenamiento al nivel inferior sin cargar el bloque en esta caché. Combina de forma natural con la escritura directa y puede evitar el desplazamiento de bloques útiles durante un flujo de salida de una sola vez.

Estas son decisiones de política independientes. Saber que una caché es de escritura directa no indica por sí solo si un fallo de escritura asigna una línea; una traza debe especificar ambas políticas.

Un fallo de escritura diferida que selecciona una víctima modificada implica datos salientes además de la carga entrante, lo que aumenta la penalización salvo que los búferes o el solapamiento oculten parte del trabajo. Otros núcleos y dispositivos de entrada y salida también necesitan una visión coherente cuando la memoria inferior está desactualizada. La coherencia y los mecanismos del sistema coordinan esa visibilidad; un bit de modificación por sí solo registra los cambios pendientes.

Una tasa de aciertos alta es útil, pero no es una medida completa del rendimiento. Un pequeño número de fallos costosos puede dominar el promedio, y un diseño que evita más fallos puede aun así resultar peor si su búsqueda se vuelve demasiado lenta.

Empieza por las definiciones de tasas y tiempos

Las dos fracciones suman uno. Convierte los porcentajes en fracciones antes de multiplicar: el 5 % es 0,05.

El tiempo medio de acceso a memoria, o AMAT, es

Toda solicitud comprueba la caché, incluidas las solicitudes que fallan. La penalización es la demora adicional después de esa búsqueda. De forma equivalente, pondera el tiempo de acierto por la fracción de aciertos y el tiempo total de fallo por la fracción de fallos; al desarrollar la expresión se obtiene la misma fórmula.

Con un tiempo de acierto de 1 ciclo, un 5 % de fallos y una penalización adicional de 100 ciclos, el AMAT es $1+\mathrm{0,05}\times 100=6$ ciclos. A 2 GHz, cada ciclo dura 0,5 ns, por lo que son 3 ns. Haz todos los cálculos en ciclos o todos en unidades de tiempo y después convierte el resultado final si es necesario.

Compara diseños completos

La caché A tiene una búsqueda de 1,0 ns y un 5 % de fallos. La caché B tiene una búsqueda de 1,2 ns y un 3,5 % de fallos. Con una penalización de 50 ns:

B gana porque evitar fallos costosos compensa con creces su búsqueda más lenta. Si la penalización baja a 10 ns, A tarda 1,5 ns y B tarda 1,55 ns. Ahora gana A. El valor de una mejora de la tasa de fallos es proporcional a la penalización que evita.

Pondera correctamente los accesos a instrucciones y datos

Supón que cada instrucción produce una búsqueda de instrucción y 0,3 accesos a datos en promedio. La tasa de fallos de instrucciones es del 2 % y la tasa de fallos de datos es del 4 %. En 100 instrucciones hay 100 búsquedas y 30 accesos a datos. Los fallos esperados son $100\times \mathrm{0,02}+30\times \mathrm{0,04}=\mathrm{3,2}$ de 130 accesos.

La fracción combinada de fallos es, por tanto, $\frac{\mathrm{0,02}+\mathrm{0,3}\times \mathrm{0,04}}{\mathrm{1,3}}\mathrm{.}$ Con tiempos de acierto iguales de 1 ciclo y penalizaciones de 100 ciclos, el AMAT es de unos 3,46 ciclos por acceso a memoria. Promediar directamente el 2 % y el 4 % daría incorrectamente el mismo peso a los dos tipos de acceso.

Estima una penalización de transferencia

Una solicitud de bloque puede incluir una latencia inicial seguida del tiempo de transferencia. Con una latencia de 60 ns, una línea de 64 bytes y un ancho de banda de 16 GB/s, la transferencia tarda 4 ns, lo que hace que la penalización adicional sea de unos 64 ns. A 3 GHz hay 3 ciclos/ns, por lo que equivale a 192 ciclos.

Comprueba qué incluye el tiempo indicado en un problema. Si proporciona un tiempo completo de acceso con fallo, resta la búsqueda inicial antes de tratar esa cifra como una penalización adicional por fallo. Contar la búsqueda dos veces sobreestima el AMAT.

El AMAT mide el tiempo por acceso a memoria. El CPI mide los ciclos por instrucción ejecutada. Para relacionarlos, cuenta cuántas solicitudes de instrucciones y datos produce cada instrucción y cuántos ciclos de parada añaden esas solicitudes.

Suma los términos de parada

Para un procesador sencillo con ejecución en orden cuyos aciertos de caché están incluidos en el CPI base, un fallo que no se solapa añade su penalización adicional. Con una tasa de fallos de instrucciones $m_I$, accesos a datos por instrucción $f_D$, una tasa de fallos de datos $m_D$ y una penalización $P$ en ciclos:

Cada instrucción tiene una solicitud de búsqueda de instrucción en este modelo. Solo las cargas y los almacenamientos hacen solicitudes de datos, por lo que debes multiplicar su tasa de fallos por su frecuencia. Si sus penalizaciones difieren, usa una penalización distinta en cada término.

Pasa de las solicitudes a las paradas

Sea el CPI base 1,0, la tasa de fallos de instrucciones del 2 %, la frecuencia de cargas y almacenamientos del 30 %, la tasa de fallos de datos del 4 % y la penalización por fallo de 100 ciclos. Las paradas por instrucciones son $\mathrm{0,02}\times 100=\mathrm{2,0}$ ciclos por instrucción. Las paradas por datos son $\mathrm{0,3}\times \mathrm{0,04}\times 100=\mathrm{1,2}$. El CPI total es 4,2.

Con una caché perfecta, el CPI volvería a 1,0. Con el mismo reloj y número de instrucciones ejecutadas, eso daría un factor de aceleración de 4,2. La tasa de fallos de datos es el doble de la tasa de fallos de instrucciones, pero los fallos de instrucciones cuestan más tiempo en total porque se busca cada instrucción y solo el 30 % accede a datos.

No introduzcas el AMAT directamente como CPI. El AMAT es por acceso e incluye el tiempo de servicio de los aciertos. El cálculo del CPI aquí añade solo las paradas que exceden la ejecución base ya contabilizada.

Un reloj más rápido hace que cada espera de memoria cueste más ciclos

La latencia de la DRAM en nanosegundos no disminuye cuando aumenta la frecuencia del reloj del procesador. Duplicar la frecuencia convierte la misma espera de memoria de 100 ciclos en 200 ciclos con el nuevo reloj. El CPI del ejemplo pasa a ser

Cada nuevo ciclo dura la mitad, por lo que el tiempo de ejecución relativo pasa de 4,2 ciclos antiguos por instrucción al equivalente de 3,7 ciclos antiguos. El factor de aceleración es $\mathrm{4,2}\mathrm{/}\mathrm{3,7}\approx \mathrm{1,14}$, muy por debajo de dos.

Las mejoras desplazan el cuello de botella

Si el CPI base baja de 1,0 a 0,5 mientras las paradas de memoria permanecen en 3,2, el CPI total pasa a ser 3,7. Las paradas consumen ahora $\mathrm{3,2}\mathrm{/}\mathrm{3,7}\approx 86\mathrm{\%}$ de los ciclos. Mejorar el núcleo hace que la demora de memoria sin cambios ocupe una mayor proporción del tiempo de ejecución, un ejemplo de la ley de Amdahl.

El modelo sencillo cuenta todas las demoras por fallos como paradas. La ejecución fuera de orden y las cachés no bloqueantes pueden solapar los fallos con trabajo útil u otros fallos. Se necesitan contadores de hardware y mediciones del tiempo de ejecución para evaluar ese solapamiento en una máquina real. Al comparar diseños con este modelo, mantén el mismo flujo de instrucciones e indica qué demoras ya están incluidas en el CPI base.

Una caché inferior reduce la penalización que se paga cuando L1 falla. Tiene su propio tiempo de búsqueda y tasa de fallos, por lo que el coste esperado de la jerarquía debe seguir la fracción de solicitudes que llega a cada nivel.

Ten en cuenta el denominador de cada tasa

La tasa local de fallos de un nivel es su número de fallos dividido entre las solicitudes a ese nivel. Su tasa global de fallos es su número de fallos dividido entre todas las solicitudes de memoria del procesador.

Si L1 falla el 4 % de las veces y L2 falla en el 25 % de esas solicitudes, solo $\mathrm{0,04}\times \mathrm{0,25}=\mathrm{0,01}$, o el 1 % de las solicitudes originales, llega a memoria. Una tasa local de fallos de L2 del 25 % no dice por sí sola qué fracción de todas las solicitudes llega a memoria: L1 filtró primero el flujo.

Para dos niveles comprobados secuencialmente:

Aquí $H_1$ y $H_2$ son tiempos de búsqueda, $m_1$ y $m_2$ son fracciones locales de fallos y $P$ es la penalización adicional de memoria. Solo los fallos de L1 pagan la búsqueda de L2. Solo los fallos en ambos niveles pagan la penalización de memoria.

Evalúa desde dentro hacia fuera

Usa un tiempo de acierto de L1 de 1 ciclo, una tasa de fallos de L1 del 4 %, un tiempo de acierto de L2 de 12 ciclos, una tasa local de fallos de L2 del 25 % y una penalización de memoria de 200 ciclos. Una solicitud que llega a L2 tarda en promedio $12+\mathrm{0,25}\times 200=62$ ciclos adicionales. Así,

Sin L2, el AMAT sería $1+\mathrm{0,04}\times 200=9$ ciclos. La búsqueda de L2 añade trabajo a cada fallo de L1, pero evita que la mayoría de esas solicitudes paguen la demora de memoria mucho mayor.

No sustituyas $m_2$ por la tasa global de fallos de L2 del 1 % dentro del paréntesis. Eso multiplicaría dos veces por la fracción de fallos de L1. Una forma desarrollada equivalente usa directamente la tasa global:

Añade L3 con la misma lógica

Con un tiempo de acierto de L3 de 40 ciclos y una tasa local de fallos del 40 %, el término de servicio de L3 es $40+\mathrm{0,4}\times 200=120$ ciclos. El término de L2 pasa a ser $12+\mathrm{0,25}\times 120=42$ ciclos. El AMAT global es $1+\mathrm{0,04}\times 42=\mathrm{2,68}$ ciclos.

La expresión completa es $H_1+m_1(H_2+m_2(H_3+m_{3}P))\mathrm{.}$ L3 se imputa solo a las solicitudes que fallan en ambos niveles superiores. Un nivel con una búsqueda muy lenta o muy pocos aciertos puede añadir más demora de la que ahorra.

Usa tasas por instrucción para el CPI

Supón que el CPI base es 1, L1 produce 0,032 fallos por instrucción y la memoria añade 100 ciclos. Sin L2, el CPI es $1+\mathrm{0,032}\times 100=\mathrm{4,2}$. Añade una L2 de 10 ciclos cuya tasa local de fallos es del 25 %:

Con el mismo reloj, el factor de aceleración es $\mathrm{4,2}\mathrm{/}\mathrm{2,12}\approx \mathrm{1,98}$. La cifra 0,032 ya representa fallos por instrucción, por lo que otro multiplicador de frecuencia de acceso contaría esa frecuencia dos veces.

La memoria virtual separa las direcciones que usa un programa de las posiciones que contienen sus datos en la memoria principal. Cada proceso obtiene su propio espacio de direcciones virtuales. El hardware traduce las direcciones mediante las correspondencias del sistema operativo y comprueba si cada acceso solicitado está permitido.

Sustituye el número de página y conserva el desplazamiento

Una página es una región de tamaño fijo de direcciones virtuales. Un marco de página es un espacio del tamaño de una página en la memoria física. Con páginas de 4 KiB, cada página contiene 4096 bytes, por lo que el desplazamiento dentro de la página necesita 12 bits. Los bits más significativos restantes de la dirección virtual forman el número de página virtual, o VPN.

Una entrada de la tabla de páginas, o PTE, asigna un VPN a un número de página física, o PPN. La traducción sustituye el número de página, pero conserva el desplazamiento: se selecciona la misma posición de byte dentro del marco físico.

Para la dirección virtual 0x00403A7C, los 12 bits menos significativos dan el desplazamiento 0xA7C y el VPN es 0x00403. Si ese VPN se asigna al PPN 0x02F1C, la dirección física es 0x02F1CA7C. Añadir un desplazamiento de 12 bits al final equivale a multiplicar el PPN por 4096 y sumar el desplazamiento; sumar el PPN sin desplazar daría una dirección incorrecta.

Una correspondencia incluye permisos

Una PTE registra la validez, un número de página física y permisos como lectura, escritura, ejecución y acceso de usuario. Los bits de acceso y modificación registran el uso y la modificación. Un registro privilegiado del procesador identifica la tabla de páginas; RISC-V usa satp. Los programas de usuario no pueden reescribir libremente estas correspondencias.

Las tablas de páginas separadas permiten que una misma dirección virtual se refiera a datos físicos diferentes en distintos procesos. También permiten la compartición selectiva: dos procesos pueden asignar páginas virtuales al mismo marco físico, por ejemplo, para compartir código de biblioteca de solo lectura. El aislamiento y la compartición son ambos consecuencias de las correspondencias controladas.

Un fallo de página necesita la atención del sistema operativo

Un fallo de página es una excepción que se produce cuando la traducción o sus comprobaciones de permisos no pueden completarse normalmente. Un almacenamiento en una correspondencia de solo lectura puede provocar un fallo incluso si la página ya está en memoria.

Cuando una página necesaria no está en la memoria principal, el sistema operativo obtiene un marco físico, lee la página del almacenamiento, actualiza la correspondencia y reinicia la instrucción. Es posible que primero deba escribirse en el nivel inferior una página víctima modificada. Algunos fallos se resuelven sin almacenamiento, como al establecer una correspondencia con una página existente o gestionar la copia en escritura. Un acceso que el sistema no puede permitir puede terminar en un error del proceso.

Los fallos que requieren almacenamiento son costosos. A 3 GHz, una demora de 50 µs cuesta 150 000 ciclos y 1 ms cuesta 3 000 000. Las páginas grandes reparten los costes de transferencia entre muchos bytes. Una página virtual puede ocupar cualquier marco adecuado, y las páginas modificadas usan escritura diferida porque enviar cada almacenamiento directamente al almacenamiento secundario sería demasiado lento.

Las tablas de páginas también consumen memoria

Una tabla plana para direcciones virtuales de 32 bits y páginas de 4 KiB necesita $2^{32-12}=2^{20}$ entradas. Con 4 bytes por entrada, son 4 MiB por proceso. Los diseños reales usan tablas multinivel para evitar asignar una enorme tabla plana a espacios de direcciones dispersos; RISC-V Sv39 usa tres niveles.

La memoria virtual incluye traducción de direcciones, protección y compartición incluso cuando todas las páginas usadas caben en la DRAM. La paginación al almacenamiento es un uso de ese mecanismo, no todo su propósito.

La traducción de direcciones puede requerir varias lecturas de la tabla de páginas antes de que continúe un acceso a datos. Las entradas de la tabla de páginas pueden acertar en las cachés ordinarias, pero esas lecturas siguen añadiendo trabajo. El búfer de traducciones anticipadas, o TLB, almacena en caché las traducciones usadas recientemente para que la mayoría de los accesos puedan evitar un recorrido de la tabla de páginas.

Sigue un acceso permitido

Se busca el número de página virtual en el TLB. Una entrada coincidente proporciona el número de página física y la información de permisos. Tras las comprobaciones de permisos, la dirección física identifica los datos en la jerarquía de caché.

Ante un fallo de TLB, un recorrido de la tabla de páginas obtiene la traducción. Si la correspondencia es válida y permite la solicitud, la traducción se instala en el TLB y el acceso continúa. RISC-V y x86-64 normalmente usan mecanismos de recorrido por hardware; algunas arquitecturas usan gestores de software. Si la correspondencia no puede atender la solicitud, el procesador genera un fallo de página para el sistema operativo.

Por tanto, un fallo de TLB puede acompañar tanto a un acierto como a un fallo de caché de datos. Indica que la traducción no estaba en el TLB, no que la página faltara en la DRAM. A la inversa, un acierto de TLB puede acompañar a un fallo de caché o a un fallo de permisos por un acceso prohibido. La traducción y la presencia de los datos responden a preguntas diferentes.

Cuenta la memoria cubierta por las traducciones

La cobertura del TLB es el número de entradas multiplicado por el tamaño de página. Un TLB de 64 entradas con páginas de 4 KiB cubre 256 KiB a la vez. Con páginas de 2 MiB, 64 entradas cubren 128 MiB. Acceder a muchas páginas diferentes puede agotar la capacidad de traducción incluso cuando solo se usan unos pocos bytes de cada página.

Los TLB de primer nivel suelen contener decenas de entradas; los niveles inferiores de TLB pueden contener cientos o miles. Sus entradas incluyen etiquetas de número de página, correspondencias físicas, permisos y, a menudo, identificadores del espacio de direcciones. La localidad dentro de las páginas y la reutilización entre accesos cercanos mantienen altas las tasas de aciertos de traducción.

Por ejemplo, si el 1 % de los accesos requiere un recorrido de 30 ciclos y el tiempo de acierto de TLB está oculto por lo demás, los recorridos añaden $\mathrm{0,01}\times 30=\mathrm{0,3}$ ciclos por acceso en promedio. Este ejemplo supone que los recorridos terminan normalmente y excluye la gestión de fallos de página.

Solapa el indexado con la traducción

Una caché con índice físico y etiqueta física espera una dirección física antes de seleccionar su conjunto. Una caché con índice virtual y etiqueta física, o caché VIPT, comienza a leer un conjunto mientras el TLB traduce y después compara las etiquetas físicas.

El diseño VIPT sencillo toma todos los bits de índice y de desplazamiento dentro del bloque del desplazamiento dentro de la página, porque la traducción conserva esos bits. Esto requiere

Con páginas de 4 KiB, una caché de 32 KiB y 8 vías tiene 4 KiB por vía y cumple la condición. Una caché de 48 KiB y 12 vías también la cumple. Una caché de 64 KiB y 8 vías tiene 8 KiB por vía y necesita un bit del número de página para el indexado, por lo que requiere más vías o una gestión adicional.

Mantén actualizadas las correspondencias en caché

Las traducciones pertenecen a espacios de direcciones. Un cambio de contexto puede vaciar las entradas antiguas o distinguirlas mediante identificadores del espacio de direcciones, o ASID. Los cambios en las correspondencias requieren el mantenimiento correspondiente de la caché de traducciones; RISC-V proporciona sfence.vma. Cuando se expulsa una página de la memoria, su antigua traducción no debe seguir siendo utilizable en el TLB. El TLB contiene correspondencias y derechos de acceso, mientras que las cachés ordinarias contienen los datos y las instrucciones del programa.

El código que tiene en cuenta la caché aprovecha los bytes traídos antes de que se expulse su bloque. Empieza por las direcciones que genera el bucle interno. Después pregúntate qué datos se reutilizan, qué distancia hay entre los accesos y si esos bloques pueden coexistir en la caché.

Recorre los arreglos en el orden de almacenamiento

C y C++ almacenan los arreglos rectangulares en orden por filas. Las columnas adyacentes de una fila son adyacentes en memoria. Fortran, MATLAB y Julia usan el orden por columnas; los arreglos de NumPy usan por defecto el orden por filas. El recorrido interno eficiente sigue la organización real.

Un arreglo de C double a[1024][1024] ocupa 8 MiB. Cada fila ocupa 8192 bytes. Con líneas de caché de 64 bytes, cada línea contiene ocho valores de tipo double. Un recorrido por filas puede usar los ocho antes de continuar, lo que da aproximadamente un fallo de arranque en frío por cada ocho accesos en un modelo sencillo de búsqueda por demanda.

Un recorrido por columnas avanza 8192 bytes entre accesos consecutivos. Toca 1024 líneas distintas antes de volver a visitar datos cercanos en la columna siguiente. Esas líneas ocupan 64 KiB, lo que supera una L1 de 32 KiB. También entran en conflicto: en una caché de 64 conjuntos, un paso de 128 líneas conserva el índice de conjunto. Un conjunto de 8 vías no puede contener 1024 líneas que compiten entre sí.

Añadir relleno a una fila hasta alcanzar 1032 valores de tipo double hace que su paso sea de 8256 bytes, o 129 líneas. Las filas sucesivas avanzan entonces un conjunto módulo 64, distribuyendo las solicitudes. El relleno aborda los conflictos de asignación; la cantidad de datos sigue importando.

Intercambia bucles cuando se conserva el resultado

El intercambio de bucles cambia qué bucle se ejecuta dentro de otro. En la multiplicación de matrices en orden por filas, el orden i, j, k recorre secuencialmente una fila de A, pero una columna de B. En un modelo de recorrido secuencial grande con poca reutilización entre pasadas, esto cuesta aproximadamente $1\mathrm{/}8+1=\mathrm{1,125}$ fallos por iteración interna.

Con i, k, j, el bucle interno recorre secuencialmente filas de B y C, mientras se reutiliza un elemento de A. Contar un recorrido nuevo para ambas filas da aproximadamente $1\mathrm{/}8+1\mathrm{/}8=\mathrm{0,25}$ fallos por iteración, 4,5 veces menos. Si la fila de C, que se actualiza repetidamente, permanece en caché, la cifra se aproxima a 0,125. La capacidad de la caché y los conflictos determinan qué reutilización se conserva.

El intercambio debe conservar el comportamiento requerido del cálculo. Las dependencias, los punteros solapados y el orden de evaluación de coma flotante pueden limitar las transformaciones; los compiladores necesitan pruebas de que un cambio está permitido.

Trae los campos que usas

Un arreglo de estructuras agrupa todos los campos de un objeto. Una estructura de arreglos agrupa un campo de varios objetos. Si un registro de partícula contiene ocho valores de tipo double en una línea de 64 bytes, sumar solo x en un millón de registros alineados trae aproximadamente 64 MB. Un arreglo x contiguo y separado trae aproximadamente 8 MB y usa todos los valores de tipo double que llegan. El código que usa juntos todos los campos de cada partícula puede favorecer la organización original de estructuras.

Los nodos enlazados pueden estar dispersos, y cada dirección siguiente puede depender de un puntero recién cargado. Los arreglos contiguos o las reservas de nodos pueden mejorar la localidad. Los campos de uso frecuente y compactos también permiten que quepan más datos activos en cada nivel.

Mide el tiempo de ejecución y los contadores de hardware pertinentes antes y después de un cambio. Los fallos de caché pueden explicar un bucle lento, pero el cálculo, el ancho de banda o los saltos pueden ser el factor limitante. Mantén comparables la entrada y los resultados para que una diferencia de velocidad refleje el cambio que se evalúa.

El intercambio de bucles mejora el orden de acceso. El procesamiento por bloques, también llamado tiling, va más allá al mantener activa una pequeña región de datos hasta completar su reutilización útil. La precarga adelanta una transferencia futura para que su demora se solape con trabajo útil.

Mantén un grupo de bloques en caché

En la multiplicación por bloques de matrices cuadradas, un bloque de A y uno de B contribuyen a un bloque de C. Un bloque de lado $b$ contiene $b^2$ elementos. Trabajar repetidamente en estos bloques pequeños permite reutilizar datos antes de pasar a la siguiente región.

Para valores de tipo double de 8 bytes, tres bloques requieren $3b^2\times 8=24b^2$ bytes. En una caché de 32 KiB, el límite de capacidad es

Elegir un lado de 32 usa 24 576 bytes, o 24 KiB, y deja algo de espacio para otros datos. Elegir 36 solo porque la aritmética lo permite deja mucho menos espacio y puede dar lugar a conflictos. La capacidad es una estimación inicial; los tamaños reales de bloque se ajustan mediante mediciones.

Un recorrido por bloques hace avanzar el bucle exterior según el tamaño de bloque. Sus límites internos se detienen en el menor de los dos valores: el final del bloque o el tamaño de la matriz. Por ejemplo, si una dimensión es 70 y los bloques tienen lado 32, el bloque final tiene solo seis elementos en esa dimensión. Un bloque final de tamaño completo accedería más allá del arreglo.

Estima lo que ahorra la reutilización

En un modelo simplificado de matrices grandes con líneas de 64 bytes, el orden ingenuo i, j, k tiene aproximadamente $\mathrm{1,125}{N}^3$ fallos cuando las filas recorridas secuencialmente ya no están en caché en la siguiente pasada. Una versión por bloques puede reducir esto a aproximadamente $N^3\mathrm{/}(4b)$, suponiendo que los tres bloques de trabajo permanecen en caché e ignorando los conflictos.

Para $N=1024$ y $b=32$, estas estimaciones son de aproximadamente 1,2 mil millones y 8,4 millones de fallos, un factor de 144. Ambas versiones siguen realizando aproximadamente $2N^3$ operaciones de coma flotante. El ahorro está en el movimiento repetido de datos, no en el número de operaciones aritméticas de la multiplicación. El modelo describe una reutilización ideal; el factor de aceleración medido también depende del ancho de banda, la ejecución y otros sobrecostes.

Precarga con suficiente antelación para ocultar la latencia

Los mecanismos de precarga por hardware reconocen flujos como los accesos secuenciales o de paso constante. Solicitan líneas antes de que los accesos por demanda las necesiten. El software también puede solicitar búsquedas por adelantado, por ejemplo, con __builtin_prefetch de GCC o Clang.

El momento importa. Una solicitud demasiado tardía deja esperando al acceso por demanda. Una solicitud demasiado temprana puede traer una línea que se expulse antes de usarse. Una solicitud incorrecta consume ancho de banda y espacio de caché sin ayudar al programa. El seguimiento de punteros es más difícil de precargar porque la dirección siguiente a menudo solo se conoce después de que llega el nodo actual.

Una precarga oportuna puede convertir fallos posteriores por demanda en aciertos, pero las líneas siguen viajando por la jerarquía. Oculta la latencia en vez de reducir los datos necesarios de una pasada secuencial. El procesamiento por bloques ayuda cuando se reutilizan valores; un recorrido de una sola vez no tiene datos repetidos que conservar y puede estar ya limitado por el ancho de banda de memoria.