Comment écrire le code qui utilise le mieux le cache du processeur pour améliorer les performances?

Cela peut sembler une question subjective, mais ce que je recherche, ce sont des exemples spécifiques que vous auriez pu rencontrer à ce sujet.

1. Comment rendre le code, le cache efficace / convivial (plus de hits de cache, aussi peu de cache manque que possible)? Des deux points de vue, le cache de données et le cache de programme (cache d'instructions), c'est-à-dire ce que les choses dans son code, liées aux structures de données et aux constructions de code, devraient-on prendre en compte pour rendre le cache efficace.

2. Y a-t-il des structures de données particulières à utiliser / éviter, ou y a-t-il un moyen particulier d'accéder aux membres de cette structure, etc. pour rendre le cache de code efficace.

3. Y a-t-il des constructions de programme (if, for, switch, break, goto, ...), un flux de code (pour à l'intérieur d'un if, si à l'intérieur d'un for, etc ...) à suivre / éviter dans ce domaine?

J'ai hâte d'entendre des expériences individuelles liées à la création d'un code efficace pour le cache en général. Il peut s'agir de tout langage de programmation (C, C ++, Assembly, ...), de toute cible matérielle (ARM, Intel, PowerPC, ...), de tout OS (Windows, Linux, S ymbian, ...), etc. .

La variété aidera à mieux la comprendre en profondeur.

Le cache est là pour réduire le nombre de calages du processeur en attendant qu'une demande de mémoire soit satisfaite (évitant la latence de la mémoire ), et comme second effet, éventuellement pour réduire la quantité globale de données à transférer (en préservant bande passante mémoire ).

Les techniques pour éviter de souffrir de latence de récupération de la mémoire sont généralement la première chose à considérer, et elles aident parfois beaucoup. La bande passante mémoire limitée est également un facteur limitant, en particulier pour les applications multicores et multithread où de nombreux threads souhaitent utiliser le bus mémoire. Un ensemble différent de techniques permet de résoudre ce dernier problème.

L'amélioration de la localité spatiale signifie que vous vous assurez que chaque ligne de cache est pleinement utilisée une fois qu'elle a été mappée à un cache. Lorsque nous avons examiné divers benchmarks standard, nous avons vu qu'une grande partie surprenante de ceux-ci n'utilisent pas 100% des lignes de cache récupérées avant que les lignes de cache ne soient expulsées.

L'amélioration de l'utilisation de la ligne de cache aide à trois égards:

• Il a tendance à contenir des données plus utiles dans le cache, augmentant essentiellement la taille effective du cache.
• Il a tendance à contenir des données plus utiles dans la même ligne de cache, ce qui augmente la probabilité que les données demandées puissent être trouvées dans le cache.
• Cela réduit les besoins en bande passante mémoire, car il y aura moins de récupérations.

Les techniques courantes sont:

• Utilisez des types de données plus petits
• Organisez vos données pour éviter les trous d'alignement (le tri des membres de votre structure par taille décroissante est un moyen)
• Méfiez-vous de l'allocateur de mémoire dynamique standard, qui peut introduire des trous et répartir vos données dans la mémoire lors de son échauffement.
• Assurez-vous que toutes les données adjacentes sont effectivement utilisées dans les boucles actives. Sinon, envisagez de diviser les structures de données en composants chauds et froids, afin que les boucles chaudes utilisent des données chaudes.
• évitez les algorithmes et les structures de données qui présentent des modèles d'accès irréguliers et privilégiez les structures de données linéaires.

Nous devons également noter qu'il existe d'autres moyens de masquer la latence de la mémoire que d'utiliser des caches.

Processeur moderne: s ont souvent un ou plusieurs prélecteurs matériels . Ils s'entraînent sur les ratés dans une cache et tentent de repérer les régularités. Par exemple, après quelques échecs sur les lignes de cache suivantes, le pré-récupérateur hw commencera à récupérer les lignes de cache dans le cache, anticipant les besoins de l'application. Si vous avez un modèle d'accès régulier, le prefetcher matériel fait généralement un très bon travail. Et si votre programme n'affiche pas les modèles d'accès réguliers, vous pouvez améliorer les choses en ajoutant vous-même des instructions de prélecture .

Regrouper les instructions de telle sorte que celles qui manquent toujours dans le cache se produisent à proximité les unes des autres, le processeur peut parfois chevaucher ces récupérations de sorte que l'application ne supporte qu'un seul coup de latence ( parallélisme au niveau de la mémoire ).

Pour réduire la pression globale du bus mémoire, vous devez commencer à adresser ce que l'on appelle la localité temporelle . Cela signifie que vous devez réutiliser les données alors qu'elles n'ont toujours pas été expulsées du cache.

La fusion de boucles qui touchent les mêmes données ( fusion de boucles ) et l'utilisation de techniques de réécriture connues sous le nom de mosaïque ou de blocage visent toutes à éviter ces extractions de mémoire supplémentaires.

Bien qu'il existe quelques règles empiriques pour cet exercice de réécriture, vous devez généralement considérer attentivement les dépendances de données transportées par boucle, pour vous assurer que vous n'affectez pas la sémantique du programme.

Ces choses sont vraiment payantes dans le monde multicœur, où vous ne verrez généralement pas beaucoup d'améliorations de débit après l'ajout du deuxième thread.

Je ne peux pas croire qu'il n'y ait pas plus de réponses à cela. Quoi qu'il en soit, un exemple classique est d'itérer un tableau multidimensionnel "à l'envers":

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

La raison pour laquelle le cache est inefficace est que les processeurs modernes chargeront la ligne de cache avec des adresses mémoire «proches» de la mémoire principale lorsque vous accédez à une seule adresse mémoire. Nous parcourons les lignes «j» (externes) dans le tableau de la boucle interne, donc pour chaque voyage à travers la boucle interne, la ligne de cache provoquera le vidage et le chargement d'une ligne d'adresses proches du [ j] [i] entrée. Si cela est remplacé par l'équivalent:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Cela fonctionnera beaucoup plus vite.

Les règles de base sont en fait assez simples. Là où cela devient délicat, c'est dans la façon dont ils s'appliquent à votre code.

La cache fonctionne sur deux principes: la localité temporelle et la localité spatiale. Le premier est l'idée que si vous avez récemment utilisé un certain morceau de données, vous en aurez probablement besoin à nouveau bientôt. Ce dernier signifie que si vous avez récemment utilisé les données à l'adresse X, vous aurez probablement bientôt besoin de l'adresse X + 1.

Le cache essaie d'accommoder cela en se souvenant des morceaux de données les plus récemment utilisés. Il fonctionne avec des lignes de cache, généralement d'une taille d'environ 128 octets, donc même si vous n'avez besoin que d'un seul octet, toute la ligne de cache qui le contient est tirée dans le cache. Donc, si vous avez besoin de l'octet suivant par la suite, il sera déjà dans le cache.

Et cela signifie que vous voudrez toujours que votre propre code exploite autant que possible ces deux formes de localité. Ne sautez pas partout dans la mémoire. Faites autant de travail que possible sur une petite zone, puis passez à la suivante, et faites autant de travail que possible.

Un exemple simple est le parcours de tableau 2D que la réponse de 1800 a montré. Si vous le parcourez une ligne à la fois, vous lisez la mémoire de manière séquentielle. Si vous le faites par colonne, vous lirez une entrée, puis sauterez à un emplacement complètement différent (le début de la ligne suivante), lirez une entrée et sauterez à nouveau. Et lorsque vous reviendrez enfin à la première ligne, elle ne sera plus dans le cache.

La même chose s'applique au code. Les sauts ou les branches signifient une utilisation moins efficace du cache (car vous ne lisez pas les instructions séquentiellement, mais sautez vers une adresse différente). Bien sûr, de petites instructions if ne changeront probablement rien (vous ne sautez que quelques octets, vous vous retrouverez donc toujours dans la région mise en cache), mais les appels de fonction impliquent généralement que vous passez à un tout autre adresse qui ne peut pas être mise en cache. À moins qu'il n'ait été appelé récemment.

Cependant, l'utilisation du cache d'instructions est généralement beaucoup moins problématique. Ce dont vous devez généralement vous soucier, c'est le cache de données.

Dans une structure ou une classe, tous les membres sont disposés de manière contiguë, ce qui est bien. Dans un tableau, toutes les entrées sont également disposées de manière contiguë. Dans les listes chaînées, chaque nœud est alloué à un emplacement complètement différent, ce qui est mauvais. Les pointeurs en général ont tendance à pointer vers des adresses non liées, ce qui entraînera probablement un échec du cache si vous le déréférencer.

Et si vous souhaitez exploiter plusieurs cœurs, cela peut devenir vraiment intéressant, car généralement, un seul processeur peut avoir une adresse donnée dans son cache L1 à la fois. Donc, si les deux cœurs accèdent constamment à la même adresse, il en résultera des échecs constants dans le cache, car ils se disputent l'adresse.

Je recommande de lire l'article en 9 parties Ce que tout programmeur devrait savoir sur la mémoire par Ulrich Drepper si vous êtes intéressé par la façon dont la mémoire et le logiciel interagissent. Il est également disponible au format PDF de 104 pages .

Les sections particulièrement pertinentes à cette question pourraient être la partie 2 (caches CPU) et la partie 5 (ce que les programmeurs peuvent faire - optimisation du cache).

Outre les modèles d'accès aux données, la taille des données est un facteur majeur du code convivial pour le cache . Moins de données signifie plus de données dans le cache.

C'est principalement un facteur avec les structures de données alignées sur la mémoire. La sagesse «conventionnelle» dit que les structures de données doivent être alignées aux limites des mots car le processeur ne peut accéder qu'à des mots entiers, et si un mot contient plus d'une valeur, vous devez faire un travail supplémentaire (lecture-modification-écriture au lieu d'une simple écriture) . Mais les caches peuvent complètement invalider cet argument.

De même, un tableau booléen Java utilise un octet entier pour chaque valeur afin de permettre d'opérer directement sur des valeurs individuelles. Vous pouvez réduire la taille des données d'un facteur 8 si vous utilisez des bits réels, mais l'accès aux valeurs individuelles devient alors beaucoup plus complexe, nécessitant des opérations de décalage de bits et de masquage (la BitSetclasse fait cela pour vous). Cependant, en raison des effets de cache, cela peut encore être considérablement plus rapide que d'utiliser un booléen [] lorsque le tableau est grand. IIRC I a une fois réalisé une accélération d'un facteur 2 ou 3 de cette façon.

La structure de données la plus efficace pour un cache est un tableau. Les caches fonctionnent mieux si votre structure de données est disposée séquentiellement, car les processeurs lisent des lignes de cache entières (généralement 32 octets ou plus) à la fois à partir de la mémoire principale.

Tout algorithme qui accède à la mémoire dans un ordre aléatoire supprime les caches car il a toujours besoin de nouvelles lignes de cache pour accueillir la mémoire à accès aléatoire. D'un autre côté, un algorithme, qui s'exécute séquentiellement dans un tableau, est préférable car:

1. Cela donne au CPU une chance de lire à l'avance, par exemple mettre plus de mémoire dans le cache, qui sera accessible plus tard. Cette lecture anticipée augmente considérablement les performances.

2. L'exécution d'une boucle serrée sur un grand tableau permet également au processeur de mettre en cache le code s'exécutant dans la boucle et, dans la plupart des cas, vous permet d'exécuter un algorithme entièrement à partir de la mémoire cache sans avoir à bloquer l'accès à la mémoire externe.

Un exemple que j'ai vu utilisé dans un moteur de jeu était de déplacer des données hors des objets vers leurs propres tableaux. Un objet de jeu soumis à la physique peut également contenir de nombreuses autres données. Mais pendant la boucle de mise à jour physique, tout le moteur se souciait des données sur la position, la vitesse, la masse, la boîte englobante, etc. Donc tout cela a été placé dans ses propres tableaux et optimisé autant que possible pour SSE.

Ainsi, pendant la boucle de physique, les données de physique ont été traitées dans l'ordre des tableaux en utilisant des mathématiques vectorielles. Les objets du jeu utilisaient leur ID d'objet comme index dans les différents tableaux. Ce n'était pas un pointeur car les pointeurs pouvaient devenir invalides si les tableaux devaient être déplacés.

À bien des égards, cela violait les modèles de conception orientés objet, mais cela rendait le code beaucoup plus rapide en plaçant les données proches les unes des autres qui devaient être exploitées dans les mêmes boucles.

Cet exemple est probablement obsolète car je pense que la plupart des jeux modernes utilisent un moteur physique prédéfini comme Havok.

Un seul article l'a abordé, mais un gros problème se pose lors du partage de données entre processus. Vous voulez éviter que plusieurs processus tentent de modifier la même ligne de cache simultanément. Quelque chose à surveiller ici est le partage «faux», où deux structures de données adjacentes partagent une ligne de cache et les modifications apportées à l'une invalident la ligne de cache pour l'autre. Cela peut entraîner des déplacements inutilement des lignes de cache entre les caches de processeur partageant les données sur un système multiprocesseur. Une façon d'éviter cela est d'aligner et de remplir les structures de données pour les placer sur des lignes différentes.

Une remarque à "l'exemple classique" par l'utilisateur 1800 INFORMATION (trop long pour un commentaire)

Je voulais vérifier les différences de temps pour deux ordres d'itération ("outter" et "inner"), j'ai donc fait une expérience simple avec un grand tableau 2D:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

et le deuxième cas avec les forboucles échangées.

La version la plus lente («x first») était de 0,88 sec et la plus rapide, de 0,06 sec. C'est le pouvoir de la mise en cache :)

J'ai utilisé gcc -O2et les boucles n'étaient toujours pas optimisées. Le commentaire de Ricardo selon lequel "la plupart des compilateurs modernes peuvent comprendre cela par eux-mêmes" ne tient pas

Je peux répondre (2) en disant que dans le monde C ++, les listes liées peuvent facilement tuer le cache du processeur. Les tableaux sont une meilleure solution lorsque cela est possible. Aucune expérience pour savoir si la même chose s'applique à d'autres langues, mais il est facile d'imaginer que les mêmes problèmes se poseraient.

Le cache est organisé en "lignes de cache" et la mémoire (réelle) est lue et écrite en blocs de cette taille.

Les structures de données contenues dans une seule ligne de cache sont donc plus efficaces.

De même, les algorithmes qui accèdent à des blocs de mémoire contigus seront plus efficaces que les algorithmes qui sautent dans la mémoire dans un ordre aléatoire.

Malheureusement, la taille de la ligne de cache varie considérablement d'un processeur à l'autre, il n'y a donc aucun moyen de garantir qu'une structure de données optimale sur un processeur le sera sur n'importe quel autre.

Se demander comment créer un code, un cache efficace-cache convivial et la plupart des autres questions, c'est généralement se demander comment optimiser un programme, c'est parce que le cache a un impact si énorme sur les performances que tout programme optimisé est celui qui est cache compatible avec le cache efficace.

Je suggère de lire sur l'optimisation, il y a quelques bonnes réponses sur ce site. En termes de livres, je recommande sur les systèmes informatiques: la perspective d'un programmeur qui contient un texte fin sur l'utilisation correcte du cache.

(btw - aussi mauvais qu'un manque de cache peut être, il y a pire - si un programme pagine à partir du disque dur ...)

Il y a eu beaucoup de réponses sur des conseils généraux comme la sélection de la structure de données, le modèle d'accès, etc. Ici, je voudrais ajouter un autre modèle de conception de code appelé pipeline logiciel qui utilise la gestion active du cache.

L'idée est empruntée à d'autres techniques de pipelining, par exemple le pipelining d'instructions CPU.

Ce type de modèle s'applique le mieux aux procédures qui

1. pourrait être décomposé en plusieurs sous-étapes raisonnables, S [1], S [2], S [3], ... dont le temps d'exécution est à peu près comparable au temps d'accès RAM (~ 60-70ns).
2. prend un lot d'entrées et effectue les étapes multiples susmentionnées pour obtenir le résultat.

Prenons un cas simple où il n'y a qu'une seule sous-procédure. Normalement, le code voudrait:

def proc(input):
    return sub-step(input))

Pour obtenir de meilleures performances, vous souhaiterez peut-être transmettre plusieurs entrées à la fonction dans un lot afin d'amortir la surcharge d'appel de fonction et d'augmenter également la localité du cache de code.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Cependant, comme indiqué précédemment, si l'exécution de l'étape est à peu près la même que le temps d'accès à la RAM, vous pouvez encore améliorer le code à quelque chose comme ceci:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

Le flux d'exécution ressemblerait à ceci:

1. prefetch (1) demande au CPU de pré-lire l'entrée [1] dans le cache, où l'instruction de prélecture prend P cycles elle-même et retourne, et en arrière-plan, l'entrée [1] arriverait dans le cache après R cycles.
2. works_on (0) manque à froid sur 0 et travaille dessus, ce qui prend M
3. prefetch (2) émet une autre récupération
4. works_on (1) si P + R <= M, alors les entrées [1] doivent être dans le cache déjà avant cette étape, évitez ainsi un échec du cache de données
5. works_on (2) ...

Il pourrait y avoir plus d'étapes impliquées, alors vous pouvez concevoir un pipeline à plusieurs étapes tant que le timing des étapes et la latence d'accès à la mémoire correspondent, vous souffrirez de peu de manque de code / cache de données. Cependant, ce processus doit être réglé avec de nombreuses expériences pour trouver le bon regroupement d'étapes et le temps de prélecture. En raison de l'effort requis, il voit une plus grande adoption dans le traitement de flux de données / paquets haute performance. Un bon exemple de code de production peut être trouvé dans la conception du pipeline DPDK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Chapitre 21.2.4.3. Pipeline Enqueue.

Plus d'informations peuvent être trouvées:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Écrivez votre programme pour prendre une taille minimale. C'est pourquoi ce n'est pas toujours une bonne idée d'utiliser les optimisations -O3 pour GCC. Il prend une taille plus grande. Souvent, -Os est aussi bon que -O2. Tout dépend du processeur utilisé. YMMV.

Travaillez avec de petits morceaux de données à la fois. C'est pourquoi des algorithmes de tri moins efficaces peuvent s'exécuter plus rapidement que le tri rapide si l'ensemble de données est volumineux. Trouvez des moyens de diviser vos grands ensembles de données en plus petits. D'autres l'ont suggéré.

Afin de vous aider à mieux exploiter la localité temporelle / spatiale des instructions, vous voudrez peut-être étudier comment votre code est converti en assembly. Par exemple:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Les deux boucles produisent des codes différents même si elles ne font qu'analyser un tableau. Dans tous les cas, votre question est très spécifique à l'architecture. Ainsi, votre seul moyen de contrôler étroitement l'utilisation du cache est de comprendre le fonctionnement du matériel et d'optimiser votre code pour celui-ci.

En plus d'aligner votre structure et vos champs, si votre structure est allouée au tas, vous voudrez peut-être utiliser des allocateurs qui prennent en charge les allocations alignées; comme _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); sinon vous pourriez avoir un faux partage aléatoire; rappelez-vous que dans Windows, le tas par défaut a un alignement de 16 octets.