Pourquoi la multiplication des baies 2048x2048 par rapport à 2047x2047 a-t-elle un impact énorme sur les performances?

Je fais des comparaisons de multiplication matricielle, comme mentionné précédemment dans Pourquoi MATLAB est-il si rapide en multiplication matricielle?

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'essaye de ne multiplier que les matrices 2047x2047, cela semble normal. Ajout de quelques autres pour la comparaison aussi.

1024x1024 - 10 secondes.

1027x1027 - 10 secondes.

2047x2047 - 90 secondes.

2048x2048 - 300 secondes.

2049x2049 - 91 secondes. (mettre à jour)

2500x2500 - 166 secondes

C'est une différence de trois minutes et demie pour le cas 2k par 2k.

en utilisant des 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;
   }
 }

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

Les erreurs de cache sur matice1 ne sont pas le problème car elles sont accessibles de manière séquentielle. Cependant pour matice2 si une colonne complète tient dans L2 (c'est-à-dire lorsque vous accédez à matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... etc, rien n'est expulsé) alors il n'y a pas de problème avec le cache manque non plus avec matice2.

Maintenant, pour aller plus loin dans le fonctionnement des caches, si l'adresse d'octet de votre variable est X, que la ligne de cache serait (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 six vient du fait que 2 ^ 6 == 64 octets est la taille standard de la ligne de cache.

Maintenant 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), ils seront stockés dans la même ligne de cache.

Maintenant, pour 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 de flotteur). Donc une grande puissance de 2.

Ainsi, en fonction de la taille de votre L2, vous aurez beaucoup de conflits de ligne de cache et n'utiliserez qu'une petite partie de votre L2 pour stocker une colonne, vous ne pourrez donc pas réellement stocker la colonne complète dans votre cache, vous obtiendrez ainsi 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, vous aurez donc moins de conflits et votre colonne s'intégrera en toute sécurité dans votre cache.

Maintenant, pour tester cette théorie, vous pouvez faire deux choses:

Allouez votre matrice matrice2 comme celle-ci matice2 [razmor, 4096], et exécutez-la avec razmor = 1024, 1025 ou n'importe quelle taille, et vous devriez voir de très mauvaises performances par rapport à ce que vous aviez auparavant. En effet, vous alignez de force toutes les colonnes pour qu'elles soient en conflit les unes avec les autres.

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

Probablement un effet de cache. Avec des dimensions de matrice qui sont de grandes puissances de deux et une taille de cache qui est également 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 de matrice naïve est généralement limitée par la nécessité de récupérer des données dans le cache. Les algorithmes optimisés utilisant la mosaïque (ou des algorithmes ignorant le 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 de l'autre de 2048 * sizeof (float) et ainsi mapper 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 tous. Ainsi, presque tous ces accès déclencheront une éviction du cache L1 et une récupération des données à partir d'un cache plus lent ou de la mémoire principale.

Cela peut avoir à voir avec la taille de votre cache cpu. Si 2 lignes de la matrice matricielle ne correspondent pas, vous perdrez du temps à permuter les éléments de la RAM. Les 4095 éléments supplémentaires peuvent suffire à empêcher les rangées de s'ajuster.

Dans votre cas, 2 lignes pour 2047 matrices 2D se situent dans 16 Ko de mémoire (en supposant des types de 32 bits). Par exemple, si vous avez un cache L1 (le plus proche du processeur sur le bus) de 64 Ko, vous pouvez insérer au moins 4 lignes (de 2047 * 32) dans le cache à la fois. Avec les lignes plus longues, s'il y a un remplissage requis qui pousse les paires de lignes au-delà de 16 Ko, les choses commencent à devenir compliquées. De plus, chaque fois que vous «manquez» le cache, l'échange de données d'un autre cache ou de la mémoire principale retarde les choses.

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

Louis Brandy a écrit deux articles de blog analysant exactement ce problème:

Plus de folie du cache et de performances de calcul - Une étude de cas pour débutants avec des statistiques intéressantes et des tentatives pour expliquer le comportement plus en détail, cela se résume en effet aux limitations de la taille du cache.

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

Au fur et à mesure que vous accédez au matice2tableau verticalement, il sera beaucoup plus échangé dans le cache. Si vous mettez en miroir le tableau en diagonale, afin de pouvoir y accéder à la [k,m]place de [m,k], le code s'exécutera beaucoup plus rapidement.

J'ai testé cela pour des matrices 1024x1024, et c'est environ deux fois plus rapide. Pour les matrices 2048x2048, c'est environ dix fois plus rapide.

Alias ​​de cache

Ou du cache-cache , si je peux inventer un terme.

Les caches fonctionnent en indexant avec des bits de poids faible et en marquant avec des bits de poids fort.

Imagerie que votre cache a 4 mots et que votre matrice est 4 x 4. Lorsqu'une colonne est accédée et que la ligne a une puissance de deux, alors chaque élément de colonne en mémoire sera mappé au même élément de cache.

Une puissance de deux plus un est en fait à peu près optimale pour ce problème. Chaque nouvel élément de colonne sera mappé au prochain emplacement de cache exactement comme s'il accédait par ligne.

Dans la vraie vie, une balise couvre plusieurs adresses croissantes séquentiellement qui mettront en cache plusieurs éléments adjacents dans une rangée. En décalant le compartiment auquel chaque nouvelle ligne mappe, la traversée de la colonne ne remplace pas l'entrée précédente. Lorsque la colonne suivante est parcourue, tout le cache sera rempli de différentes lignes et chaque section de ligne qui rentre dans le cache sera affectée pendant plusieurs colonnes.

Étant donné que le cache est beaucoup plus rapide que la DRAM (principalement en raison du fait qu'il est sur puce), le taux de réussite est tout.

Vous semblez avoir atteint une limite de taille de cache, ou peut-être avoir des problèmes de répétabilité dans vos horaires.

Quel que soit le problème, vous ne devez tout simplement pas écrire vous-même la multiplication matricielle en C # et utiliser à la place une version optimisée du BLAS. Cette taille de matrice devrait être multipliée en moins d'une seconde sur n'importe quelle machine moderne.

L'utilisation efficace de la hiérarchie du cache est très importante. Vous devez vous assurer que les tableaux multidimensionnels ont des données dans un bon agencement, ce qui peut être accompli en mosaïque . Pour ce faire, vous devrez stocker le tableau 2D en tant que tableau 1D avec un mécanisme d'indexation. Le problème avec la méthode traditionnelle est que, bien que deux éléments de tableau adjacents qui sont dans la même ligne soient côte à côte en mémoire, deux éléments adjacents dans la même colonne seront séparés par W éléments en mémoire, où W est le nombre de colonnes . Le carrelage peut faire une différence de performance d'un facteur de dix.

Je soupçonne que c'est le résultat de quelque chose appelé « inondation séquentielle ». Ce que c'est que vous essayez de parcourir la liste des objets qui est légèrement plus grande que la taille du cache, donc chaque requête à une liste (tableau) doit être effectuée à partir de la RAM, et vous n'obtiendrez pas un seul cache frappé.

Dans votre cas, vous faites une boucle dans vos tableaux 2048 index 2048 fois, mais vous n'avez de l'espace que pour 2047 (peut-être en raison d'une surcharge de la structure du tableau), donc chaque fois que vous accédez à un tableau pos, il doit obtenir ce tableau pos de bélier. Il est ensuite stocké dans le cache, mais juste avant d'être réutilisé, il est vidé. Le cache est donc essentiellement inutile, ce qui entraîne un temps d'exécution beaucoup plus long.