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)
| Kernel | Latencia | GFLOPS | Error máx. |
|---|---|---|---|
| Pure Python (i→j→k) | 62,595.64 ms | 0.03 | — |
| Rust Naive (i→j→k) | 3,382.31 ms | 0.63 | 0.00e0 |
| Rust Cache-Tiled (64×64) | 134.90 ms | 15.92 | 0.00e0 |
| Rust Cache-Linear (i→k→j) | 106.25 ms | 20.21 | 0.00e0 |
| Rust Parallel SIMD (16 threads) | 27.25 ms | 78.81 | 0.00e0 |
Código completo y tests de equivalencia en github.com/yonillo/tiny-tensor-engine.