Una caché nunca trae un solo byte. Trae una línea entera de 64 bytes, así que el valor contiguo al que acaba de leer ya está allí. Esta lección construye una caché, muestra que leer en orden es ocho veces más barato que saltar una línea cada vez, y lo aplica a una tabla de precios.
La memoria viene en líneas
Traer de la memoria cuesta lo mismo sin importar cuántos bytes pida, así que el hardware pide muchos de golpe. La memoria se corta en bloques de 64 bytes y la caché siempre carga y expulsa bloques enteros. Imagine un ascensor que sube 64 bytes a la caché: si sube de todos modos, llevar a sus vecinos no cuesta nada, y la próxima vez que necesite a uno de ellos ya está arriba.
Un bloque de bytes consecutivos, 64 en la mayoría de los procesadores, que la caché carga y expulsa como una sola unidad. La línea n contiene los bytes de 64n a 64n + 63.
Cada byte tiene una dirección, un número que dice dónde está. Para hallar la línea de una dirección, divida por el tamaño de línea y descarte el resto. El código siguiente muestra la línea de cuatro direcciones.
line_bytes = 64for address in (0, 63, 64, 130): print(address, "is in line", address // line_bytes)
0 is in line 0 63 is in line 0 64 is in line 1 130 is in line 2
Las direcciones 0 y 63 comparten la línea 0, así que una vez cargada una, la otra es gratis. La dirección 64 empieza la línea 1 y la 130 está en la línea 2. Todo este tema se deriva de esa división entera.
Una caché es una tabla de ranuras
La caché más simple es una tabla con una ranura por cada línea que puede contener. Una caché de 32 KB con líneas de 64 bytes tiene 512 ranuras. Cada línea de memoria solo puede ocupar una ranura, que se halla con un resto: número de línea módulo el número de ranuras. Es una caché de mapeo directo. Como muchas líneas comparten una ranura, esta guarda además una etiqueta que dice qué línea contiene en ese momento.
- 1Hallar la líneaDivida la dirección por el tamaño de línea.
- 2Hallar la ranuraTome el número de línea módulo el número de ranuras.
- 3Comparar la etiquetaSi la ranura contiene esta línea, es un acierto.
- 4Reemplazar si fallaCargue la línea en la ranura y olvide la que estaba.
Eso es toda la caché. La clase siguiente es una versión completa y funcional en quince líneas. Leemos cuatro valores contiguos, luego la línea siguiente y luego volvemos a la dirección 0.
def line_of(address, line_bytes): return address // line_bytesclass Cache: def __init__(self, size_bytes, line_bytes): self.line_bytes = line_bytes self.n_lines = size_bytes // line_bytes self.tags = [None] * self.n_lines self.hits = 0 self.misses = 0 def access(self, address): line = line_of(address, self.line_bytes)1 slot = line % self.n_lines if self.tags[slot] == line:2 self.hits += 1 return True self.misses += 1 self.tags[slot] = line return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")
[False, True, True, True, False, True, True, False, False] 5 hits and 4 misses
- 1La ranura es el número de línea módulo el número de ranuras.
- 2Un acierto significa que la etiqueta de la ranura es esta misma línea.
Lea la lista de indicadores: la primera lectura falla y carga la línea 0, las tres siguientes aciertan porque están en la línea 0, 64 falla y carga la línea 1, 72 acierta, y volver a 0 acierta otra vez porque la línea 0 no fue expulsada. Luego la dirección 512 es la línea 8, que también va a la ranura 0 (8 módulo 8), así que expulsa la línea 0, y la última lectura de la dirección 0 falla de nuevo: un conflicto nos costó un fallo.
Una caché de 512 bytes con líneas de 64 bytes tiene solo 8 ranuras, no 512. Olvidar dividir el tamaño por el tamaño de línea es la forma habitual de construir una caché que parece enorme y se comporta mal.
Leer en orden frente a saltar
Ahora use la caché. Un valor float64 ocupa 8 bytes, así que una línea contiene ocho. Lea un arreglo en orden y la primera lectura de cada línea falla y las siete siguientes aciertan: un fallo de cada ocho. Léalo con un paso, es decir, saltando un número fijo de valores entre lecturas, y las lecturas caen en líneas distintas. El código siguiente mide la tasa de fallos para pasos de 1, 2, 4, 8 y 16 valores.
def sequential_trace(n, elem_bytes): return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride): return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64): cache = Cache(size_bytes, line_bytes) for address in trace: cache.access(address) return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16): print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))
stride 1 values: 0.125 stride 2 values: 0.25 stride 4 values: 0.5 stride 8 values: 1.0 stride 16 values: 1.0
La tasa de fallos se duplica con cada duplicación del paso hasta llegar a 1,0: con un paso de 8 valores el salto es de 64 bytes, una línea entera, así que cada lectura abre una línea nueva y la caché no ahorra nada. Un paso mayor no puede ser peor, solo igual. El patrón es la fórmula siguiente.
En casi todos los chips x86 y ARM de servidor, sí. Algunos chips usan 128 bytes en una caché externa, así que mida el tamaño de línea de la máquina de destino. Nuestra caché lo recibe como parámetro para que pruebe ambos.
La disposición de una tabla decide el paso
Una tabla de barras diarias tiene cinco números por día: apertura, máximo, mínimo, cierre y volumen. Guárdela fila a fila, como hacen la mayoría de los programas, y los cinco números de un día quedan juntos. Para leer solo los cierres se saltan cuatro valores entre lecturas: un paso de 5, que son 40 bytes. Guarde cada columna aparte y los cierres quedan uno tras otro: un paso de 1. Mismos números, mismas lecturas, distinta disposición.
closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout: ", as_rows)
column layout: 0.125 row layout: 0.625
Cinco veces más lecturas fallan cuando los cierres están espaciados. Eso no cambia la respuesta de su programa, solo su velocidad, y ninguna línea de aritmética del perfilador lo mostrará: el tiempo extra se gasta esperando a la memoria.
Lo que va a construir
El laboratorio pide las piezas que acaba de leer, en el mismo orden, y termina con el estudio sobre la tabla real de SPY.
- Función · preguntaSe apoya en
- line_of(address, line_bytes)¿Qué línea contiene esta dirección?La división entera
- Cache(size_bytes, line_bytes).access(address)¿Esta lectura es un acierto?line_of
- sequential_trace(n, elem_bytes)¿Qué direcciones toca una lectura en orden?Aritmética simple
- strided_trace(n, elem_bytes, stride)¿Qué direcciones toca una lectura con saltos?Aritmética simple
- miss_rate(trace, size_bytes, line_bytes)¿Qué parte de una traza falla?Cache
- study(bars)¿Cuánto cuesta la disposición en filas para los cierres de SPY?miss_ratestrided_trace
Siguiente tema: una caché de mapeo directo tiene una debilidad que esta lección rozó, el conflicto entre líneas que comparten una ranura. En Asociatividad y fallos por conflicto da a cada ranura varios lugares y ve por qué una tabla cuyas filas están separadas 4096 bytes puede arruinar una caché.
Lab: qué se califica
6 tareas · 100 pts- La línea de una dirección10 pts
- Una caché de mapeo directo25 pts
- Una lectura en orden10 pts
- Una lectura con paso10 pts
- La tasa de fallos de una traza20 pts
- El estudio con la tabla de SPY25 pts