Asociatividad y fallos por conflicto

En una caché con una ranura por línea, dos líneas muy usadas que comparten ranura se expulsan una y otra vez. Dé varias vías a cada ranura y el problema casi desaparece, salvo que las filas de su tabla estén separadas exactamente 4096 bytes. Esta lección construye una caché asociativa por conjuntos y muestra cómo un tamaño de fila potencia de dos puede hacer que falle el 100 % de las lecturas.

En la caché de mapeo directo del tema anterior cada línea de memoria tiene exactamente una ranura. Si su programa sigue usando dos líneas que van a la misma ranura, digamos la línea 0 y la línea 8 en una caché de 8 ranuras, cada lectura de una expulsa a la otra, aunque las otras siete ranuras estén vacías. El tamaño de la caché no es el problema: las líneas se pelean por un sitio demasiado pequeño. Un fallo de este tipo se llama fallo por conflicto.

La solución es agrupar las ranuras. Las ranuras se reúnen en conjuntos, y cada ranura de un conjunto es una vía. Una línea de memoria pertenece a un conjunto, hallado con el mismo resto de antes, pero puede ocupar cualquier vía de ese conjunto. Dos líneas que chocan ahora comparten un conjunto con sitio para ambas. El número de conjuntos sale de los tamaños:

Una dirección ahora se divide en tres partes. El desplazamiento es el byte dentro de la línea. El índice de conjunto dice a qué conjunto pertenece la línea. La etiqueta es el resto del número de línea, y es lo que la caché compara para saber si una vía contiene esta línea. La función siguiente divide una dirección para una caché con líneas de 64 bytes y 64 conjuntos.

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1Etiqueta, índice de conjunto y desplazamiento: cada uno es una división entera o un resto de la dirección.

La dirección 74565 es el byte 5 de la línea 1165. La línea 1165 va al conjunto 13 (1165 módulo 64), y 18 es lo que queda del número de línea, la etiqueta. Toda línea cuyo conjunto sea 13 competirá por las ocho vías de ese conjunto, sea cual sea su etiqueta.

Cuando un conjunto está lleno y llega una línea nueva, una de las líneas debe salir. La regla habitual es LRU: se expulsa la línea usada menos recientemente. Podemos guardar cada conjunto como una lista de Python ordenada de la menos recientemente usada a la más recientemente usada.

1. 1
   Hallar el conjuntoEl número de línea módulo el número de conjuntos.
2. 2
   Mirar en cada víaSi acierta, mueva la línea al extremo de las más recientemente usadas.
3. 3
   Añadir si fallaPonga la línea nueva en el extremo de las más recientemente usadas.
4. 4
   Eliminar la más antiguaSi el conjunto tiene más líneas que vías, elimine la primera.

Aquí está la caché completa. La ejecución del final lee dos líneas, las direcciones 0 y 256, que chocan en una caché de 256 bytes con líneas de 64 bytes, primero con una vía y luego con dos.

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1Mover al final una línea que acierta mantiene la lista ordenada: la primera entrada es siempre la menos recientemente usada.
2. 2El conjunto lleno pierde su primera entrada, la línea menos recientemente usada.

Con una vía, las dos líneas se expulsan y las seis lecturas fallan. Con dos vías, las dos líneas caben en su conjunto: tras los dos primeros fallos en frío, cada lectura acierta. Añadir una vía eliminó todos los fallos por conflicto de este patrón.

Ahora la trampa. Una tabla de 512 columnas float64 tiene filas de exactamente 4096 bytes. Leer una columna es leer las direcciones 0, 4096, 8192 y así sucesivamente. En nuestra caché el índice de conjunto es el número de línea módulo 64, y 4096 bytes son exactamente 64 líneas, así que todas esas direcciones tienen el mismo índice de conjunto. El código muestra el conjunto de las seis primeras filas con un tamaño de fila de 4096 bytes y de 4160 bytes, que es 4096 más una línea extra.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

Con filas de 4096 bytes todos los cierres de una columna se pelean por el conjunto 0. Con filas de 4160 bytes recorren los conjuntos 0, 1, 2, 3 y así sucesivamente, usando toda la caché. El código siguiente lee 96 cierres dos veces y mide la tasa de fallos con 1, 2, 4 y 8 vías.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

La tabla con relleno solo falla en la primera pasada: 0,5 de todas las lecturas, sea cual sea el número de vías. La tabla alineada falla en cada lectura, incluso con 8 vías, porque 96 líneas necesitan 96 sitios y el conjunto tiene 8. Peor aún, LRU siempre expulsa la línea que va a leer a continuación en un patrón cíclico, así que la segunda pasada no encuentra nada. Más vías solo ayudarían al alcanzar el número de líneas.

El laboratorio sigue la lección: la división de la dirección, la caché LRU, los dos tipos de trazas, la comparación por número de vías y el estudio sobre la tabla real de SPY.

• Función · preguntaSe apoya en
• split_address(address, line_bytes, n_sets)¿Qué etiqueta, conjunto y desplazamiento tiene una dirección?La división entera
• SetAssocCache(size_bytes, line_bytes, ways).access(address)¿Esta lectura es un acierto en una caché LRU con varias vías?Conjuntos de líneas en orden LRU
• conflict_trace(n_lines, line_bytes, n_sets, rounds)¿Qué direcciones chocan todas en un conjunto?Aritmética simple
• column_trace(n_rows, row_bytes, passes)¿Qué direcciones toca la lectura de una columna?Aritmética simple
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)¿Cómo cambian más vías la tasa de fallos?SetAssocCache
• study(bars)¿Cuánto cuestan filas separadas 4096 bytes?column_tracemiss_rates_by_ways

Siguiente tema: la caché ya guarda las líneas correctas cuando no chocan, pero ¿cuánto tiempo siguen siendo útiles las líneas? En Localidad temporal y conjuntos de trabajo mide cuánto tarda en releerse un valor y halla el tamaño de caché a partir del cual un programa cabe.