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

127

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;
   }
 }
Loup
la source
23
Ce serait une excellente question d'examen pour une programmation de niveau avancé C ou une classe de conception d'OS ;-)
Dana the Sane
Avez-vous essayé de tester des tableaux multidimensionnels [,] et dentelés [] [] ainsi que des tableaux 32 et 64 bits? Je n'ai testé que quelques fois mais dentelé semblait plus conforme à vos résultats, mais le 64 bits dentelé était élevé, je ne sais pas s'il y a des heuristiques dans le jit qui s'appliquent à cette situation ou si son cache est lié comme suggéré précédemment. Si vous voulez une solution GPGPU, il y a research.microsoft.com/en-us/projects/accelerator qui devrait être compétitif avec les temps de votre autre article.
Kris
Question un peu naïve, mais combien d'opérations (addition / multiplication) sont impliquées dans la multiplication de deux matrices carrées?
Nick T

Réponses:

61

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.

zviadm
la source
Avez-vous fait une erreur dans vos 2 derniers paragraphes? Les deux essais sont exactement les mêmes. :)
Xeo
L'associativité du cache joue également un rôle.
Ben Jackson
20

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.

Jonathan Moore
la source
+1. Cela semble probable. Il faut faire attention à l'associativité du cache.
Macke
16

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.

Dana le Sane
la source
2
mais il est très peu probable qu'il dispose de 16,7 Mo de mémoire cache CPU
Marino Šimić
J'ai mis à jour les résultats avec 2049x2049 - 91 secondes. S'il s'agissait d'un "problème de cache", cela ne devrait-il pas être encore plus de 300 s?
Loup
@Marino la réponse a été mise à jour pour en tenir compte.
Dana the Sane
1
Je pense qu'aucune de ces explications ne peut aborder de manière adéquate les nouveaux détails concernant les différentes tailles clairsemées qui soulèvent le problème, les autres n'étant pas affectées.
Ken Rockot
2
Je ne pense pas que cette explication soit correcte. Le problème réside dans le fait de ne pas utiliser pleinement la capacité du cache en raison des conflits de ligne de cache lorsque la taille est égale à 2. De plus, le système d'exploitation n'a vraiment rien à voir avec les caches, car ce n'est pas le système d'exploitation qui décide quoi mettre en cache et quoi expulser, c'est tout dans le matériel. OS a quelque chose à voir avec l'alignement des données, mais dans ce cas, tout dépend de la façon dont C # décide d'allouer les données et de la représentation du tableau 2D en mémoire, OS n'a rien à voir avec cela.
zviadm
5

É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 .


la source
La section 5 du lien sur l'associativité du cache semble s'appliquer en particulier.
Dana the Sane
4

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.

Guffa
la source
Cela n'explique pas pourquoi 2049 est plus rapide que 2048.
Macke
@Macke: C'est parce qu'il dépasse une certaine limite dans la mise en cache de la mémoire, de sorte qu'il y a beaucoup plus d'erreurs de cache.
Guffa
Pourquoi le vote négatif? Si vous ne dites pas ce que vous pensez être faux, cela ne peut pas améliorer la réponse.
Guffa
Un autre vote négatif sans aucune explication ... Est-ce que ma réponse contient trop peu de "probablement", de "deviner" et de "devrait", comme les réponses qui obtiennent le plus de votes positifs ...?
Guffa
4

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.

DigitalRoss
la source
2

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.

David Heffernan
la source
1
Je connais BLAS, mais la tâche n'était pas de le rendre le plus rapide possible, mais de l'écrire et de le tester dans différentes langues. C'est un problème très étrange pour moi et je suis vraiment curieux de savoir pourquoi les résultats sont comme ils sont.
Loup
3
@Wolf J'aurais du mal à m'exciter à savoir si quelque chose qui devrait prendre une seconde prend 90 ou 300 secondes.
David Heffernan
4
La meilleure façon d'apprendre comment quelque chose fonctionne est de l'écrire vous-même et de voir comment vous pouvez améliorer votre implémentation; c'est (espérons-le) ce que fait Wolf.
Callum Rogers
@Callum Rogers, d'accord. C'est ainsi que j'ai appris l'importance de la taille des tampons dans les opérations de copie de fichiers.
Kelly
1

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.

Arlen
la source
Hmm - pourtant un tableau déclaré en 2D (float [,] matice = new float [rozmer, rozmer];) n'est toujours alloué dans la RAM que sous forme de tableau unidimensionnel et de calculs de ligne / foulée effectués sous le capot. Alors, pourquoi le déclarer comme 1D et faire des calculs manuels de ligne / foulée serait-il plus rapide? Voulez-vous dire que sol'n alloue un grand tableau sous forme de tableau de carreaux plus petits dont chacun peut tenir dans le cache alors que le grand tableau ne le ferait pas?
Eric M
1
Si votre bibliothèque ou tout autre outil que vous utilisez fait de la mosaïque, vous n'en avez pas besoin. Mais si vous utilisiez un tableau 2D traditionnel dans, par exemple, C / C ++, la mosaïque améliorerait les performances.
Arlen
0

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.

Automatico
la source
1
Incorrect. 2049 est plus rapide que 2048, ce qui réfute votre affirmation.
Macke
@Macke: C'est tout à fait possible. Mais il y a une légère chance que la politique de cache utilisée dans son processeur puisse encore faire cette description. Ce n'est pas très probable, mais ce n'est pas impensable.
Automatico