Pourquoi la transposition d'une matrice de 512x512 est-elle beaucoup plus lente que la transposition d'une matrice de 513x513?

après avoir effectué quelques expériences sur des matrices carrées de différentes tailles, un modèle est apparu. Invariablement, transposant une matrice de taille 2^n est plus lent que transposant une matrice de taille 2^n+1 . Pour les petites valeurs de n , la différence n'est pas importante.

de grandes différences se produisent cependant sur une valeur de 512. (du moins pour moi)

avertissement: je sais que la fonction n'est pas réellement transposer la matrice à cause du double échange d'éléments, mais cela ne fait aucune différence.

suit le code:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

changer MATSIZE permet de modifier la taille (duh!). J'ai posté deux versions sur ideone:

dans mon environnement (MSVS 2010, optimisations complètes), la différence est similaire:

  • taille de 512 moyenne 2.19 ms
  • taille 513 - moyenne 0,57 ms

pourquoi cela se produit-il?

188
demandé sur Luchian Grigore 2012-07-10 17:00:20
la source

3 ответов

l'explication vient de Agner Fog dans logiciel D'optimisation en C++ et réduit à la façon dont les données sont accessibles et stockées dans le cache.

pour les Termes et les informations détaillées, voir l'entrée wiki sur la mise en cache , je vais réduire le champ ici.

Un cache est organisée en jeux et lignes . À un moment, un seul ensemble est utilisé, dont l'une des lignes qu'il contient peuvent être utilisés. La mémoire d'une ligne peut refléter le nombre de lignes nous donne la taille du cache.

pour une adresse mémoire particulière, nous pouvons calculer quel ensemble devrait refléter avec la formule:

set = ( address / lineSize ) % numberOfsets

ce genre de formule donne idéalement une distribution uniforme à travers les ensembles, parce que chaque adresse mémoire est aussi susceptible d'être lu (j'ai dit idéalement ).

il est clair que des chevauchements peuvent se produire. En cas de manque de cache, la mémoire est lue dans le cache et l'ancienne valeur est remplacée. Rappelez-vous que chaque ensemble a un certain nombre de lignes, dont la plus récente utilisée est écrasée avec la mémoire nouvellement lue.

je vais essayer de suivre un peu L'exemple D'Agner:

suppose que chaque jeu a 4 lignes, chaque contenant 64 octets. Nous essayons d'abord de lire l'adresse 0x2710 , qui va dans le jeu 28 . Et puis nous essayons aussi de lire les adresses 0x2F00 , 0x3700 , 0x3F00 et 0x4700 . L'ensemble de ces appartiennent au même ensemble. Avant de lire 0x4700 , toutes les lignes de l'ensemble auraient été occupées. La lecture de cette mémoire expulse une ligne existante dans l'ensemble, la ligne qui au départ tenait 0x2710 . Le problème réside dans le fait que nous lisons des adresses qui sont (pour cet exemple) 0x800 à part. C'est le critique de la foulée (encore une fois, pour cet exemple).

la foulée critique peut aussi être calculée:

criticalStride = numberOfSets * lineSize

Variables espacées criticalStride ou un enchère multiple pour les mêmes lignes de cache.

C'est la théorie. Ensuite, l'explication (aussi Agner, je la suis de près pour éviter de faire des erreurs):

suppose une matrice de 64x64 (rappelez-vous, les effets varient selon le cache) avec un cache de 8kb, 4 lignes par set * longueur de ligne de 64 octets. Chaque ligne peut contenir 8 des éléments de la matrice (64 bits int ).

la foulée critique serait de 2048 octets, ce qui correspond à 4 lignes de la matrice (qui est continue en mémoire).

supposons que nous traitons la rangée 28. Nous essayons de prendre les éléments de cette ligne et de les échanger avec les éléments de la colonne 28. Les 8 premiers éléments de la rangée forment une ligne de cache, mais ils vont en 8 différentes lignes de cache dans la colonne 28. Rappelez-vous, la foulée critique est de 4 lignes d'écart (4 éléments consécutifs dans une colonne).

lorsque l'élément 16 est atteint dans la colonne (4 lignes de cache par jeu et 4 lignes d'écart = problème) l'élément ex-0 sera expulsé du cache. Lorsque nous atteignons la fin de la colonne, Toutes les lignes de cache précédentes auraient été perdues et auraient dû être rechargées sur l'accès à l'élément suivant (toute la ligne est écrasée).

ayant une taille ce n'est pas un multiple de la foulée critique qui gâche ce scénario parfait pour désastre, car nous n'avons plus affaire à des éléments qui sont la foulée critique à part sur la verticale, donc le nombre de recharges de cache est fortement réduit.

une autre clause de non - responsabilité - je viens d'avoir ma tête autour de l'explication et j'espère que je l'ai cloué, mais je pourrais me tromper. Quoi qu'il en soit, j'attends une réponse (ou une confirmation) de Mysticial . :)

173
répondu Luchian Grigore 2018-09-21 08:39:26
la source

Luchian donne une explication de pourquoi ce comportement se produit, mais j'ai pensé que ce serait une bonne idée de montrer une solution possible à ce problème et en même temps montrer un peu sur les algorithmes inconscients de cache.

votre algorithme fait essentiellement:

for (int i = 0; i < N; i++) 
   for (int j = 0; j < N; j++) 
        A[j][i] = A[i][j];

qui est tout simplement horrible pour un CPU moderne. Une solution consiste à connaître les détails de votre système de cache et à modifier l'algorithme pour éviter ces problèmes. Ça marche bien tant que tu connais ces détails.. pas spécialement portable.

Peut-on faire mieux que ça? Oui nous le pouvons: une approche générale de ce problème est algorithmes de cache inconscients qui, comme le nom le dit, évite de dépendre de tailles de cache spécifiques [1]

la solution ressemblerait à ceci:

void recursiveTranspose(int i0, int i1, int j0, int j1) {
    int di = i1 - i0, dj = j1 - j0;
    const int LEAFSIZE = 32; // well ok caching still affects this one here
    if (di >= dj && di > LEAFSIZE) {
        int im = (i0 + i1) / 2;
        recursiveTranspose(i0, im, j0, j1);
        recursiveTranspose(im, i1, j0, j1);
    } else if (dj > LEAFSIZE) {
        int jm = (j0 + j1) / 2;
        recursiveTranspose(i0, i1, j0, jm);
        recursiveTranspose(i0, i1, jm, j1);
    } else {
    for (int i = i0; i < i1; i++ )
        for (int j = j0; j < j1; j++ )
            mat[j][i] = mat[i][j];
    }
}

légèrement plus complexe, mais un court test montre quelque chose de très intéressant sur mon ancien e8400 avec version VS2010 x64, code test pour MATSIZE 8192

int main() {
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);
    recursiveTranspose(0, MATSIZE, 0, MATSIZE);
    QueryPerformanceCounter(&end);
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));

    QueryPerformanceCounter(&start);
    transpose();
    QueryPerformanceCounter(&end);
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));
    return 0;
}

results: 
recursive: 480.58ms
iterative: 3678.46ms

Edit: à propos de l'influence de la taille: elle est beaucoup moins prononcée bien qu'encore perceptible à un certain degré, c'est parce que nous utilisons la solution itérative comme un noeud de feuille au lieu de revenir à 1 (l'optimisation habituelle pour les algorithmes récursifs). Si nous définissons LEAFSIZE = 1, le cache n'a aucune influence pour moi [ 8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms - c'est à l'intérieur de la marge d'erreur, les fluctuations sont dans les 100ms zone; cette "référence" n'est pas quelque chose que je serais trop à l'aise avec, si nous voulions tout à fait précis valeurs])

[1] Sources pour ce genre de choses: eh Bien, si vous ne pouvez pas obtenir une conférence de quelqu'un qui a travaillé avec Leiserson et la coopération sur ce.. Je suppose que leurs papiers un bon point de départ. Ces algorithmes sont encore assez rarement décrits - CLR a une seule note de bas de page à leur sujet. C'est quand même une bonne façon de surprendre les gens.


Edit (note: Je ne suis pas celui qui a posté cette réponse; je voulais juste ajouter ceci):

Voici une version C++ complète du code ci-dessus:

template<class InIt, class OutIt>
void transpose(InIt const input, OutIt const output,
    size_t const rows, size_t const columns,
    size_t const r1 = 0, size_t const c1 = 0,
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0,
    size_t const leaf = 0x20)
{
    if (!~c2) { c2 = columns - c1; }
    if (!~r2) { r2 = rows - r1; }
    size_t const di = r2 - r1, dj = c2 - c1;
    if (di >= dj && di > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, (r1 + r2) / 2, c2);
        transpose(input, output, rows, columns, (r1 + r2) / 2, c1, r2, c2);
    }
    else if (dj > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2) / 2);
        transpose(input, output, rows, columns, r1, (c1 + c2) / 2, r2, c2);
    }
    else
    {
        for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns);
            i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns)
        {
            for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows);
                j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows)
            {
                output[j2 + i1] = input[i2 + j1];
            }
        }
    }
}
71
répondu Voo 2014-05-25 10:26:19
la source

comme illustration de l'explication dans réponse de Luchian Grigore , voici à quoi ressemble la présence de cache matricielle pour les deux cas de matrices 64x64 et 65x65 (voir le lien ci-dessus pour plus de détails sur les nombres).

les couleurs dans les animations ci-dessous signifient ce qui suit:

La 64x64 cas:

cache presence animation for 64x64 matrix

remarquez comment presque chaque l'accès à une nouvelle rangée entraîne une erreur de cache. Et maintenant comment il regarde pour le cas normal, une matrice 65x65:

cache presence animation for 65x65 matrix

ici vous pouvez voir que la plupart des accès après le réchauffement initial sont des hits de cache. C'est ainsi que le cache CPU est censé fonctionner en général.

31
répondu Ruslan 2018-03-04 09:58:52
la source

Autres questions sur c++ performance optimization