La TLB: una caché de traducciones

1. El problema: traducir es caro

Con paginación, cada acceso a memoria requiere consultar la tabla de páginas. Con tablas multinivel (tema 22), son 4 accesos a memoria (uno por nivel) antes de acceder a la RAM. Es decir, cada acceso a memoria se multiplica por 4 o 5. Para un programa que hace miles de millones de accesos por segundo, esto es inaceptable.

La observación clave es que los programas tienen localidad (tema 2): acceden repetidamente a las mismas páginas. Si el hardware recuerda las traducciones recientes, puede evitar consultar la tabla en el caso común.

2. La idea: caché de traducciones

La TLB (Translation Lookaside Buffer) es una pequeña memoria caché de hardware, dentro de la MMU, que almacena las traducciones recientes: dado un número de página virtual, devuelve el marco físico correspondiente.

Es una caché asociativa: busca en paralelo en todas las entradas. Si encuentra la página (acierto), devuelve el marco en un ciclo. Si no (fallo), consulta la tabla de páginas (lento) y guarda el resultado en la TLB.

TLB es una caché de hardware que almacena las traducciones de página virtual a marco físico más recientes, acelerando la traducción en el caso común.

3. Cómo funciona la TLB

En cada acceso a memoria:

1. Buscar en la TLB: la MMU busca el número de página virtual en la TLB.
2. Si hay acierto (hit): se obtiene el marco en un ciclo y se accede a la RAM.
3. Si hay fallo (miss): se consulta la tabla de páginas (varios accesos), se obtiene el marco, se guarda en la TLB (reemplazando una entrada si es necesario) y se accede a la RAM.

La TLB almacena también los bits de protección de la página, para no tener que consultarlos en la tabla.

4. Acierto y fallo en la TLB

La tasa de aciertos de la TLB es muy alta (95-99 %) para la mayoría de los programas, gracias a la localidad. Por eso el costo medio de la traducción es bajo.

5. Tipos de TLB

Las TLB son pequeñas (decenas a cientos de entradas) porque son caras en hardware (memoria asociativa). La L1 de datos suele tener 64-128 entradas; la L2, 512-1024.

6. El costo de un fallo

Un fallo de TLB es costoso porque requiere consultar la tabla de páginas. En x86-64 con 4 niveles:

• 4 accesos a memoria para recorrer los 4 niveles.
• Posiblemente un fallo de caché (si la tabla no está en L1/L2/L3).
• Actualizar la TLB con la nueva entrada.

El costo total de un fallo de TLB puede ser de 10 a 100 ciclos. Por eso, aunque la tasa de fallos sea baja (1-5 %), el impacto en el rendimiento es significativo.

Los fallos de TLB son más frecuentes cuando:

• El programa accede a muchas páginas distintas (baja localidad).
• Hay cambios de contexto frecuentes (la TLB se invalida).
• Se usan páginas grandes (menos entradas en la TLB).

7. Ejemplo numérico

Un programa accede a memoria con una tasa de aciertos de la TLB del 98 %. El tiempo de un acierto es 1 ciclo, y el de un fallo es 20 ciclos (acceso a la tabla en L2). El tiempo medio de traducción:

Tiempo medio = 0,98 × 1 + 0,02 × 20 = 0,98 + 0,4 = 1,38 ciclos.

Sin TLB, cada acceso costaría 20 ciclos. La TLB reduce el costo en un factor de 14.

8. Experimento en C

El programa siguiente mide el efecto de la TLB accediendo a un arreglo con distintos pasos. Un paso pequeño (localidad espacial) tiene alta tasa de aciertos de TLB; un paso grande (salto entre páginas) tiene baja:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double ahora(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec/1e9; }

int main(int argc, char **argv)
{
    size_t n = argc > 1 ? (size_t)strtoul(argv[1], NULL, 10) : (1u << 20);
    int paso = argc > 2 ? atoi(argv[2]) : 1;
    int *a = malloc(n * sizeof *a);
    for (size_t i = 0; i < n; i++) a[i] = (int)i;

    volatile long s = 0;
    for (size_t i = 0; i < n; i += paso) s += a[i];  /* calentamiento */

    double t0 = ahora();
    long sum = 0; size_t acc = 0;
    for (int r = 0; r < 5; r++)
        for (size_t i = 0; i < n; i += paso) { sum += a[i]; acc++; }
    double t1 = ahora();
    printf("n=%zu paso=%d -> %.2f ns/acceso\\n", n, paso, (t1 - t0) * 1e9 / acc);
    return 0;
}

$ gcc -std=c17 -O2 -Wall -Wextra -o tlb tlb.c
$ ./tlb 1048576 1
n=1048576 paso=1 -> 0,85 ns/acceso
$ ./tlb 1048576 1024
n=1048576 paso=1024 -> 12,5 ns/acceson=1048576 paso=1024 -> 12,5 ns/acceso

Con paso 1, la TLB tiene alta tasa de aciertos (acceso secuencial, misma página). Con paso 1024, cada acceso cae en una página distinta, causando muchos fallos de TLB.

9. Probar con un simulador

Este simulador simula una TLB pequeña y procesa una secuencia de accesos a páginas, mostrando aciertos y fallos.

10. En Linux

Linux no expone la TLB directamente, pero se puede observar su efecto:

$ perf stat -e dTLB-load-misses,dTLB-loads ./tlb 1048576 1
$ perf stat -e dTLB-load-misses,dTLB-loads ./tlb 1048576 1024

• perf stat -e dTLB-load-misses,dTLB-loads: cuenta los fallos y accesos a la TLB de datos.
• perf stat -e iTLB-load-misses,iTLB-loads: lo mismo para instrucciones.
• Comparar los resultados con paso 1 y paso 1024 muestra el efecto de la TLB.

11. Resumen

• La TLB es una caché de hardware que almacena traducciones recientes.
• En un acierto (hit), el marco se obtiene en un ciclo.
• En un fallo (miss), se consulta la tabla de páginas (costoso) y se actualiza la TLB.
• La tasa de aciertos es alta (95-99 %) gracias a la localidad.
• Hay TLB de instrucciones, datos y unificada, más TLB para páginas grandes.
• Los fallos de TLB son costosos (10-100 ciclos) y frecuentes con baja localidad.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Modifica el simulador para usar la política LRU en lugar de FIFO. ¿Cambian los resultados?
2. Calcula el tiempo medio de traducción para tasa de aciertos 95 %, 99 % y 99,9 % con fallo de 20 ciclos.
3. Ejecuta perf stat sobre ./tlb con paso 1 y paso 1024. ¿Cuántos fallos más hay?
4. Explica por qué los cambios de contexto invalidan la TLB.
5. Investiga cómo se mantiene la coherencia de la TLB en sistemas multinúcleo.
6. Compara la TLB de instrucciones y la de datos: ¿por qué están separadas?
7. Dibuja el flujo de un acceso a memoria con acierto y con fallo de TLB.