Question Qu'est-ce qu'un code "cache-friendly"?


Quelle est la différence entre "cache le code hostile" et le "cache amical"code?

Comment puis-je m'assurer d'écrire du code efficace en cache?


612
2018-05-22 18:37


origine


Réponses:


Préliminaires

Sur les ordinateurs modernes, seules les structures de mémoire de plus bas niveau registres) peut déplacer des données dans des cycles d'horloge uniques. Cependant, les registres sont très chers et la plupart des cœurs d'ordinateurs ont moins de quelques dizaines de registres (quelques centaines à peut-être mille octets total). À l'autre extrémité du spectre de la mémoire (DRACHME), la mémoire est très bon marché (c'est-à-dire littéralement des millions de fois moins cher) mais prend des centaines de cycles après une demande pour recevoir les données. Pour combler ce fossé entre super rapide et cher et super lent et bon marché sont les mémoires cache, nommé L1, L2, L3 en vitesse et coût décroissants. L'idée est que la plus grande partie du code en cours d'exécution touchera un petit ensemble de variables souvent, et le reste (un ensemble beaucoup plus grand de variables) rarement. Si le processeur ne peut pas trouver les données dans le cache L1, alors il regarde dans le cache L2. Si ce n'est pas là, alors cache L3, et sinon là, la mémoire principale. Chacun de ces "ratés" est coûteux en temps.

(L'analogie est la mémoire cache est à la mémoire système, comme la mémoire système est de stockage sur disque dur.Le stockage sur disque dur est super bon marché, mais très lent).

La mise en cache est l'une des principales méthodes pour réduire l'impact de latence (Cf. le discours de Herb Sutter que j'ai lié au début). Pour paraphraser Herb Sutter (voir les liens ci-dessous): l'augmentation de la bande passante est facile, mais nous ne pouvons pas nous libérer de la latence.

Les données sont toujours récupérées dans la hiérarchie de la mémoire (le plus petit == le plus rapide au plus lent). UNE cache hit / miss se réfère généralement à un hit / miss dans le plus haut niveau de cache dans le processeur - par le plus haut niveau, je veux dire le plus grand == plus lent. Le taux de réussite du cache est crucial pour les performances, car chaque échec de cache entraîne l'extraction de données de la RAM (ou pire ...) qui prend beaucoup du temps (des centaines de cycles pour la RAM, des dizaines de millions de cycles pour le disque dur). En comparaison, la lecture des données du cache (le plus haut niveau) ne prend généralement qu'une poignée de cycles.

Dans les architectures informatiques modernes, le goulot d'étranglement des performances laisse le processeur mourir (par exemple en accédant à la RAM ou plus haut). Cela ne fera qu'empirer avec le temps. L'augmentation de la fréquence du processeur n'est actuellement plus pertinente pour augmenter les performances. Le problème est l'accès à la mémoire. Les efforts de conception matérielle dans les processeurs sont donc actuellement fortement axés sur l'optimisation des caches, de la prélecture, des pipelines et de la concurrence. Par exemple, les processeurs modernes passent environ 85% de la mémoire morte sur les caches et jusqu'à 99% pour stocker / déplacer les données!

Il y a beaucoup à dire sur le sujet. Voici quelques excellentes références sur les caches, les hiérarchies de mémoire et la programmation appropriée:

Principaux concepts pour le code compatible avec le cache

Un aspect très important du code cache-friendly est tout à propos de le principe de localité, dont le but est de placer des données proches en mémoire pour permettre une mise en cache efficace. En termes de cache du processeur, il est important d'être conscient des lignes de cache pour comprendre comment cela fonctionne: Comment fonctionnent les lignes de cache? 

Les aspects particuliers suivants sont d'une grande importance pour optimiser la mise en cache:

  1. Localité temporelle: quand un emplacement mémoire donné a été accédé, il est probable que le même emplacement soit à nouveau accessible dans un proche avenir. Idéalement, cette information sera toujours mise en cache à ce moment-là.
  2. Localité spatiale: cela se réfère à la mise en relation de données connexes. La mise en cache se produit à plusieurs niveaux, pas seulement dans le processeur. Par exemple, lorsque vous lisez à partir de la mémoire vive, une partie plus importante de la mémoire est récupérée que ce qui a été spécifiquement demandé car très souvent le programme nécessitera bientôt ces données. Les caches HDD suivent la même ligne de pensée. Spécifiquement pour les caches CPU, la notion de lignes de cache est important.

Utiliser approprié  conteneurs

Un exemple simple de cache-friendly versus cache-hostile est de std::vector contre std::list. Éléments d'un std::vector sont stockés dans la mémoire contiguë, et à ce titre, l'accès est beaucoup plus facile à mettre en cache que d'accéder à des éléments dans un std::list, qui stocke son contenu partout. Ceci est dû à la localité spatiale.

Bjarne Stroustrup en donne une très belle illustration ce clip youtube (merci à @Mohammad Ali Baydoun pour le lien!).

Ne négligez pas le cache dans la structure de données et la conception de l'algorithme

Dans la mesure du possible, essayez d'adapter vos structures de données et l'ordre des calculs de manière à permettre une utilisation maximale du cache. Une technique courante à cet égard est blocage de la mémoire cache  (Version Archive.org), ce qui est extrêmement important dans le calcul haute performance (cf. ATLAS).

Connaître et exploiter la structure implicite des données

Un autre exemple simple, que beaucoup de gens sur le terrain oublient parfois, est la colonne majeure (ex. ,) par rapport à l'ordre des rangées majeures (ex. ,) pour stocker des tableaux bidimensionnels. Par exemple, considérez la matrice suivante:

1 2
3 4

Dans la commande de rangée-majeure, ceci est stocké dans la mémoire comme 1 2 3 4; dans l'ordre de colonne majeur, cela serait stocké comme 1 3 2 4. Il est facile de voir que les implémentations qui n'exploitent pas cette commande vont rapidement se heurter à des problèmes de cache (facilement évitables!). Malheureusement, je vois des choses comme ça très souvent dans mon domaine (apprentissage automatique). @MatteoItalia a montré cet exemple plus en détail dans sa réponse.

Lors de la récupération d'un certain élément d'une matrice à partir de la mémoire, les éléments à proximité seront également récupérés et stockés dans une ligne de cache. Si l'ordre est exploité, cela entraînera moins d'accès à la mémoire (car les prochaines valeurs qui sont nécessaires pour les calculs ultérieurs sont déjà dans une ligne de cache).

Pour simplifier, supposons que le cache comprenne une seule ligne de cache qui peut contenir 2 éléments de matrice et que lorsqu'un élément donné est extrait de la mémoire, le suivant le soit également. Disons que nous voulons prendre la somme sur tous les éléments dans l'exemple matrice 2x2 ci-dessus (appelons-le M):

Exploitation de la commande (par exemple, modification de l'index des colonnes dans ):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

Ne pas exploiter l'ordre (par exemple, changer l'index de ligne d'abord dans ):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

Dans cet exemple simple, l'exploitation de la commande double approximativement la vitesse d'exécution (puisque l'accès à la mémoire nécessite beaucoup plus de cycles que le calcul des sommes). En pratique, la différence de performance peut être beaucoup plus grand.

Évitez les branches imprévisibles

Les architectures modernes disposent de pipelines et les compilateurs deviennent très bons pour réorganiser le code afin de minimiser les retards dus à l'accès mémoire. Lorsque votre code critique contient des branches (imprévisibles), il est difficile ou impossible de pré-lire les données. Cela conduira indirectement à plus d'échecs de cache.

Ceci est expliqué très bien ici (merci à @ 0x90 pour le lien): Pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié?

Éviter les fonctions virtuelles

Dans le contexte de , virtual les méthodes représentent une question controversée en ce qui concerne les erreurs de cache (un consensus général existe selon lequel elles devraient être évitées autant que possible en termes de performance). Les fonctions virtuelles peuvent induire des échecs de cache lors de la recherche, mais cela arrive seulement si la fonction spécifique n'est pas appelée souvent (sinon elle serait probablement mise en cache), ce qui est considéré comme un non-problème par certains. Pour référence sur ce problème, consultez: Quel est le coût d'exécution d'une méthode virtuelle dans une classe C ++? 

Problèmes communs

Un problème commun dans les architectures modernes avec des caches multiprocesseurs est appelé faux partage. Cela se produit lorsque chaque processeur individuel tente d'utiliser des données dans une autre région de mémoire et tente de les stocker dans le même ligne de cache. Cela provoque l'écrasement de la ligne de cache - qui contient des données qu'un autre processeur peut utiliser - à plusieurs reprises. En effet, différents threads se font mutuellement patienter en induisant des échecs de cache dans cette situation. Voir aussi (merci à @Matt pour le lien): Comment et quand aligner la taille de la ligne de cache?

Un symptôme extrême de mauvaise mise en cache dans la mémoire RAM (ce qui n'est probablement pas ce que vous voulez dire dans ce contexte) est ce que l'on appelle raclée. Cela se produit lorsque le processus génère continuellement des erreurs de page (par exemple, accède à la mémoire qui n'est pas dans la page en cours), ce qui nécessite un accès au disque.


798
2018-05-22 18:39



En plus de la réponse de @Marc Claesen, je pense qu'un exemple classique instructif de code anti-cache est le code qui scanne un tableau bidimensionnel C (par exemple une image bitmap) au niveau des colonnes plutôt que des lignes.

Les éléments qui sont adjacents dans une rangée sont également adjacents dans la mémoire, en y accédant ainsi en séquence signifie les y accéder dans l'ordre croissant de la mémoire; ceci est compatible avec le cache, puisque le cache a tendance à pré-charger des blocs de mémoire contigus.

Au lieu de cela, l'accès à ces éléments par colonne est hostile au cache, car les éléments d'une même colonne sont distants les uns des autres (en particulier, leur distance est égale à la taille de la ligne). sautent dans la mémoire, gaspillant potentiellement l'effort de la cache de récupérer les éléments à proximité dans la mémoire.

Et tout ce qu'il faut pour ruiner la performance est d'aller de

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

à

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Cet effet peut être tout à fait dramatique (plusieurs ordres de grandeur en vitesse) dans des systèmes avec de petites caches et / ou travaillant avec de grands réseaux (par exemple 10+ mégapixels 24 images bpp sur des machines courantes); Pour cette raison, si vous devez effectuer de nombreuses analyses verticales, il est souvent préférable de faire d'abord pivoter l'image de 90 degrés et d'effectuer les différentes analyses ultérieurement, en limitant le code anti-cache à la rotation.


121
2018-05-22 19:51



L'optimisation de l'utilisation du cache dépend principalement de deux facteurs.

Localité de référence

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

  • Spatial

La dimension spatiale se résume également à deux choses: d'abord, nous voulons densifier nos informations de manière dense, de sorte que plus d'informations s'inscrivent dans cette mémoire limitée. Cela signifie (par exemple) que vous avez besoin d'une amélioration majeure de la complexité de calcul pour justifier les structures de données basées sur de petits nœuds joints par des pointeurs.

Deuxièmement, nous voulons que les informations qui seront traitées ensemble soient également situées ensemble. Un cache typique fonctionne en "lignes", ce qui signifie que lorsque vous accédez à certaines informations, d'autres informations à proximité des adresses seront chargées dans le cache avec la partie que nous avons touchée. Par exemple, lorsque je touche un octet, le cache peut charger 128 ou 256 octets près de celui-ci. Pour tirer parti de cela, vous souhaitez généralement que les données soient agencées pour maximiser la probabilité que vous utilisiez également ces autres données qui ont été chargées en même temps.

Pour un exemple vraiment trivial, cela peut signifier qu'une recherche linéaire peut être beaucoup plus compétitive avec une recherche binaire que ce à quoi vous vous attendez. Une fois que vous avez chargé un élément d'une ligne de cache, l'utilisation du reste des données dans cette ligne de cache est presque gratuite. Une recherche binaire devient sensiblement plus rapide uniquement lorsque les données sont suffisamment importantes pour que la recherche binaire réduise le nombre de lignes de cache auxquelles vous accédez.

  • Temps

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

Depuis que vous avez étiqueté cela comme C ++, je vais pointer vers un exemple classique d'un design relativement anti-cache: std::valarray. valarray surcharge 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 l'addition par élément de ces tableaux.

Le problème avec ceci est qu'il marche à travers une paire d'entrées, met les résultats dans un provisoire, marche à travers une autre paire d'entrées, et ainsi de suite. Avec beaucoup de données, le résultat d'un calcul peut disparaître du cache avant qu'il ne soit utilisé dans le calcul suivant. Nous finissons par lire (et écrire) les données plusieurs fois avant d'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 préférerions généralement lire chaque a[n], b[n], c[n] et d[n] une fois, faites le calcul, écrivez le résultat, incrémentez n et répétez jusqu'à ce que nous ayons fini.2

Partage de ligne

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

Pour éviter cela, la plupart des caches sont ce qu'on appelle "set associative". Par exemple, dans un cache associatif à quatre voies, n'importe quel élément de la mémoire principale peut être stocké à l'un des quatre endroits différents dans le cache. Donc, quand le cache va charger un objet, il cherche le moins récemment utilisé3 élément parmi ces quatre, le vide dans la mémoire principale, et charge le nouvel élément à sa place.

Le problème est probablement assez évident: pour un cache mappé directement, deux opérandes qui correspondent au même emplacement de cache peuvent conduire à un mauvais comportement. Un cache associatif à N-voies augmente le nombre de 2 à N + 1. L'organisation d'un cache en plusieurs "chemins" nécessite des circuits supplémentaires et fonctionne généralement plus lentement, donc (par exemple) un cache associatif à 8192 voies est rarement une bonne solution non plus.

En fin de compte, ce facteur est plus difficile à contrôler dans un code portable. Votre contrôle sur l'emplacement de vos données est généralement assez limité. Pire, le mappage exact de l'adresse au cache varie entre des processeurs similaires. Dans certains cas, cependant, il peut être utile d'allouer un tampon de grande taille, puis d'utiliser uniquement les parties de ce que vous avez allouées pour éviter le partage de données avec les mêmes lignes de cache (même si vous aurez probablement besoin du processeur agir en conséquence pour le faire).

  • Faux partage

Il y a un autre article connexe appelé "faux partage". Cela se produit dans un système multiprocesseur ou multicœur, dans lequel deux (ou plusieurs) processeurs / cœurs ont des données séparées, mais qui appartiennent à la même ligne de cache. Cela force les deux processeurs / coeurs à coordonner leur accès aux données, même si chacun a son propre élément de données séparé. Surtout si les deux modifient les données en alternance, cela peut conduire à un ralentissement massif car les données doivent être constamment transmises entre les processeurs. Cela ne peut pas facilement être guéri en organisant le cache dans plus de "façons" ou quelque chose comme ça non plus. La principale façon de l'éviter est de s'assurer que deux threads modifient rarement (de préférence jamais) les données qui pourraient éventuellement se trouver dans la même ligne de cache (avec les mêmes mises en garde sur la difficulté de contrôler les adresses auxquelles les données sont allouées).


  1. Ceux qui connaissent bien C ++ peuvent se demander si cela est ouvert à l'optimisation via quelque chose comme des modèles d'expression. Je suis assez sûr que la réponse est oui, cela pourrait être fait et si c'était le cas, ce serait probablement une victoire assez substantielle. Je ne suis pas au courant de quiconque l'ayant fait, cependant, et compte tenu du peu valarray s'habituera, je serais au moins un peu surpris de voir quelqu'un le faire non plus.

  2. Au cas où quelqu'un se demande comment valarray (conçu spécifiquement pour la performance) pourrait être si mal, il se résume à une chose: il a été vraiment conçu pour des machines comme les anciens Crays, qui utilisent la mémoire principale rapide et pas de cache. Pour eux, c'était vraiment un design presque idéal.

  3. Oui, je simplifie: la plupart des caches ne mesurent pas vraiment l'objet utilisé le moins récemment, mais ils utilisent une heuristique qui est destinée à être proche de cela sans avoir à garder un horodatage complet pour chaque accès.


74
2018-05-31 18:18



Bienvenue dans le monde de Data Oriented Design. Le mantra de base est de trier, éliminer les branches, les lots, éliminer virtual appels - toutes les étapes vers une meilleure localité.

Depuis que vous avez étiqueté la question avec C ++, voici l'obligatoire conneries C ++ typiques. Tony Albrecht Pièges de la programmation orientée objet est également une excellente introduction au sujet.


28
2018-05-22 21:03



Juste empiler sur: l'exemple classique de cache-hostile vs cache-code est le "blocage de cache" de la matrice multiplier.

La matrice naïve se multiplie 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 ex. si N * sizeof(elemType) est supérieure à la taille du cache, puis chaque accès unique à src2[k][j] sera un cache manqué.

Il existe plusieurs façons d'optimiser cela pour un cache. Voici un exemple très simple: au lieu de lire un élément par ligne de cache dans la boucle interne, utilisez 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 la taille de la ligne de cache est de 64 octets et si nous opérons sur des flottants de 32 bits (4 octets), il y a 16 éléments par ligne de cache. Et le nombre d'échecs de cache via cette simple transformation est réduit d'environ 16 fois.

Les transformations de colombage fonctionnent sur des mosaïques 2D, optimisent pour plusieurs caches (L1, L2, TLB), et ainsi de suite.

Quelques résultats de googling "cache blocking":

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

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

Une belle animation vidéo d'un algorithme de blocage de cache optimisé.

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

Le pavage de boucle est très étroitement lié:

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


20
2018-05-29 03:50



Les processeurs fonctionnent aujourd'hui avec de nombreux niveaux de zones de mémoire en cascade. Ainsi, le processeur aura un tas de mémoire qui est sur la puce CPU elle-même. Il a un accès très rapide à cette mémoire. Il existe différents niveaux de cache chaque accès plus lent (et plus) que le suivant, jusqu'à ce que vous arriviez à la mémoire système qui n'est pas sur le processeur et est relativement beaucoup plus lent à l'accès.

Logiquement, dans le jeu d'instructions de la CPU, il suffit de se référer aux adresses mémoire dans un espace d'adressage virtuel géant. Lorsque vous accédez à une seule adresse mémoire, le CPU ira le chercher. dans l'ancien temps, il allait chercher cette seule adresse. Mais aujourd'hui, le processeur va chercher un tas de mémoire autour du bit que vous avez demandé, et le copier dans le cache. Il suppose que si vous avez demandé une adresse particulière, il est très probable que vous allez demander une adresse à proximité très bientôt. Par exemple, si vous copiez un tampon, vous lisez et écrivez à partir d'adresses consécutives, l'une après l'autre.

Donc aujourd'hui, quand vous récupérez une adresse, elle vérifie le premier niveau de cache pour voir si elle a déjà lu cette adresse dans le cache, si elle ne la trouve pas, alors c'est un cache manquant et il faut passer au niveau suivant de cache pour le trouver, jusqu'à ce qu'il doit finalement sortir dans la mémoire principale.

Le code amical du cache essaie de garder les accès proches les uns des autres en mémoire afin de minimiser les échecs de cache.

Donc, un exemple serait d'imaginer que vous vouliez copier une table géante en 2 dimensions. Il est organisé avec reach row en mémoire consécutive, et une rangée suit la suivante après.

Si vous avez copié les éléments une rangée à la fois de gauche à droite, cela serait facile à mettre en cache. Si vous avez décidé de copier la table une colonne à la fois, vous copieriez exactement la même quantité de mémoire, mais le cache serait hostile.


12
2018-05-22 19:58



Il faut préciser que non seulement les données doivent être compatibles avec le cache, mais aussi pour le code. Ceci est en plus de la prédicition de branche, réorganisation de l'instruction, en évitant les divisions réelles et d'autres techniques.

Typiquement, plus le code est dense, moins il faut de lignes de cache pour le stocker. Cela se traduit par plus de lignes de cache disponibles pour les données.

Le code ne doit pas appeler des fonctions partout, car elles nécessitent généralement une ou plusieurs lignes de cache, ce qui réduit le nombre de lignes de cache pour les données.

Une fonction doit commencer à une adresse de ligne d'alignement de ligne de cache. Bien qu'il existe des commutateurs de compilateur (gcc) pour cela, sachez que si les fonctions sont très courtes, il peut être inutile pour chacune d'occuper une ligne de cache entière. Par exemple, si trois des fonctions les plus utilisées correspondent à une ligne de cache de 64 octets, cela représente moins de gaspillage que si chacune d'entre elles possède sa propre ligne et que deux lignes de cache sont moins disponibles pour d'autres utilisations. Une valeur d'alignement typique pourrait être 32 ou 16.

Donc, passez un peu de temps pour rendre le code dense. Testez différentes constructions, compilez et examinez la taille et le profil du code généré.


4
2017-08-08 17:50