Pourquoi la multiplication de tableaux en 2048x2048 contre 2047x2047 a-t-elle un impact considérable sur les performances ?

Question

Je suis en train de faire un benchmarking de la multiplication de matrices, comme mentionné précédemment dans Pourquoi MATLAB est-il si rapide dans la multiplication de matrices ?

Maintenant j'ai un autre problème, lors de la multiplication de deux matrices 2048x2048, il y a une grande différence entre C# et les autres. Lorsque j'essaie de multiplier uniquement des matrices 2047x2047, cela semble normal. J'ai ajouté quelques autres matrices pour comparaison.

1024x1024 - 10 secondes.

1027x1027 - 10 secondes.

2047x2047 - 90 secondes.

2048x2048 - 300 secondes.

2049x2049 - 91 secondes. (mise à jour)

2500x2500 - 166 secondes

Cela représente une différence de trois minutes et demie pour le cas de 2k par 2k.

Utilisation de tableaux 2dim

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

Answer 1

Cela a probablement à voir avec des conflits dans votre cache L2.

Les ratés du cache sur matice1 ne sont pas le problème car ils sont accédés séquentiellement. Cependant, pour matice2, si une colonne complète tient dans L2 (c'est-à-dire que lorsque vous accédez à matice2[0, 0], matice2[1, 0], matice2[2, 0] ... etc, rien n'est évincé), il n'y a pas de problème d'absence de cache avec matice2 non plus.

Maintenant, pour aller plus loin dans le fonctionnement des caches, si l'adresse d'octet de votre variable est X, alors la ligne de cache pour celle-ci sera (X >> 6) & (L - 1). Où L est le nombre total de lignes de cache dans votre cache. L est toujours une puissance de 2. Le 6 vient du fait que 2^6 == 64 octets est la taille standard d'une ligne de cache.

Qu'est-ce que cela signifie ? Eh bien cela signifie que si j'ai l'adresse X et l'adresse Y et que (X >> 6) - (Y >> 6) est divisible par L (c'est-à-dire une grande puissance de 2), elles seront stockées dans la même ligne de cache.

Pour en revenir à votre problème, quelle est la différence entre 2048 et 2049 ?

quand 2048 est votre taille :

Si vous prenez &matice2[x, k] et &matice2[y, k] la différence (&matice2[x, k] >> 6) - (&matice2[y,k] >> 6) sera divisible par 2048 * 4 (taille du float). Donc une grande puissance de 2.

Ainsi, en fonction de la taille de votre L2, vous aurez beaucoup de conflits de lignes de cache, et n'utiliserez qu'une petite partie de votre L2 pour stocker une colonne, donc vous ne serez pas en mesure de stocker la colonne complète dans votre cache, donc vous obtiendrez de mauvaises performances.

Lorsque la taille est de 2049, la différence est de 2049 * 4, ce qui n'est pas une puissance de 2. Ainsi, vous aurez moins de conflits et votre colonne tiendra en toute sécurité dans votre cache.

Pour tester cette théorie, il y a deux choses que vous pouvez faire :

Allouez votre tableau matice2 comme ceci matice2 [razmor, 4096], et exécutez avec razmor = 1024, 1025 ou n'importe quelle taille, et vous devriez voir de très mauvaises performances par rapport à ce que vous aviez avant. Ceci est dû au fait que vous avez aligné de force toutes les colonnes pour qu'elles entrent en conflit les unes avec les autres.

Essayez ensuite matice2 [razmor, 4097] et exécutez-le avec n'importe quelle taille et vous devriez voir de bien meilleures performances.

Answer 2

Probablement un effet de mise en cache. Avec des dimensions de matrice qui sont de grandes puissances de deux, et une taille de cache qui est aussi une puissance de deux, vous pouvez finir par n'utiliser qu'une petite fraction de votre cache L1, ce qui ralentit beaucoup les choses. La multiplication matricielle naïve est généralement limitée par la nécessité d'aller chercher les données dans le cache. Les algorithmes optimisés utilisant le tuilage (ou algorithmes oblivres au cache) se concentrent sur une meilleure utilisation du cache L1.

Si vous chronométrez d'autres paires (2^n-1,2^n), je pense que vous verrez des effets similaires.

Pour expliquer plus en détail, dans la boucle interne, où vous accédez à matice2[m,k], il est probable que matice2[m,k] et matice2[m+1,k] soient décalés l'un par rapport à l'autre de 2048*sizeof(float) et correspondent donc au même index dans le cache L1. Avec un cache associatif à N voies, vous aurez généralement 1 à 8 emplacements de cache pour chacun d'entre eux. Ainsi, presque tous ces accès déclencheront une éviction du cache L1 et la récupération de données dans un cache plus lent ou dans la mémoire principale.

Answer 3

Cela peut avoir un rapport avec la taille du cache de votre processeur. Si 2 lignes de la matrice ne rentrent pas, vous perdrez du temps à échanger des éléments depuis la RAM. Les 4095 éléments supplémentaires peuvent être juste suffisants pour empêcher les rangées de s'adapter.

Dans votre cas, 2 lignes pour 2047 matrices 2d tombent dans les 16KB de mémoire (en supposant des types 32 bits). Par exemple, si vous avez un cache L1 (le plus proche du processeur sur le bus) de 64 Ko, vous pouvez placer au moins 4 lignes (de 2047 * 32) dans le cache en une seule fois. Avec les rangées plus longues, s'il y a un remplissage nécessaire qui pousse les paires de rangées au-delà de 16KB, alors les choses commencent à se gâter. De plus, à chaque fois que le cache n'est pas utilisé, l'échange de données à partir d'un autre cache ou de la mémoire principale retarde les choses.

Je pense que la variation des temps d'exécution que vous observez avec les matrices de différentes tailles est affectée par l'efficacité avec laquelle le système d'exploitation peut utiliser le cache disponible (et certaines combinaisons sont tout simplement problématiques). Bien sûr, il s'agit d'une simplification grossière de ma part.

Answer 4

Louis Brandy a écrit deux billets de blog analysant exactement cette question :

Plus de folie de cache y Performances de calcul - Une étude de cas de débutants avec des statistiques intéressantes et des tentatives d'expliquer le comportement plus en détail, il s'agit bien de limitations de la taille du cache.

Answer 5

Étant donné que le temps diminue pour les grandes tailles, ne serait-il pas plus probable qu'il s'agisse de conflits de cache, surtout avec des puissances de 2 pour les tailles de matrice problématiques ? Je ne suis pas un expert en matière de cache, mais d'excellentes informations sur les problèmes de performances liés au cache. aquí .