Quelle combinaison de cause et de remède typique est correcte pour expliquer les nombreux défauts de cache lors de la transposition d’une grande matrice (b[j][i] = a[i][j]) ?

Réponse : C. Cause : la lecture ou l’écriture se fait par colonne ; remède : la transposition par blocs

Dans une transposition, lire a par ligne revient à écrire b par colonne, et écrire b par ligne revient à lire a par colonne ; l’un des deux accès est forcément dispersé. On découpe donc la matrice en petits blocs tenant dans le cache et on transpose à l’intérieur de chaque bloc : les lignes chargées sont entièrement utilisées avant de passer à la suite, et les défauts diminuent fortement. Rendre contiguës uniquement les écritures ne fait que disperser les lectures, sans résoudre le fond du problème. Il ne s’agit pas non plus d’une question de quantité de calcul.