Precarga

Un fallo solo cuesta 80 ns si el programa tiene que esperarlo. Un precargador pide una línea antes que el programa, de modo que la espera ha terminado cuando llega la lectura. Esta lección construye dos precargadores, los puntúa con cobertura y precisión, y muestra dónde funcionan, en bucles con paso regular, y dónde no pueden, en lecturas en orden impredecible.

Hasta ahora la caché cargaba una línea cuando una lectura fallaba. Una precarga la carga antes. Si la apuesta es buena, la lectura que llega después encuentra la línea ya en la caché y acierta. Todos los procesadores modernos tienen precargadores de hardware que vigilan las direcciones de las lecturas y adivinan lo siguiente. La apuesta más simple: quien leyó la línea L querrá luego la línea L + 1. Nuestra caché dada tiene un método fill que carga una línea sin contar acierto ni fallo, que es exactamente una precarga.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1Precargar la línea siguiente no cuesta nada aquí: fill no cuenta como acierto ni como fallo.

Al leer 800 valores en orden, una caché simple falla una vez por línea, 100 veces. Con el precargador de línea siguiente falla una sola vez en total: tras la primerísima lectura, la línea que hace falta a continuación ya está siempre allí. El segundo caso muestra el límite. Si el programa salta 4096 bytes cada vez, la línea que sigue a la actual es inútil y el precargador no ahorra nada: siguen siendo 50 fallos de 50 lecturas.

Los precargadores reales buscan un patrón en las líneas que lee un programa. El más común es un paso constante: el programa lee las líneas 0, 3, 6, 9, saltando tres líneas cada vez. Un detector de pasos recuerda la última línea y el último salto. Cuando el nuevo salto iguala al anterior, es un patrón y la línea siguiente es la actual más el salto. Hacen falta dos saltos iguales para estar seguro, así que nunca adivina en las dos primeras lecturas.

1. 1
   Ignorar una repeticiónLeer otra vez la misma línea no dice nada sobre un paso.
2. 2
   Calcular el saltoLa línea nueva menos la última línea.
3. 3
   Comparar con el último saltoSaltos iguales significan un patrón: prediga la línea nueva más el salto.
4. 4
   RecordarGuarde el nuevo salto y la nueva línea para la siguiente lectura.

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1Dos saltos iguales seguidos: es un paso, así que la línea siguiente es la actual más el salto.

La primera secuencia es un paso de tres líneas. El detector no dice nada en las dos primeras lecturas y luego predice 9, 12 y 15, siempre un paso por delante. En la segunda secuencia se ignoran las lecturas repetidas de la línea 5 y el paso de 1 solo se confirma en la última lectura. Un buen detector es cauto: una predicción errónea tiene un precio, como veremos a continuación.

Dos números puntúan a un precargador. La cobertura dice cuánto del problema resolvió. La precisión dice cuánto de su trabajo fue útil. Para medirlos pasamos la traza por la caché, hacemos una lectura, preguntamos al precargador qué cargar después, recordamos qué líneas se precargaron y contamos cuándo una lectura acierta en una de ellas.

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

En la lectura en orden el precargador elimina el 98,8 % de los fallos y el 99,6 % de sus precargas se usan. En la lectura mezclada no hace nada: sin un paso repetido casi nunca emite una precarga (solo una), y por tanto tampoco hace daño. Ese es el comportamiento deseado. Un precargador que adivinara todo el tiempo llenaría la caché de líneas que nadie lee.

El laboratorio lee 2000 cierres de tres formas: guardados uno tras otro y leídos en orden, guardados dentro de filas de cinco valores (un paso de 40 bytes), y guardados uno tras otro pero leídos por volumen de negociación creciente. Las dos primeras tienen un patrón regular; la tercera visita los días en un orden que parece aleatorio, porque el volumen de un día no dice nada del volumen del siguiente.

La pista está en la pregunta que responde el precargador: ¿qué viene después? Si la respuesta está en el patrón de las direcciones, el hardware la halla gratis. Si el orden depende de los datos, como cuando se visitan filas ordenadas por volumen, nada puede adivinarlo. La solución por software es cambiar la disposición de los datos para que el acceso vuelva a ser regular, por ejemplo ordenando las filas una vez y luego leyéndolas en orden.

El laboratorio construye los dos precargadores, la simulación que los puntúa y el estudio sobre las tres formas de leer los cierres de SPY.

• Función · preguntaSe apoya en
• baseline_misses(trace)¿Cuántos fallos sin precarga?Cache
• next_line_misses(trace)¿Cuántos con un precargador de línea siguiente?Cache.fill
• StridePrefetcher().observe(line)¿Qué línea viene después?La última línea y el último salto
• run_with_prefetcher(trace, prefetcher)¿Qué pasó: fallos, precargas, útiles?Cache
• quality(trace)¿Qué cobertura y precisión alcanza?baseline_missesrun_with_prefetcher
• study(bars)¿Dónde ayuda el precargador en los cierres de SPY?qualitynext_line_misses

Siguiente tema: hasta ahora una dirección era una línea y solo importaba un acierto de caché. En TLB y páginas grandes toda dirección debe traducirse primero de una página virtual a una física, y una pequeña caché de traducciones, el TLB, también puede fallar, de una forma que depende del tamaño de página.