Multiplication matricielle: petite différence dans la taille de la matrice, grande différence dans les synchronisations

Question

J'ai une matrice de multiplier code 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 matrice est représentée par dimension. Maintenant, si la taille de la matrice est de 2000, il prend 147 secondes pour exécuter ce morceau de code, alors que si la taille de la matrice est de 2048, il faut 447 secondes. Ainsi, alors que la différence de pas de. de multiplications est (2048*2048*2048)/(2000*2000*2000) = 1.073, la différence dans le timing est 447/147 = 3. Quelqu'un peut m'expliquer pourquoi cela se produit? Je m'attendais à l'échelle linéaire, ce qui n'arrive pas. Je ne cherche pas à faire de la manière la plus rapide de la matrice de multiplier code, il suffit d'essayer de comprendre pourquoi cela arrive.

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

Programme compilé en gcc -O3 simple.c

J'ai l'exécuter sur Intel compilateur icc ainsi, et obtenu des résultats similaires.

EDIT:

Comme suggéré dans les commentaires/réponses, j'ai couru le code avec la dimension=2060, et il prend 145 secondes.

Voici le programme complet:

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

/* 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;
}

Answer 1

Voici mon sauvage deviner: cache

Il pourrait être que vous pouvez mettre 2 rangées de 2000 doubles dans le cache. Ce qui est légèrement moins que les 32 ko de cache L1. (tout en laissant la place à d'autres choses nécessaires)

Mais quand vous l'augmenter jusqu'à 2048, il utilise la totalité de la mémoire cache (et vous déversement de certains parce que vous avez besoin de place pour d'autres choses)

En supposant que la politique de cache est LRU, répandre le cache juste un tout petit peu pour cause l'ensemble de la ligne à plusieurs reprises vidé et rechargé dans le cache L1.

L'autre possibilité est l'associativité du cache en raison de la puissance de deux. Même si je pense que le processeur est à 2 voies L1 associatif, donc je ne pense pas que c'est important dans ce cas. (mais je vais lancer l'idée là de toute façon)

Explication 2: Conflit cache en raison de super-alignement sur le cache L2.

Votre B tableau est indiqué à la colonne. L'accès est strided. Votre total de la taille des données est - 2k x 2k , qui est d'environ 32 MO pour la matrice. Qui est beaucoup plus grande que celle de votre cache L2.

Lorsque les données ne sont pas parfaitement alignés, vous aurez décent spatiale de la localité sur B. si vous êtes à sauts de lignes, et en utilisant uniquement un élément par cacheline, le cacheline reste dans le cache L2 être réutilisés par la prochaine itération de la milieu de la boucle.

Toutefois, lorsque les données sont parfaitement alignés (2048), ces houblon sera de toutes les terres de la même "cache" et dépassera de loin vos cache L2 l'associativité. Par conséquent, l'accès lignes de cache de B ne restera pas dans la mémoire cache pour la prochaine itération. Au lieu de cela, ils auront besoin d'être tiré dans tout le chemin à partir de la ram.

Answer 2

Vous êtes certainement obtenir ce que j'appelle un cache de résonance. Ceci est similaire à l'aliasing, mais pas exactement le même. Laissez-moi vous expliquer.

Les Caches sont de matériel de structures de données qui extrait une partie de l'adresse et de l'utiliser comme un index dans une table, pas contrairement à un tableau dans le logiciel. (En fait, nous les appelons des tableaux dans le matériel.) Le tableau de cache contient des lignes de cache de données, et des étiquettes - parfois, une telle entrée par l'index dans le tableau (direct mapped), parfois plusieurs de ces (N-way set associativité). Une deuxième partie de l'adresse est extrait et par rapport à la balise stockés dans le tableau. Ensemble, l'index et le tag identifier de manière unique une ligne de cache de la mémoire d'adresse. Enfin, le reste des bits de l'adresse permet d'identifier les octets de la ligne de cache sont abordées, ainsi que la taille de l'accès.

Habituellement, l'index et le tag sont simples bitfields. Si une adresse de mémoire ressemble

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

(Parfois, l'index et le tag sont les tables de hachage, par exemple, quelques XORs d'autres bits dans le milieu de gamme, les bits qui sont à l'index. Beaucoup plus rarement, parfois, les index, et plus rarement tag, sont des choses comme la prise en cache de l'adresse de ligne modulo un nombre premier. Ces plus compliqué calculs d'indice sont des tentatives visant à lutter contre le problème de la résonance, qui je l'explique ici. Tous souffrent d'une certaine forme de résonance, mais le plus simple champ de bits systèmes d'extraction souffrent de résonance sur la commune de modèles d'accès, comme vous l'avez trouvé.)

Ainsi, 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 que vous avez. Choisir un au hasard, le plus récent manuel je vois sur le site web d'AMD, le Bios et le Noyau Guide du Développeur (BKDG) pour AMD de la Famille 15h Modèles 00h-0Fh, le 12 Mars 2012.

(Famille 15h = Bulldozer de la famille, le plus récent haut de gamme de processeur - la BKDG mentionne dual core, mais je ne sais pas le numéro du produit, c'est exactement ce que vous décrivez. Mais, de toute façon, la même idée de la résonance s'applique à tous les processeurs, c'est juste que les paramètres tels que la taille de la mémoire cache et l'associativité peut varier un peu.)

À partir de p.33:

L'AMD Famille 15h processeur contient un 16 kilo-octets, 4-way prédit L1 cache de données avec deux de 128 bits ports. C'est un cache à écriture immédiate que prend en charge jusqu'à deux 128 Octets charge par cycle. Il est divisé en 16 les banques, chaque 16 octets. [...] Une seule charge peut être effectuée à partir d'un compte tenu de la banque de la L1 cache en un seul cycle.

Pour résumer:

• De 64 octets par ligne de cache => 6 décalage de bits à l'intérieur de ligne de cache

• 16KO/4-way => la résonance est de 4 ko.

  I. e. bits de l'adresse 0 à 5 sont la ligne de cache de décalage.

• 16KO / 64B lignes de cache => 2^14/2^6 = 2^8=128 les lignes de cache dans le cache.

• 4 chemin associatif => 128/4 = 32 index dans le tableau de cache. J' (Intel) appel de ces "ensembles".

  c'est à dire que vous pouvez envisager de la cache comme un tableau de 32 entrées ou les séries, chaque entrée contenant 4 lignes de cache annonce de leurs tags. (C'est plus compliqué que cela, mais ce n'est pas grave).

(En passant, les termes "set" et "moyen" ont des définitions différentes.)

• il y a 5 indice de bits, les bits 6 à 10 dans le plus simple régime.

  Cela signifie que toutes les lignes de cache qui ont exactement les mêmes valeurs dans l'indice de bits, les bits 6 à 10, correspond à la même série de la cache.

Maintenant, regardez votre programme.

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

Boucle k le plus proche du centre de la boucle. Le type de base est double, de 8 octets. Si la dimension=2048, c'est à dire 2K, alors éléments successifs d' B[dimension*k+j] accessible par la boucle sera de 2048 * 8 = 16 K octets en dehors. Ils seront tous de carte pour le même jeu de la L1 cache - ils ont tous le même indice dans le cache. Ce qui signifie que, au lieu de 128 lignes de cache dans le cache disponible pour l'utilisation, il y aura seulement 4 - la "4 voies associativité" de la cache.

I. e. vous obtiendrez probablement un cache miss tous les 4 itérations autour de cette boucle. Pas bonne.

(En fait, les choses sont un peu plus compliquées. Mais ce qui précède est une première bonne compréhension. Les adresses des entrées de B mentionné ci-dessus est une adresse virtuelle. Il y aurait peut-être légèrement différente de l'adresse physique. En outre, le Bulldozer a une façon prédictive cache, probablement à l'aide des adresses virtuelles bits, afin de ne pas avoir à attendre pour un virtuelle et adresse physique de la traduction. Mais, dans tous les cas: votre code a une "résonance" de 16K. Le cache de données L1 a une résonance de 16K. Pas bon.)]

Si vous modifiez la dimension juste un peu, par exemple à 2 048+1, alors les adresses de la matrice B seront répartis à travers tous les jeux de la mémoire cache. Et vous aurez beaucoup moins de défauts de cache.

Il est assez commun d'optimisation pour étoffer vos tableaux, par exemple pour changer à 2048 2049, pour éviter cette théorie de la relativité restreinte de la résonance. Mais "cache le blocage est encore plus important de l'optimisation. http://suif.stanford.edu/papers/lam-asplos91.pdf

---

En plus de la ligne de cache de résonance, il y a d'autres choses qui se passent ici. Par exemple, le cache L1 a 16 banques, chacune de 16 octets. Avec la dimension = 2048, successives B accède à l'intérieur de la boucle de la volonté de toujours aller à la même banque. Donc ils ne peuvent pas aller en parallèle - et si l'Un d'accès pour aller à la même banque, vous allez perdre.

Je ne pense pas, en le regardant, que c'est aussi grand que le cache de résonance.

Et, oui, probablement, il peut être aliasing va. E. g. le STLF (Magasin À la Charge de la Redirection de tampons) peut-être que la comparaison à l'aide d'un petit champ de bits, et d'obtenir de mauvais résultats.

(En fait, si vous pensez à ce sujet, la résonance dans le cache, c'est comme l'aliasing, liés à l'utilisation de bitfields. La résonance est causé par de multiples lignes de cache cartographie de la même série, ne diffuse pas arond. Alisaing est causée par le matching basé sur incomplète bits de l'adresse.)

---

Dans l'ensemble, ma recommandation pour le paramétrage:

1. Essayez de cache de blocage, sans autre analyse. Je dis cela, car le cache de blocage 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 un bien à l'écoute de la bibliothèque de routine, la matrice se multiplier.

Answer 3

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

Vous pouvez commencer à affiner ce qui est à l'œuvre, en traçant des temps/dimension^3 pour une plage de valeurs. Si vous avez soufflé un cache ou épuisé TLB atteindre, vous verrez une plus ou moins à plat de la section suivie d'une forte hausse entre 2000 et 2048, suivie par une autre section plate. Si vous voyez aliasing liées stands, vous verrez une plus ou moins à plat graphique avec un pic étroit à la hausse à 2048.

Bien sûr, cela a de diagnostic de l'alimentation, mais il n'est pas concluant. Si vous souhaitez de façon concluante savoir quelle est la source du ralentissement de l'est, vous voulez apprendre davantage sur les compteurs de performance, qui peut répondre à ce genre de question définitivement.

Answer 4

Un couple de réponses mentionnées Cache L2 problèmes.

Vous pouvez effectivement vérifier cela avec un cache de simulation. Valgrind est cachegrind outil peut le faire.

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

Définissez les paramètres de ligne de commande afin qu'elles correspondent avec votre CPU L2 paramètres.

Tester avec des matrices de différentes tailles, vous verrez probablement une augmentation soudaine de la L2 miss ratio.

Answer 5

Je sais que c'est waaaay trop vieux, mais je vais en prendre une bouchée. C'est (comme il a été dit) un problème de cache quelles sont les causes du ralentissement de la autour de des puissances de deux. Mais il y a un autre problème: il est trop lent. Si vous regardez votre calcul de la boucle.

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];

Le plus intérieur de la boucle de changements k de 1 à chaque itération, ce qui signifie que l'accès à seulement 1 double à partir du dernier élément que vous avez utilisé d'Une mais d'un ensemble de "dimension" doubles à partir du dernier élément de B. Cela ne prend pas tout l'avantage de la mise en cache des éléments de B.

Si vous modifiez ce:

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 les mêmes résultats (modulo double plus associativité des erreurs), mais c'est un ensemble beaucoup plus de cache-friendly (local). Je l'ai essayé et il donne des améliorations substantielles. Cela peut être résumé comme

Ne multipliez pas les matrices, par définition, mais plutôt, par les lignes

---

Exemple de la vitesse (j'ai changé votre code afin de prendre la dimension d'un argument)

$ diff a.c b.c
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     a.c   -o a
$ make b
cc     b.c   -o b
$ ./a 1024

secs:88.732918
$ ./b 1024

secs:12.116630

---

Comme un bonus (et en quoi est-ce lié à cette question), c'est que cette boucle ne souffre pas du problème précédent.

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