Falso compartir y relleno

Cuatro hilos actualizan cada uno su propio contador, no se comparte nada, y aun así el bucle corre 40 veces más lento de lo debido. La razón es que los cuatro contadores están en una misma línea de caché y los núcleos se la disputan. Esta lección construye un pequeño modelo de coherencia de caché, muestra lo que cuesta el falso compartir en un bucle dirigido por las fechas de la tabla de SPY y lo arregla con unos bytes de relleno.

Hasta ahora un programa corría en un núcleo. Una máquina real tiene varios núcleos y cada uno tiene su propia caché pequeña y rápida. Esto crea un problema: si el núcleo 0 y el núcleo 1 tienen una copia de una línea y el núcleo 0 la cambia, el núcleo 1 no debe seguir leyendo el valor viejo. La regla de hardware que lo evita es la coherencia de caché. La forma más simple de imponerla: antes de que un núcleo escriba en una línea, se descarta la copia de esa línea en todos los demás núcleos. Eso es una invalidación.

1. 1
   Mirar en su propia cachéSi la línea no está, este acceso es un fallo.
2. 2
   Al escribir, expulsar a los demásCada otro núcleo que tenga la línea pierde su copia: una invalidación cada uno.
3. 3
   Quedarse con la líneaDespués la línea está en la caché de este núcleo, lista para su próximo acceso.

La clase siguiente guarda, para cada núcleo, el conjunto de líneas que tiene. Repetimos tres pasos: el núcleo 0 escribe el byte 0, el núcleo 1 escribe el byte 8 (la misma línea) y luego el núcleo 0 escribe de nuevo el byte 0.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1Una escritura quita la línea de cada otro núcleo que la tenga y cuenta una invalidación por copia.

Los tres accesos fallan. La escritura del núcleo 1 invalida la copia del núcleo 0, y la nueva escritura del núcleo 0 invalida a su vez la copia del núcleo 1. Los núcleos 0 y 1 nunca escribieron el mismo byte, solo bytes vecinos, y aun así se quitan la línea en cada escritura.

Una forma común de contar eventos en paralelo es dar a cada núcleo su propio contador, para que ningún núcleo espere a otro. Los contadores miden 8 bytes cada uno. Póngalos uno tras otro en un arreglo y cuatro caben en una línea de 64 bytes. Construimos las escrituras de 50 rondas de actualizaciones, una escritura por núcleo en cada ronda, y las repetimos con los contadores separados 8 bytes (compactos) y 64 bytes (con relleno). El tiempo es de 1 ns para un acceso en la caché del propio núcleo y de 60 ns para un fallo que trae la línea de otro núcleo.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

Compactos, las 200 escrituras fallan y 199 invalidan al último escritor: 12 000 ns. Con relleno, cada núcleo guarda su contador en su propia línea: cuatro fallos en frío al principio, luego cada escritura acierta y no hay invalidaciones: 436 ns. Es 27 veces más rápido para exactamente la misma aritmética, porque los cuatro núcleos ya no se quitan la línea.

Para dar a cada contador una línea propia, la distancia entre dos contadores debe ser múltiplo del tamaño de línea, así que el tamaño del elemento se redondea al siguiente múltiplo de 64. Un contador de 8 bytes ocupa 64 bytes, lo que desperdicia 56. Un elemento de 65 bytes ocupa 128. La función siguiente hace el redondeo.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

En el laboratorio cuatro núcleos cuentan cada uno los días bursátiles que atienden, y el día número i de la tabla de SPY va al núcleo día de la semana % 4. Los primeros 1000 días dirigen las escrituras en orden de fecha. Como los días siguen el calendario, el mismo núcleo rara vez escribe dos veces seguidas y la línea se quita una y otra vez. Con los contadores compactos, 818 de las 1000 escrituras fallan y 817 invalidan a otro núcleo; con ellos rellenados, solo fallan las cuatro primeras escrituras.

El laboratorio construye el modelo de coherencia, las trazas de contadores por núcleo con un paso dado, la repetición, la regla de relleno, el modelo de tiempo y el estudio sobre las fechas de SPY.

• Función · preguntaSe apoya en
• CoherentCaches(n_cores).access(core, address, write)¿Acierto o fallo, y quién pierde una copia?Aritmética simple
• counter_address(core, stride_bytes)¿Dónde vive el contador de un núcleo?Aritmética simple
• update_trace(n_cores, n_updates, stride_bytes)¿Qué escrituras hacen los núcleos?counter_address
• run_trace(trace, n_cores)¿Cuántos fallos e invalidaciones?CoherentCaches
• padding_needed(item_bytes)¿A qué distancia deben estar los elementos?Aritmética simple
• time_ns(stats)¿Cuánto tarda la ejecución?Los costes de acierto y fallo
• study(bars)¿Cuánto cuesta el falso compartir con las fechas de SPY?run_tracepadding_neededtime_ns

Siguiente tema: el falso compartir trata de núcleos que comparten un zócalo. En una máquina con dos zócalos la propia memoria está dividida: una parte está cerca de un núcleo y otra lejos. En Efectos NUMA coloca páginas en nodos, cuenta los accesos locales y remotos y valora la diferencia.