Skip to content

English · Español

Lab 02 — Ver la jerarquía de cache mediante acceso con stride

Objetivo: convertir la abstracción "cache line / localidad espacial" de theory/02-memory-hierarchy.md en una curva que generaste tú mismo.

Tiempo estimado: 60–90 minutos.

Prerrequisito: lab 00 + lab 01 comprometidos.

Qué produces

Un directorio experiments/01-cache-walks/ que contenga:

  • walk.py — el benchmark de recorrido con stride.
  • results.json — tiempo de acceso por stride.
  • cache_walk.png — gráfica log-log de stride vs ns/acceso.
  • manifest.json.
  • README.md interpretando la curva.

El kernel

Asigna un buffer grande np.float32 (digamos 128 MiB — mayor que L3). Recórrelo con un stride fijo S, sumando cada S-ésimo elemento. Cronometra cuánto tarda un recorrido completo. Computa ns por acceso.

Repite para muchos strides: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.

La gráfica de stride vs ns/acceso revela el tamaño de cache line y (con la elección de tamaño de buffer correcta) los propios niveles de cache.

TODOs

Bloque A — elige las dimensiones con cuidado

  • Tamaño del buffer: mayor que L3 (≥ 64 MiB).
  • Tipo de elemento: np.float32 (4 bytes — coincide con la discusión típica de cache-line).
  • Strides: como mínimo [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] (es decir, 2^(0..10)). Nota: un stride de 16 fp32 = 64 bytes = una cache line en x86.
  • Por medición: apunta a ≥ 100 ms de tiempo de pared. Ajusta n_iters en consecuencia.

Bloque B — escribe el recorrido

La forma ingenua:

def walk(buf: np.ndarray, stride: int) -> float:
    n = len(buf)
    n_accesses = n // stride
    total = np.float32(0.0)
    for i in range(0, n, stride):
        total += buf[i]
    return total

Pero esto es un bucle de Python, así que mide overhead del intérprete, no memoria. Necesitas una forma NumPy idiomática que siga siendo memory-bound al stride elegido.

Dos opciones: - total = buf[::stride].sum() — limpio, pero [::stride] crea una vista, no una copia; sum() la recorre. - total = np.add.reduce(buf[::stride]) — lo mismo, ligeramente más rápido.

Elige una. Justifica en README.md por qué esto aísla el coste de memoria (y qué no aísla).

Bloque C — cronometra correctamente

  • Calienta una vez.
  • Cronometra con perf_counter_ns().
  • Repite las suficientes veces para obtener ≥ 100 ms totales por stride.
  • Computa ns_per_access = elapsed_ns / (n_accesses × iters).
  • Registra en results.json.

Bloque D — gráfica

  • Log-log: x = stride (elementos), y = ns/acceso.
  • Anota el tamaño de cache line (16 fp32 = 64 bytes) como una línea vertical — la curva debería mostrar un cambio de pendiente claro ahí.
  • Anota los límites L1/L2/L3 si tu elección de tamaño de buffer los expone (puede que quieras repetir el lab a tres tamaños de buffer total distintos si quieres los tres).

Bloque E — interpreta

Responde en README.md:

  1. ¿Dónde "se acoda" la curva? El primer codo es la cache line: por debajo de stride = line_size, estás reutilizando la línea ya cargada; por encima, cada acceso es una línea nueva.
  2. ¿Por qué la curva es plana por encima de un cierto stride mayor? Cuando el stride excede asociatividad × número de sets, cada acceso es un miss; más incrementos no compran nada.
  3. ¿Cuál es la razón entre el "mejor tiempo de acceso" y el "peor tiempo de acceso"? Debería ser aproximadamente la razón de latencias cache-a-DRAM.

Restricciones

  • Python puro + NumPy. Sin extensiones de C, sin cython, sin ctypes.
  • Un buffer por experimento — no asignes accidentalmente uno nuevo dentro del bucle de timing.
  • Un solo hilo.

Condiciones de parada

Terminado cuando:

  1. Los cinco archivos en el directorio.
  2. La gráfica muestra un codo visible cerca de stride = 16 (una cache line de fp32).
  3. README.md responde a las tres preguntas del Bloque E.
  4. Los números en results.json son reproducibles: volver a ejecutar walk.py da ns/acceso dentro de ±15% de la primera ejecución.

Escollos

  • El striding de NumPy se fusiona con SIMD de forma diferente. buf[::1] es contiguo; NumPy lo hace SIMD. buf[::2] no lo es; NumPy recae en un gather escalar. La transición de stride 1 → stride 2 es en parte algo de SIMD, no puramente de memoria. Anota esto en tu interpretación.
  • La curva no es lisa. Tendrá ondulaciones. Está bien.
  • A strides muy grandes, la curva puede caer. La ejecución fuera de orden puede ocultar la latencia DRAM cuando cada petición es un miss (porque todas van en paralelo). Este es el efecto de "memory-level parallelism" — interesante, distractor; menciónalo pero no optimices por ello.

Cuándo consultar solutions/

Después de comprometer tus cinco archivos. Solución en solutions/02-cache-walks-ref.md (escrita en apertura de fase).

Siguiente lab: lab/03-roofline-plot.md. Este es el lab de integración.