Caídas repentinas en el rendimiento de la multiplicación de matrices

He estado leyendo sobre la implementación de la multiplicación de matriz densa cuando la matriz no cabe en el caché. Uno de los gráficos que he visto (diapositiva 9 de estas diapositivas ) muestra caídas repentinas en el rendimiento utilizando el algoritmo ingenuo. Estas caídas son de alrededor del 50% de la velocidad, ocurren mientras la matriz todavía cabe en la memoria caché y solo ocurren para uno o dos tamaños. No planeo usar el algoritmo ingenuo, pero me gustaría saber de dónde provienen las caídas repentinas en el rendimiento. (Las caídas también ocurren con algoritmos bloqueados, pero son mucho más pequeños).

Ese es un ejemplo clásico de asociatividad de caché. La zancada asociada con ese tamaño del problema está llenando ciertos conjuntos que causan el desalojo de caché a pesar de que hay mucho espacio en otros conjuntos.

Figura de la excelente publicación de blog de Gustavo Duarte sobre el tema

Vea también Drepper's Lo que todo programador debe saber sobre la memoria .