Comment fonctionne la mémoire cache?

Question

Aujourd'hui, alors que j'étais en classe d'organisation informatique, un enseignant m'a parlé de quelque chose d'intéressant. En ce qui concerne Pourquoi la mémoire cache fonctionne, il a déclaré:

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

il n’est pas bon de changer la première ligne avec la seconde. Quelle est votre opinion à ce sujet? Et pourquoi c'est comme ça?

Answer 1

Localité de référence. Comme les données sont stockées par rangées, pour chaque rangée, les j colonnes sont dans des adresses de mémoire adjacentes. Le système d'exploitation charge généralement une page entière de la mémoire dans la mémoire cache et les références d'adresses adjacentes font probablement référence à cette même page. Si vous incrémentez l'index de ligne dans la boucle interne, il est possible que ces lignes se trouvent sur des pages différentes (car elles sont séparées par un j double) et que le cache doit sans cesse importer et supprimer des pages de mémoire lors de la référence. les données. C'est ce qu'on appelle la raclée et c'est mauvais pour la performance.

En pratique, et avec des caches plus grands et modernes, la taille des lignes / colonnes devrait être assez grande avant que cela ne soit utilisé, mais cela reste une bonne pratique.

[EDIT] La réponse ci-dessus est spécifique à C et peut différer pour d'autres langues. Le seul que je connaisse est différent, c'est le Fortran. FORTRAN stocke les objets dans l'ordre des colonnes (la ligne ci-dessus est la principale) et il serait correct de modifier l'ordre des instructions dans FORTRAN. Si vous voulez / avez besoin d’efficacité, il est important de savoir comment votre langage implémente le stockage des données.

Answer 2

Ulrich Drepper, de Red Hat et glibc fame, a publié un très bon article, Ce que tout programmeur devrait avoir Connaître la mémoire . Une section a traité des caches en détail. Par exemple, dans les systèmes SMP, il existe des effets de cache dans lesquels les processeurs peuvent finir par écraser la propriété d’une ligne de cache modifiée, ce qui nuit considérablement aux performances.

Answer 3

C’est comme ça car caches comme une localité. Le même nombre de mémoires accédées, mais espacées davantage, atteindra différentes "lignes". de cache, ou pourrait même manquer le cache tout à fait. Il est donc judicieux, chaque fois que vous avez le choix, d'organiser les données de manière à ce que les accès susceptibles de se produire à proximité l'un de l'autre dans le temps se fassent également dans l'espace. Cela augmente les chances d'un accès au cache et vous donne plus de performances.

Il existe bien sûr une mine d'informations sur ce sujet, voir par exemple cette entrée wikipedia sur la localité de référence . Ou, je suppose, votre propre manuel de cours. :)

Answer 4

En C, les matrices à n dimensions sont les lignes principales, ce qui signifie que le dernier index de la matrice représente les espaces adjacents en mémoire. Ceci diffère de certains autres langages, par exemple FORTRAN, qui sont des colonnes majeures. En FORTRAN, il est plus efficace de parcourir une matrice 2D comme ceci:

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

La mémoire cache est une mémoire très rapide et très chère, proche du processeur. Plutôt que d'extraire à chaque fois un petit morceau de données de la RAM, le CPU récupère un bloc de données et le stocke dans le cache. Le pari est que si vous ne lisez qu'un octet, le prochain octet que vous lisez sera probablement juste après. Si tel est le cas, cela peut venir du cache.

En disposant votre boucle telle que vous l’avez, vous lisez les octets dans l’ordre dans lequel ils sont stockés en mémoire. Cela signifie qu'ils sont dans le cache et peuvent être lus très rapidement par la CPU. Si vous permutiez les lignes 1 et 2, vous liriez tous les "N". octets à chaque fois autour de la boucle. Les octets que vous lisez ne sont plus consécutifs en mémoire et peuvent donc ne pas être dans le cache. Le processeur doit les récupérer dans la RAM (plus lente) pour que vos performances diminuent.