Pourquoi les transpositions matricielles 513x513 sont-elles plus rapides que les transpositions matricielles 512x512 ?

Comprendre les différences de performances dans la transposition matricielle pour des tailles de matrice de 512x512 et 513x513

Les matrices carrées de différentes tailles présentent des différences temporelles uniques en ce qui concerne en les transposant. Il est intéressant de noter que les matrices de dimensions 2 ^ n ont tendance à avoir des temps de transposition plus lents que celles de dimensions 2 ^ n 1. Bien que ces différences puissent sembler insignifiantes pour de petites valeurs de n, elles deviennent significatives pour des dimensions plus grandes, comme en témoigne MATSIZE 512. .

Pour comprendre la raison sous-jacente de cette disparité de performances, nous approfondissons le concept de mise en cache.

Organisation du cache et mappage des ensembles

Les caches sont organisés en ensembles et en lignes. Chaque ensemble contient plusieurs lignes pouvant stocker des données. Pour localiser l'ensemble auquel appartient une adresse mémoire particulière, nous utilisons la formule suivante :

set = (address / lineSize) % numberOfsets

En conséquence, les adresses mémoire correspondent aux ensembles de manière quelque peu uniforme.

Manques de cache et expulsions de lignes

Lors de l'accès à un emplacement mémoire, le cache vérifie si les données sont déjà présentes. Dans le cas contraire, un échec de cache se produit et la ligne correspondante est lue dans la mémoire et placée dans le cache. Cependant, lorsque le cache est plein, il supprime la ligne LRU (Least Récemment Utilisé) pour accueillir les nouvelles données.

foulée critique

La foulée critique représente l'espacement entre des variables qui se disputent les mêmes lignes de cache. Il est calculé comme suit :

criticalStride = numberOfSets * lineSize

Les variables espacées par la foulée critique ou ses multiples sont plus susceptibles de provoquer des expulsions de cache.

Transposition matricielle et foulée critique

Imaginez une matrice 64x64 avec un cache de 8 Ko et quatre lignes par ensemble. Chaque ligne peut contenir huit entiers de 64 bits. La foulée critique dans ce scénario est de 2048 octets, soit l'équivalent de quatre lignes de la matrice.

Lors de la transposition de la matrice, nous échangeons les lignes et les colonnes. Au fur et à mesure que nous traitons chaque ligne et l'échangeons avec sa colonne correspondante, les éléments séparés par la foulée critique (quatre lignes) rencontrent des expulsions de cache. Il en résulte un nombre important de rechargements de cache, entraînant une transposition plus lente.

Conclusion

La disparité des temps de transposition entre les matrices 512x512 et 513x513 provient de la relation entre les dimensions de la matrice et étape critique du cache. Les matrices dont les dimensions ne sont pas des multiples de la foulée critique réduisent les expulsions de cache et, par conséquent, des temps de transposition plus rapides.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!