Pourquoi la transposition d'une matrice 512x512 est-elle significativement plus lente que la transposition d'une matrice 513x513 ?

Pourquoi la transposition de matrices 512x512 est plus lente que la transposition de 513x513

Une observation particulière dans la transposition de matrices est apparue après avoir mené des expériences sur des matrices de différentes tailles : transposer une matrice de dimensions 2^ n est plus coûteux en termes de calcul que d'en transposer un de dimensions 2 ^ n 1. Le l'écart devient significatif lorsque n est égal à 512.

Le code fourni pour l'opération de transposition est le suivant :

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

En altérant la macro MATSIZE, la taille de la matrice peut être modifiée. Les références suivantes illustrent la différence marquée :

• Taille 512 : moyenne 2,46 ms
• Taille 513 : moyenne 0,75 ms

Contention de cache et foulée critique

La raison de cette anomalie réside dans le comportement du cache et la notion de cache contestation. En voici une répartition :

• Un cache est structuré en ensembles et en lignes. À un moment donné, un seul ensemble est accessible et n'importe quelle ligne de cet ensemble peut être utilisée. La taille totale du cache est déterminée par le nombre de lignes multiplié par la taille de chaque ligne.
• Pour calculer l'ensemble auquel appartient une adresse mémoire particulière, la formule suivante est utilisée : set = (adresse / lineSize ) % numberOfsets.
• Lorsque plusieurs adresses mémoire accèdent au même ensemble, des conflits de cache surviennent. Dans de tels scénarios, la ligne la moins récemment utilisée de l'ensemble est écrasée par les données nouvellement récupérées.
• La foulée critique, qui représente le nombre d'accès à la mémoire entraînant un conflit de cache, est calculée comme suit : criticStride = numberOfSets * lineSize.
• Dans le cas d'une matrice 64x64 avec un cache de 8 Ko, la foulée critique s'alignerait parfaitement avec les lignes de la matrice, menant à des rechargements excessifs du cache lors de la transposition.
• Cependant, lorsque la taille de la matrice est augmentée à 65x65, la foulée critique n'est plus parfaitement alignée, ce qui réduit la fréquence des conflits de cache et améliore les performances.

Ainsi, l'opération de transposition devient considérablement plus lente pour les matrices dont les dimensions sont des multiples de 2^n en raison de conflits de cache.

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!