Quel est le code « cache-friendly » ?

Question

Quelqu'un pourrait éventuellement donner un exemple de « cache code hostile » et la version « cache amical » de ce code ?

Comment puis-je m’assurer que j’ai écrire du code efficace-cache ?

Answer 1

En plus de @Marc Claesen réponse, je pense qu'à cet égard un bon exemple classique de cache-hostiles code est le code qui analyse un C bidimensionnelle, array (par exemple une image bitmap) les colonnes au lieu de la ligne sage.

Les éléments qui sont adjacents dans une rangée sont également à proximité dans la mémoire et donc d'accéder à la séquence de moyens d'accéder, dans l'ordre ascendant de la mémoire de l'ordre; c'est le cache-friendly, depuis le cache tend pour extraire des blocs de mémoire contigus.

Au lieu de cela, l'accès à ces éléments de la colonne sage se cache-hostiles, des éléments sur la même colonne sont éloignés dans la mémoire de l'autre (en particulier, leur distance est égale à la taille de la ligne), de sorte que lorsque vous utilisez ce modèle d'accès vous êtes à sauter partout dans la mémoire, peut-être gaspiller de l'effort de la mémoire cache de récupérer les éléments de proximité dans la mémoire.

Et tout ce qu'il faut, c'est aller de

for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

pour

for(unsigned int x=0; x<width; ++y)
{
    for(unsigned int y=0; y<height; ++x)
    {
        ... image[y][x] ...
    }
}

Cet effet peut être assez spectaculaire (plusieurs ordre de grandeur de la vitesse) dans les systèmes avec des petits caches et/ou de travailler avec de grands tableaux (par exemple,+ de 10 mégapixels 24 bpp images sur les machines actuelles); pour cette raison, si vous avez à faire beaucoup de verticale analyses, il est souvent préférable de faire pivoter l'image de 90 degrés premier et effectuer les différentes analyses plus tard, en limitant le cache-hostiles du code de la rotation.

Answer 2

L'optimisation de l'utilisation du cache provient en grande partie de deux facteurs.

La localité de Référence

Le premier facteur (à qui d'autres l'ont déjà fait allusion) est une localité de référence. La localité de référence a vraiment deux dimensions: l'espace et le temps.

• Spatiale

La dimension spatiale est également livré à deux choses: tout d'abord, nous voulons pack nos informations dense, de sorte que plus d'informations seront ajustement en ce que la mémoire est limitée. Cela signifie, par exemple) que vous avez besoin d'une amélioration majeure dans la complexité de calcul pour justifier des structures de données basées sur de petits nœuds rejoint par des pointeurs.

Deuxièmement, nous voulons des informations qui seront traitées ensemble, également située ensemble. Typique de cache fonctionne en "lignes", ce qui signifie que lorsque vous accédez à des informations, d'autres informations à proximité adresses seront chargés dans le cache avec la partie qui nous a touché. Par exemple, quand je touche un octet, le cache peut charger 128 ou 256 octets près de celui-là. Pour en profiter, en général, vous voulez que les données organisées afin de maximiser la probabilité que vous aurez également l'utiliser que d'autres données qui a été chargé en même temps.

Pour un exemple trivial, cela peut vouloir dire qu'une recherche linéaire peut être beaucoup plus compétitif avec un binaire de recherche que vous attendez. Une fois que vous avez chargé un élément à partir d'une ligne de cache, en utilisant le reste des données dans la ligne de cache est presque gratuit. Une recherche binaire devient nettement plus rapidement que lorsque les données sont assez grand pour que la recherche binaire réduit le nombre de lignes de cache.

• Le temps

La dimension de temps signifie que lorsque vous effectuez certaines opérations sur certaines données, que vous voulez (autant que possible) de faire toutes les opérations sur les données à la fois.

Depuis que vous avez marqués ce que C++, je vais souligner un exemple classique d'un relativement cache-hostiles conception: std::valarray. valarray surcharges de la plupart des opérateurs arithmétiques, donc je peux (par exemple) dire a = b + c + d; (où a, b, c et d sont tous valarrays) pour faire de l'élément-sage ajout de ces tableaux.

Le problème, c'est qu'il se promène à travers une paire d'entrées, met les résultats dans un fichier temporaire, des promenades à une autre paire d'entrées, et ainsi de suite. Avec un grand nombre de données, le résultat d'un calcul peuvent disparaître de la mémoire cache avant qu'il est utilisé dans le prochain calcul, de sorte que nous sommes en fin de lecture (et d'écriture) à plusieurs reprises les données avant de nous obtenir notre résultat final. Si chaque élément du résultat final sera quelque chose comme (a[n] + b[n]) * (c[n] + d[n]);, nous serions préfèrent généralement de lire chaque a[n], b[n], c[n] et d[n] une fois, faire le calcul, écrire le résultat, incrémenter n et répétez jusqu'à ce que nous ayons terminé.²

Le Partage De La Ligne

Le deuxième facteur important est d'éviter le partage de la ligne. Pour comprendre cela, nous avons probablement besoin de sauvegarder et de regarder un peu comment les caches sont organisées. La forme la plus simple de cache est directement mappée. Cela signifie une adresse dans la mémoire principale ne peut être stocké dans un endroit spécifique dans le cache. Si nous sommes à l'aide des données de deux éléments qui correspondent à la même place dans le cache, il fonctionne mal, chaque fois que nous utilisons un seul élément de données, l'autre doit être supprimées du cache pour faire de la place pour les autres. Le reste de la cache peut être vide, mais ces éléments ne seront pas utiliser d'autres parties de la cache.

Pour éviter cela, la plupart des caches sont ce qu'on appelle des "associative". Par exemple, dans un 4-way set-associative cache, n'importe quel élément de la mémoire principale peut être stocké à l'un des 4 endroits différents dans le cache. Ainsi, lorsque le cache est va charger un élément, il semble pour le moins récemment utilisé³ élément parmi ces quatre, des bouffées de chaleur à la mémoire principale, et charge le nouvel élément à sa place.

Le problème est probablement assez évident: pour un direct-mapped de cache, les deux opérandes qui se produisent à la carte pour le même emplacement de la cache peut conduire à un mauvais comportement. Un N-way set-associative cache augmente le nombre de 2 à N+1. L'organisation d'un cache en plus de "moyens" faut plus de circuits et généralement plus lent, de sorte que (par exemple) un 8192-chemin ensemble associatif cache est rarement une bonne solution.

En fin de compte, ce facteur est le plus difficile à contrôler dans un code portable. Votre contrôle sur l'endroit où vos données est placé est généralement assez limitée. Pire, la cartographie exacte de l'adresse de cache varie entre sinon processeurs similaires. Dans certains cas, cependant, il peut être utile de faire des choses comme l'allocation d'une grande mémoire tampon, puis en utilisant uniquement des pièces de ce que vous avez alloué à s'assurer contre le partage de données les mêmes lignes de cache (même si vous aurez probablement besoin de détecter l'exacte du processeur et d'agir en conséquence pour ce faire).

• Faux Partage

Il y a une autre question liée appelé "false sharing". Cette question se pose dans un multiprocesseur ou système multicœur, où deux (ou plus) des processeurs/cœurs ont des données qui est séparé, mais tombe dans la même ligne de cache. Cela force les deux processeurs/cœurs de coordonner leurs accès aux données, même si chacun a son propre, distinct de l'élément de données. Surtout si les deux modifier les données en alternance, ce qui peut conduire à un énorme ralentissement alors que les données doivent être constamment la navette entre les processeurs. Cela ne peut pas être facilement guéries par l'organisation de la mémoire cache en plus de "moyens" ou quelque chose comme ça. Le principal moyen d'éviter ça est de veiller à ce que les deux fils rarement (de préférence jamais) de modifier les données qui pourraient être dans la même ligne de cache (avec les mêmes mises en garde sur la difficulté de contrôler les adresses de données est affecté).

---

1. Ceux qui connaissent le C++ bien peut se demander si celle-ci est ouverte à l'optimisation par quelque chose comme l'expression de modèles. Je suis sûr que la réponse est que oui, ça pourrait se faire, et s'il l'était, il serait sans doute assez importante victoire. Je ne suis pas au courant de quelqu'un l'ayant fait, cependant, et compte tenu du peu de valarray s'en servent, je serais au moins un peu surpris de voir quelqu'un le faire.

2. Dans le cas où quelqu'un se demande comment valarray (spécialement conçu pour la performance) pourrait être ce mal, il se résume à une chose: c'était vraiment conçu pour les machines, comme les anciens Crays, qui a utilisé rapide de la mémoire principale et pas de cache. Pour eux, cela a été vraiment un près de l'idéal de la conception.

3. Oui, je simplifie: la plupart des caches n'est pas vraiment mesurer le moins récemment utilisé le point avec précision, mais elles utilisent une heuristique qui vise à se rapprocher sans avoir à garder à temps plein-timbre pour chaque accès.

Answer 3

Bienvenue dans le monde des Données de Conception Orientée. Le mantra fondamental est de Trier, Éliminer les Branches, Lot, Éliminer virtual des appels - toutes les étapes vers une meilleure localité.

Depuis que vous avez marqué la question avec le C++, ici obligatoire typique C++ Conneries. Tony Albrecht de Pièges de la Programmation Orientée Objet est aussi une excellente introduction au sujet.

Answer 4

D'intéressantes: l'exemple classique de cache-hostiles rapport à cache-friendly code est le "cache blocage" de la matrice se multiplier.

Naïf matrice de multiplier ressemble

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Si N est grand, par exemple, si N * sizeof(elemType) est plus grand que la taille du cache, puis tous les accès à l' src2[k][j] sera un cache miss.

Il existe de nombreuses façons de l'optimisation d'un cache. Voici un exemple très simple: au lieu de lire un article par ligne de cache à l'intérieur de la boucle, utiliser tous les éléments:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Si le cache de la ligne de la taille est de 64 octets, et nous sommes d'exploitation de 32 bits (4 octets) flotte, puis il y a 16 éléments par ligne de cache. Et le nombre de défauts de cache via cette simple transformation est réduite d'environ 16 fois.

Amateur de transformations à opérer sur 2D tuiles, de l'optimiser pour de multiples caches (L1, L2, TLB), et ainsi de suite.

Quelques résultats de recherche sur google cache "blocage":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Une belle vidéo d'animation d'une optimisation du cache de blocage de l'algorithme.

http://www.youtube.com/watch?v=IFWgwGMMrh0

Boucle de carrelage est très étroitement liées:

http://en.wikipedia.org/wiki/Loop_tiling