← volver a yonesuarez.es

Nota técnica · Rust / Arquitectura de Computadores

De 0,63 a 78,81 GFLOPS en Rust sin dependencias: caché L1 y AVX2

Sobre cómo un cambio de orden de bucles y localidad espacial multiplica por 124× el rendimiento de un GEMM 1024×1024 usando únicamente std.

1. El problema: cache thrashing en el bucle clásico i → j → k

En una multiplicación de matrices C = A × B de tamaño 1024 × 1024 en f32 (4,00 MB por matriz), el bucle clásico i → j → k recorre la matriz B por columnas (B[k * N + j]). En memoria contigua row-major, cada paso en k salta 4.096 bytes.

Como una línea de caché en x86_64 mide 64 bytes (16 floats), solo se aprovecha 1 float de cada 16 traídos desde RAM y el 93,75 % de la línea se desperdicia antes de ser desalojada de L1. Con el mismo lenguaje y las mismas operaciones aritméticas, la implementación naive se queda en 0,63 GFLOPS (3.382,31 ms).

2. Reordenación i → k → j y acceso stride-1

Al invertir los bucles internos a i → k → j, fijamos un escalar a_val = a[i, k] y barremos de forma contigua la fila k de B junto con la fila i de C. Ese patrón secuencial desbloquea el hardware prefetcher y permite que LLVM vectorice el bucle con instrucciones FMA (vfmadd231ps) en AVX2:

// src/matmul.rs — tiny-tensor-engine
for i in 0..m {
    let c_row = &mut c.data[i * n..(i + 1) * n];
    let a_row = &a.data[i * k_dim..(i + 1) * k_dim];

    for (k, &a_val) in a_row.iter().enumerate() {
        let b_row = &b.data[k * n..(k + 1) * n];
        for (c_val, &b_val) in c_row.iter_mut().zip(b_row.iter()) {
            *c_val += a_val * b_val;
        }
    }
}

3. Paralelismo sin locks con std::thread::scope

Para escalar a los 16 hilos de CPU sin dependencias como rayon ni mutexes, particionamos las filas de salida de C mediante chunks_mut dentro de std::thread::scope. El borrow checker demuestra en tiempo de compilación que cada hilo escribe en regiones disjuntas de memoria.

// src/matmul.rs — partición segura sin locks ni data races
std::thread::scope(|s| {
    for (chunk_idx, c_chunk) in c.data.chunks_mut(elements_per_chunk).enumerate() {
        let row_start = chunk_idx * rows_per_thread;
        let chunk_rows = c_chunk.len() / n;
        let a_slice = &a.data[row_start * k_dim..(row_start + chunk_rows) * k_dim];
        let b_ref = &b.data;

        s.spawn(move || {
            // Cada hilo ejecuta el kernel i -> k -> j sobre su bloque de filas
        });
    }
});

4. Resultados medidos (1024×1024 · 2,15 B FLOPs)

KernelLatenciaGFLOPSError máx.
Pure Python (i→j→k)62,595.64 ms0.03—
Rust Naive (i→j→k)3,382.31 ms0.630.00e0
Rust Cache-Tiled (64×64)134.90 ms15.920.00e0
Rust Cache-Linear (i→k→j)106.25 ms20.210.00e0
Rust Parallel SIMD (16 threads)27.25 ms78.810.00e0

Código completo y tests de equivalencia en github.com/yonillo/tiny-tensor-engine.