Multiplication de masortingce: petite différence de taille de masortingce, grande différence de temps

J’ai un code de multiplication de masortingce qui ressemble à ceci:

for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; 

Ici, la taille de la masortingce est représentée par une dimension . Maintenant, si la taille des masortingces est 2000, il faut 147 secondes pour exécuter ce morceau de code, alors que si la taille des masortingces est 2048, cela prend 447 secondes. Donc, alors que la différence en non. des multiplications est (2048 * 2048 * 2048) / (2000 * 2000 * 2000) = 1,073, la différence dans les timings est 447/147 = 3. Quelqu’un peut-il expliquer pourquoi cela se produit? Je m’attendais à ce qu’il évolue linéairement, ce qui ne se produit pas. Je n’essaye pas de faire le code de multiplication de masortingce le plus rapide, essayant simplement de comprendre pourquoi cela se produit.

Spécifications: nœud dual core AMD Opteron (2.2GHz), 2G RAM, gcc v 4.5.0

Programme compilé en gcc -O3 simple.c

Je l’ai aussi lancé sur le compilateur icc d’Intel et j’ai vu des résultats similaires.

MODIFIER:

Comme suggéré dans les commentaires / réponses, j’ai exécuté le code avec la dimension = 2060 et cela prend 145 secondes.

Voici le programme complet:

 #include  #include  #include  /* change dimension size as needed */ const int dimension = 2048; struct timeval tv; double timestamp() { double t; gettimeofday(&tv, NULL); t = tv.tv_sec + (tv.tv_usec/1000000.0); return t; } int main(int argc, char *argv[]) { int i, j, k; double *A, *B, *C, start, end; A = (double*)malloc(dimension*dimension*sizeof(double)); B = (double*)malloc(dimension*dimension*sizeof(double)); C = (double*)malloc(dimension*dimension*sizeof(double)); srand(292); for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) { A[dimension*i+j] = (rand()/(RAND_MAX + 1.0)); B[dimension*i+j] = (rand()/(RAND_MAX + 1.0)); C[dimension*i+j] = 0.0; } start = timestamp(); for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; end = timestamp(); printf("\nsecs:%f\n", end-start); free(A); free(B); free(C); return 0; } 

Voici ma supposition sauvage: cache

Il se peut que vous puissiez insérer 2 lignes de 2000 double s dans le cache. Ce qui est légèrement inférieur au cache L1 de 32kb. (tout en laissant place aux autres choses nécessaires)

Mais lorsque vous passez à 2048, il utilise tout le cache (et vous en répandez parce que vous avez besoin d’espace pour d’autres choses)

En supposant que la politique de cache est LRU, le déversement du cache un tout petit peu entraînera le vidage de la ligne entière et son rechargement dans le cache L1.

L’autre possibilité est l’associativité du cache en raison de la puissance de deux. Bien que je pense que ce processeur est associatif L1 à 2 voies, je ne pense pas que cela soit important dans ce cas. (mais je jetterai l’idée là-bas quand même)

Explication possible 2: Le cache de conflit a échoué en raison du super-alignement sur le cache L2.

Votre tableau B est itéré sur la colonne. Donc l’access est limité. Votre taille totale de données est de 2 2k x 2k Ko, soit environ 32 Mo par masortingce. C’est beaucoup plus grand que votre cache L2.

Lorsque les données ne sont pas parfaitement alignées, vous obtiendrez une localisation spatiale correcte sur B. Bien que vous sautiez des lignes et n’utilisiez qu’un élément par cache, la mémoire cache rest dans le cache L2 pour être réutilisée par la prochaine itération de la boucle intermédiaire.

Cependant, lorsque les données sont parfaitement alignées (2048), ces sauts se retrouveront tous sur le même “chemin de cache” et dépasseront de loin votre associativité de cache L2. Par conséquent, les lignes de cache accessibles de B ne restront pas en cache pour la prochaine itération. Au lieu de cela, ils devront être retirés de ram.

Vous obtenez certainement ce que j’appelle une résonance de cache. Ceci est similaire à l’ aliasing , mais pas exactement le même. Laisse-moi expliquer.

Les caches sont des structures de données matérielles qui extraient une partie de l’adresse et l’utilisent comme index dans une table, contrairement à une masortingce logicielle. (En fait, nous les appelons des tableaux dans le matériel.) Le tableau cache contient des lignes de données de cache et des balises – parfois une telle entrée par index dans le tableau (mappé directement), parfois plusieurs (associativité N-way). Une seconde partie de l’adresse est extraite et comparée à l’étiquette stockée dans le tableau. Ensemble, l’index et la balise identifient de manière unique une adresse mémoire de ligne de cache. Enfin, le rest des bits d’adresse identifie les octets de la ligne de cache, ainsi que la taille de l’access.

Habituellement, l’index et l’étiquette sont des champs de bits simples. Donc, une adresse mémoire ressemble à

  ...Tag... | ...Index... | Offset_within_Cache_Line 

(Parfois, l’index et la balise sont des hachages, par exemple quelques XOR d’autres bits dans les bits intermédiaires de l’index. Plus rarement, parfois, l’index, et plus rarement la balise, sont des choses comme prendre l’adresse de ligne de cache modulo a nombre premier.Ces calculs d’index plus compliqués sont des tentatives pour lutter contre le problème de la résonance, que j’explique ici: tous subissent une forme de résonance, mais les schémas les plus simples d’extraction des champs de bits subissent une résonance sur les modèles d’access communs.

Donc, les valeurs typiques … il y a beaucoup de modèles différents de “Opteron Dual Core”, et je ne vois rien ici qui spécifie celui que vous avez. En choisissant l’un au hasard, le manuel le plus récent que je vois sur le site Web d’AMD, le Guide du développeur Bios and Kernel (BKDG) pour la famille AMD 15h Modèles 00h-0Fh , 12 mars 2012.

(Famille 15h = famille Bulldozer, processeur haut de gamme le plus récent – le BKDG mentionne le dual core, bien que je ne connaisse pas le numéro de produit que vous décrivez exactement. Mais de toute façon, la même idée de résonance s’applique à tous les processeurs. c’est juste que les parameters comme la taille du cache et l’associativité peuvent varier un peu.)

De p.33:

Le processeur de la famille AMD 15h contient un cache de données L1 prévu de 16 Ko et 4 voies avec deux ports 128 bits. Il s’agit d’un cache en écriture qui prend en charge jusqu’à deux charges de 128 octets par cycle. Il est divisé en 16 banques de 16 octets de largeur. […] Un seul chargement peut être effectué à partir d’une banque donnée du cache L1 en un seul cycle.

Pour résumer:

  • Ligne de cache de 64 octets => 6 bits de décalage dans la ligne de cache

  • 16KB / 4-way => la résonance est 4KB.

    Ie bit d’adresse 0-5 correspond au décalage de la ligne de cache.

  • Lignes de cache de 16 Ko / 64 Ko => 2 ^ 14/2 ^ 6 = 2 ^ 8 = 256 lignes de cache dans le cache.
    (Correction: j’ai initialement mal calculé ceci en 128. J’ai corrigé toutes les dépendances.)

  • 4 way associative => 256/4 = 64 index dans le tableau de cache. Je (Intel) appelle ces “ensembles”.

    Vous pouvez donc considérer le cache comme un tableau de 32 entrées ou ensembles, chaque entrée contenant 4 lignes de cache et leurs balises. (C’est plus compliqué que ça, mais ça va).

(Soit dit en passant, les termes “set” et “way” ont des définitions différentes .)

  • il y a 6 bits d’index, bits 6-11 dans le schéma le plus simple.

    Cela signifie que toutes les lignes de cache qui ont exactement les mêmes valeurs dans les bits d’index, bits 6 à 11, mapperont au même ensemble du cache.

Regardez maintenant votre programme.

 C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; 

La boucle k est la boucle la plus profonde. Le type de base est double, 8 octets. Si dimension = 2048, soit 2K, alors les éléments successifs de B[dimension*k+j] auxquels la boucle accède seront 2048 * 8 = 16K séparés. Ils vont tous mapper au même ensemble du cache L1 – ils auront tous le même index dans le cache. Ce qui signifie que, au lieu d’avoir 256 lignes de cache disponibles dans le cache, il n’y en aura que 4 – l’associativité à 4 voies du cache.

C’est-à-dire que vous obtiendrez probablement un cache manquant toutes les 4 itérations autour de cette boucle. Pas bon.

(En fait, les choses sont un peu plus compliquées. Mais ce qui précède est une bonne première compréhension. L’adresse des entrées de B mentionnées ci-dessus est une adresse virtuelle. Il peut donc y avoir des adresses physiques légèrement différentes. probablement en utilisant des bits d’adresses virtuels pour ne pas avoir à attendre une traduction d’adresse virtuelle en physique, mais dans tous les cas: votre code a une “résonance” de 16 Ko. Le cache de données L1 a une résonance de 16 Ko. .)]

Si vous modifiez un peu la dimension, par exemple en 2048 + 1, les adresses du tableau B seront réparties sur tous les ensembles du cache. Et vous obtiendrez beaucoup moins de caches de cache.

Il est assez courant d’optimiser vos baies, par exemple pour modifier 2048 à 2049, afin d’éviter cette résonance. Mais “le blocage du cache est une optimisation encore plus importante. http://suif.stanford.edu/papers/lam-asplos91.pdf


En plus de la résonance de la ligne de cache, d’autres choses se passent ici. Par exemple, le cache L1 a 16 banques, chacune large de 16 octets. Avec dimension = 2048, les access B successifs dans la boucle interne iront toujours à la même banque. Donc, ils ne peuvent pas aller en parallèle – et si l’access A arrive à se rendre à la même banque, vous perdrez.

Je ne pense pas, en le regardant, que cela soit aussi important que la résonance du cache.

Et, oui, peut-être, il peut y avoir des aliasing. Par exemple, le STLF (Store To Load Forwarding) peut comparer uniquement un petit champ de bits et obtenir de fausses correspondances.

(En fait, si vous y réfléchissez, la résonance dans le cache est comme un aliasing, lié à l’utilisation de champs de bits. La résonance est causée par plusieurs lignes de cache mappant le même ensemble sans être réparties. morceaux.)


Dans l’ensemble, ma recommandation pour le réglage:

  1. Essayez le blocage du cache sans aucune parsing supplémentaire. Je dis cela parce que le blocage du cache est facile, et il est très probable que c’est tout ce que vous devez faire.

  2. Après cela, utilisez VTune ou OProf. Ou Cachegrind. Ou …

  3. Mieux encore, utilisez une routine de bibliothèque bien réglée pour multiplier les masortingces.

Il y a plusieurs explications possibles. Une explication probable est ce que Mysticial suggère: épuisement d’une ressource limitée (cache ou TLB). Une autre possibilité est un faux décrochage, qui peut se produire lorsque les access consécutifs à la mémoire sont séparés par un multiple de puissance de deux (souvent 4 Ko).

Vous pouvez commencer à affiner votre travail en traçant le temps / la dimension ^ 3 pour une plage de valeurs. Si vous avez fait sauter une cache ou épuisé la scope du TLB, vous verrez une section plus ou moins plate suivie d’une forte hausse entre 2000 et 2048, suivie d’une autre section plate. Si vous voyez des stands liés à l’aliasing, vous verrez un graphique plus ou moins plat avec un pic étroit vers le haut à 2048.

Bien sûr, cela a un pouvoir diagnostique, mais ce n’est pas concluant. Si vous voulez savoir avec certitude quelle est la source du ralentissement, vous voudrez en savoir plus sur les compteurs de performance , qui peuvent répondre définitivement à ce type de question.

Je sais que c’est trop vieux, mais je vais mordre. C’est (comme on l’a dit) un problème de cache ce qui provoque le ralentissement autour de deux puissances. Mais il y a un autre problème avec ça: c’est trop lent. Si vous regardez votre boucle de calcul.

 for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; 

La boucle la plus intérieure change de 1 à chaque itération, ce qui signifie que vous n’accédez qu’à un double du dernier élément que vous avez utilisé pour A, mais à une dimension entière qui s’éloigne du dernier élément de B. la mise en cache des éléments de B.

Si vous changez cela en:

 for(i = 0; i < dimension; i++) for(j = 0; j < dimension; j++) for(k = 0; k < dimension; k++) C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k]; 

Vous obtenez exactement les mêmes résultats (erreurs d'associativité modulo double addition), mais il est beaucoup plus convivial ( local ). Je l'ai essayé et cela apporte des améliorations substantielles. Cela peut être résumé comme

Ne pas multiplier les masortingces par définition, mais plutôt par lignes


Exemple d'accélération (j'ai changé votre code pour prendre la dimension en argument)

 $ diff ac bc 42c42 < C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j]; --- > C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k]; $ make a cc ac -oa $ make b cc bc -ob $ ./a 1024 secs:88.732918 $ ./b 1024 secs:12.116630 

En bonus (et ce qui fait que ceci est lié à cette question), c'est que cette boucle ne souffre pas du problème précédent.

Si vous saviez déjà tout cela, alors je m'excuse!

Quelques réponses mentionnent des problèmes de cache L2.

Vous pouvez réellement vérifier cela avec une simulation de cache. L’outil cachegrind de Valgrind peut faire cela.

 valgrind --tool=cachegrind --cache-sim=yes your_executable 

Définissez les parameters de la ligne de commande pour qu’ils correspondent aux parameters L2 de votre CPU.

Testez-le avec différentes tailles de masortingce, vous verrez probablement une augmentation soudaine du taux de raté L2.