Quedas repentinas no desempenho de multiplicação de matrizes

Eu tenho lido sobre a implementação de multiplicação densa de matrizes quando a matriz não se encaixa no cache. Um dos gráficos que eu vi (slide 9 desses slides ) mostra quedas repentinas no desempenho usando o algoritmo ingênuo. Essas quedas atingem cerca de 50% da velocidade, ocorrem enquanto a matriz ainda se encaixa no cache e ocorrem apenas para um ou dois tamanhos. Não estou pensando em usar o algoritmo ingênuo, mas gostaria de saber de onde vêm as quedas repentinas no desempenho. (As descargas também ocorrem com algoritmos bloqueados, mas são muito menores.)

Esse é um exemplo clássico de associatividade de cache. O ritmo associado a esse tamanho de problema está preenchendo determinados conjuntos, causando a remoção de cache, apesar de haver muito espaço em outros conjuntos.

Figura do excelente post de Gustavo Duarte sobre o tema

Veja também Drepper's O que todo programador deve saber sobre memória .