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

Question

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

1. Comment rendre le code, le cache efficace/cache convivial (plus de hits de cache, le moins de misses de cache possible) ? Des deux points de vue, cache de données et cache de programme (cache d'instructions), c'est-à-dire quels sont les éléments de votre code, liés aux structures de données et aux constructions de code, dont vous devez prendre soin pour le rendre efficace en termes de cache.

2. Y a-t-il des structures de données particulières que l'on doit utiliser/éviter, ou une manière particulière d'accéder aux membres de cette structure etc... pour rendre le code cache efficace.

3. Y a-t-il des constructions de programme (if, for, switch, break, goto,...), du code-flow (for dans un if, if dans un for, etc ...) à suivre/éviter dans ce domaine ?

Je suis impatient d'entendre les expériences individuelles liées à la création d'un code efficace en matière de cache en général. Il peut s'agir de n'importe quel langage de programmation (C, C++, Assembly, ...), de n'importe quelle cible matérielle (ARM, Intel, PowerPC, ...), de n'importe quel système d'exploitation (Windows, Linux, S ymbian, ...), etc.

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

Answer 1

Le cache est là pour réduire le nombre de fois où l'unité centrale de traitement (UC) s'arrête en attendant qu'une demande de mémoire soit satisfaite (en évitant les problèmes de mémoire). latence ), et comme deuxième effet, éventuellement pour réduire la quantité globale de données qui doivent être transférées (en préservant la mémoire bande passante ).

Les techniques permettant d'éviter de souffrir de la latence de récupération de la mémoire sont généralement la première chose à prendre en compte, et elles sont parfois très utiles. La bande passante limitée de la mémoire est également un facteur limitant, en particulier pour les multicores et les applications multithreads où de nombreux threads veulent utiliser le bus mémoire. Un ensemble différent de techniques permet de résoudre ce dernier problème.

Amélioration de localité spatiale signifie que vous vous assurez que chaque ligne de cache est utilisée dans son intégralité une fois qu'elle a été mappée à un cache. Lorsque nous avons examiné divers benchmarks standard, nous avons constaté qu'une fraction étonnamment importante d'entre eux ne parviennent pas à utiliser 100% des lignes de cache extraites avant que celles-ci ne soient évincées.

L'amélioration de l'utilisation des lignes de cache est utile à trois égards :

• Il tend à placer plus de données utiles dans le cache, ce qui augmente essentiellement la taille effective du cache.
• Il a tendance à faire tenir plus de données utiles dans la même ligne de cache, ce qui augmente la probabilité que les données demandées se trouvent dans le cache.
• Cela réduit les besoins en bande passante de la mémoire, car il y aura moins de recherches.

Les techniques courantes sont :

• Utiliser des types de données plus petits
• Organisez vos données pour éviter les trous d'alignement (trier les membres de votre structure par taille décroissante est une façon de le faire).
• Méfiez-vous de l'allocateur de mémoire dynamique standard, qui peut introduire des trous et disperser vos données dans la mémoire pendant qu'elle se réchauffe.
• Assurez-vous que toutes les données adjacentes sont effectivement utilisées dans les boucles chaudes. Sinon, envisagez de diviser les structures de données en composants chauds et froids, de sorte que les boucles chaudes utilisent les données chaudes.
• éviter les algorithmes et les structures de données qui présentent des schémas d'accès irréguliers, et favoriser les structures de données linéaires.

Il convient également de noter qu'il existe d'autres moyens de masquer la latence de la mémoire que l'utilisation des caches.

Les CPU modernes ont souvent un ou plusieurs préempteurs matériels . Ils s'entraînent sur les manques dans un cache et essaient de repérer des régularités. Par exemple, après quelques ratés sur des lignes de cache ultérieures, le préprocesseur matériel commencera à récupérer des lignes de cache dans le cache, anticipant ainsi les besoins de l'application. Si vous avez un modèle d'accès régulier, le préfetcher matériel fait généralement un très bon travail. Et si votre programme n'affiche pas des schémas d'accès réguliers, vous pouvez améliorer les choses en ajoutant des lignes de cache. instructions de préextraction vous-même.

En regroupant les instructions de manière à ce que celles qui manquent toujours dans le cache soient proches les unes des autres, le CPU peut parfois chevaucher ces recherches de sorte que l'application ne subit qu'un seul coup de latence ( Parallélisme au niveau de la mémoire ).

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

Fusionner les boucles qui touchent les mêmes données ( fusion de boucles ), et en utilisant des techniques de réécriture connues sous le nom de carrelage o blocage tous s'efforcent d'éviter ces recherches supplémentaires en mémoire.

Bien qu'il existe certaines règles empiriques pour cet exercice de réécriture, vous devez généralement examiner attentivement les dépendances des données portées par les boucles, afin de vous assurer que vous n'affectez pas la sémantique du programme.

Ce sont ces éléments qui sont vraiment payants dans le monde multicore, où l'on ne voit généralement pas d'amélioration du débit après l'ajout d'un deuxième thread.

Answer 2

Je ne peux pas croire qu'il n'y ait pas plus de réponses à cette question. Quoi qu'il en soit, un exemple classique consiste à 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 cette méthode est inefficace pour le cache est que les processeurs modernes chargent la ligne de cache avec des adresses de mémoire "proches" de la mémoire principale lorsque vous accédez à une seule adresse de mémoire. Nous itérons à travers les "j" lignes (extérieures) du tableau dans la boucle interne, donc à chaque passage dans la boucle interne, la ligne de cache sera vidée et chargée avec une ligne d'adresses qui sont proches de l'entrée [j][i]. Si l'on remplace cette ligne par l'équivalent :

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

Il fonctionnera beaucoup plus rapidement.

Answer 3

Les règles de base sont en fait assez simples. Là où les choses se compliquent, c'est dans la manière dont elles s'appliquent à votre code.

Le cache fonctionne sur deux principes : La localité temporelle et la localité spatiale. Le premier principe repose sur l'idée que si vous avez récemment utilisé une certaine quantité de données, vous en aurez probablement à nouveau besoin prochainement. Le second principe 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 de s'adapter à cela en se souvenant des derniers morceaux de données utilisés. Il fonctionne avec des lignes de cache, généralement d'une taille de 128 octets environ, de sorte que même si vous n'avez besoin que d'un seul octet, la ligne de cache entière qui le contient est placée dans le cache. Ainsi, si vous avez besoin de l'octet suivant par la suite, il sera déjà dans le cache.

Cela signifie que vous voudrez toujours que votre propre code exploite ces deux formes de localité autant que possible. Ne sautez pas partout dans la mémoire. Travaillez autant que vous le pouvez sur une petite zone, puis passez à la suivante et travaillez-y autant que vous le pouvez.

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

Il en va de même pour le code. Les sauts ou les branches signifient une utilisation moins efficace du cache (car vous ne lisez pas les instructions séquentiellement, mais vous sautez à une adresse différente). Bien sûr, de petites instructions if ne changeront probablement rien (vous ne sautez que quelques octets, donc vous finirez toujours dans la région de cache), mais les appels de fonction impliquent généralement que vous sautez à une adresse complètement différente qui peut ne pas être mise en cache. Sauf si elle a été appelée récemment.

L'utilisation du cache d'instruction est généralement beaucoup moins problématique. Ce dont vous devez généralement vous préoccuper, c'est du 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 lié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 sans rapport, ce qui entraînera probablement un manque de cache si vous déréférencez.

Et si vous voulez exploiter plusieurs cœurs, cela peut devenir très intéressant, car en général, 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 manques constants de cache, car ils se battent pour l'adresse.

Answer 4

Je vous recommande de lire l'article en 9 parties Ce que tout programmeur devrait savoir sur la mémoire d'Ulrich Drepper si vous êtes intéressé par l'interaction entre la mémoire et les logiciels. Il est également disponible sous forme de un PDF de 104 pages .

Les sections particulièrement pertinentes pour cette question pourraient être Partie 2 (caches des CPU) et Partie 5 (Ce que les programmeurs peuvent faire - optimisation du cache).

Answer 5

En dehors des schémas d'accès aux données, un facteur important pour un code respectueux de la mémoire cache est celui des données. taille . Moins de données, c'est plus de données qui rentrent 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 parce que le CPU 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 pouvoir opérer directement sur les 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 fonction BitSet le fait pour vous). Cependant, en raison des effets de cache, cette méthode peut toujours être considérablement plus rapide que l'utilisation d'un boolean[] lorsque le tableau est grand. Je crois qu'une fois j'ai obtenu un gain de vitesse d'un facteur 2 ou 3 de cette manière.