Code de conception pour tenir dans le cache du processeur?

https://stackoverflow.com/questions/1822295

10-07-2019
|

Question

Lors de l’écriture de simulations, mon ami dit qu’il aime essayer d’écrire le programme assez petit pour s’insérer dans le cache. Cela a-t-il une réelle signification? Je comprends que le cache est plus rapide que la RAM et la mémoire principale. Est-il possible de spécifier que vous voulez que le programme s'exécute à partir du cache ou au moins charge les variables dans le cache? Nous écrivons des simulations, donc tout gain en performance / optimisation est un énorme avantage.

Si vous connaissez de bons liens expliquant la mise en cache de la CPU, dirigez-moi dans cette direction.

La solution

Au moins avec un processeur de bureau typique, vous ne pouvez pas vraiment en dire beaucoup sur l'utilisation du cache directement. Vous pouvez toujours essayer d'écrire un code convivial au cache. Du côté du code, cela signifie souvent que dérouler des boucles (pour un exemple évident) est rarement utile: il développe le code et un processeur moderne minimise généralement le temps système nécessaire au bouclage. Vous pouvez généralement en faire plus du côté des données pour améliorer la localité de référence, vous protéger contre le partage frauduleux (par exemple, deux données fréquemment utilisées qui essaieront d’utiliser la même partie du cache, tandis que d’autres seront inutilisées).

Modifier (pour rendre certains points un peu plus explicites):

Un processeur typique a un certain nombre de caches différents. Un processeur de bureau moderne aura généralement au moins 2 et souvent 3 niveaux de cache. Par accord (au moins presque) universel, "niveau 1" est le cache " le plus proche " aux éléments de traitement, et les nombres montent à partir de là (le niveau 2 est le suivant, le niveau 3 après cela, etc.)

Dans la plupart des cas, le cache de niveau 1 est divisé en deux moitiés: un cache d’instructions et un cache de données (le processeur Intel 486 est presque la seule exception à ma connaissance, avec un seul cache pour les deux). instructions et données - mais il est tellement obsolète qu’il ne mérite probablement pas beaucoup de réflexion).

Dans la plupart des cas, un cache est organisé en un ensemble de "lignes". Le contenu d'un cache est normalement lu, écrit et suivi une ligne à la fois. En d'autres termes, si la CPU doit utiliser les données d'une partie de la ligne de cache, cette dernière est lue à partir du niveau de stockage immédiatement inférieur. Les caches les plus proches de la CPU sont généralement plus petits et ont des lignes de cache plus petites.

Cette architecture de base présente la plupart des caractéristiques d’un cache qui jouent un rôle important dans l’écriture de code. Autant que possible, vous voulez lire quelque chose dans le cache une fois, tout faire avec ce que vous allez faire, puis passer à autre chose.

Cela signifie que lorsque vous traitez des données, il est généralement préférable de lire une quantité de données relativement petite (assez peu pour tenir dans le cache), de traiter autant de données que vous le pouvez, puis de passer à l'étape suivante. bloc de données suivant. Des algorithmes tels que Quicksort qui cassent rapidement de grandes quantités d’informations en éléments de plus en plus petits le font plus ou moins automatiquement, de sorte qu’ils ont tendance à être relativement conviviaux pour le cache, presque indépendamment des détails précis du cache.

Ceci a également des implications sur la manière dont vous écrivez du code. Si vous avez une boucle du genre:

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

Vous ferez généralement mieux de lier autant d’étapes que vous le pouvez jusqu’à la quantité qui tiendra dans le cache. Dès que vous dépassez le cache, les performances peuvent / vont fortement chuter. Si le code de l'étape 3 ci-dessus était suffisamment volumineux pour ne pas entrer dans le cache, il serait généralement préférable de diviser la boucle en deux parties comme celle-ci (si possible):

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

Le déroulement de la boucle est un sujet assez chaudement disputé. D'une part, cela peut conduire à un code beaucoup plus convivial pour le processeur, réduisant ainsi la surcharge des instructions exécutées pour la boucle elle-même. Dans le même temps, il peut (et généralement augmente) la taille du code, ce qui rend le cache relativement peu convivial. D'après mon expérience personnelle, dans les référentiels synthétiques qui tendent à traiter de très petites quantités de données sur de très grandes quantités de données, le tirage en boucle vous apporte beaucoup. Dans un code plus pratique, où vous avez tendance à avoir plus de traitement sur une donnée individuelle, vous en gagnez beaucoup moins - et un débordement du cache entraînant une perte de performance sérieuse n'est pas particulièrement rare.

La taille du cache de données est également limitée. Cela signifie que vous souhaitez généralement que vos données soient compressées de manière aussi dense que possible, de sorte que le plus grand nombre possible de données puisse tenir dans le cache. Pour ne citer qu'un exemple évident, une structure de données liée à des pointeurs doit gagner un peu en complexité de calcul pour constituer

Autres conseils

Voici un lien vers un très bon du papier sur des caches / Optimisation de la mémoire par Christer Ericsson (de la gloire God of War I / II / III). Il a quelques années mais reste très pertinent.

What Every Programmer est un document utile qui vous en dira plus que tout ce que vous avez toujours voulu savoir sur les caches. Devrait connaître la mémoire par Ulrich Drepper. bcbbb = false "rel =" noreferrer "> Hennessey le couvre très bien. Christer et Mike Acton ont également écrit beaucoup de choses intéressantes à ce sujet.

Je pense que vous devriez vous préoccuper davantage du cache de données que du cache d'instructions & # 8212; D'après mon expérience, les échecs de décaches sont plus fréquents, plus douloureux et plus utilement corrigés.

MISE À JOUR: 13/01/2014 Selon ce concepteur de puces expérimenté, les erreurs de cache sont désormais LE facteur dominant en termes de performances du code. Nous remontons donc pratiquement au milieu des années 80 et à 286 puces rapides en termes de goulets d'étranglement relatifs en termes de charge, de stockage et d'entier. arithmétique, et cache des ratés.

Un cours intensif en matériel moderne de Cliff Click @ Azul . . . . .

--- nous vous renvoyons maintenant à votre programme régulier ---

Parfois, un exemple vaut mieux qu'une description de la façon de faire quelque chose. Dans cet esprit, voici un exemple particulièrement réussi de la façon dont j'ai modifié un code pour une meilleure utilisation sur les caches de puces. Cela a été fait il y a quelque temps sur un processeur 486 et ce dernier a migré vers un processeur Pentium de 1ère génération. L'effet sur les performances était similaire.

Exemple: mappage des indices

Voici un exemple d'une technique que j'ai utilisée pour insérer des données dans le cache de la puce et qui a un utilitaire à usage général.

J'avais un vecteur à double float long de 1 250 éléments, ce qui correspondait à une courbe épidémiologique avec de très longues queues. Le " intéressant " une partie de la courbe ne contenait que 200 valeurs uniques, mais je ne voulais pas de test if à deux faces () afin de gâcher le pipeline de la CPU (donc les longues queues, qui pourraient utiliser comme indices les valeurs les plus extrêmes de Monte Carlo le code cracherait), et j’avais besoin de la logique de prédiction de branche pour une douzaine d’autres tests conditionnels à l’intérieur du "point chaud". dans le code.

J'ai opté pour un schéma dans lequel j'ai utilisé un vecteur d'ints de 8 bits comme indice dans le double vecteur, que j'ai raccourci à 256 éléments. Les valeurs minuscules avaient toutes les mêmes valeurs avant 128 devant zéro et 128 après zéro. Par conséquent, à l'exception des 256 valeurs du milieu, elles pointaient toutes vers la première ou la dernière valeur du vecteur double.

Cela a réduit la mémoire requise à 2k pour les doublons et à 1 250 octets pour les indices de 8 bits. Cela a réduit de 10 000 octets à 3 298. Comme le programme a passé 90% ou plus de son temps dans cette boucle interne, les 2 vecteurs n'ont jamais été sortis du cache de données de 8k. Le programme a immédiatement doublé sa performance. Ce code a été touché environ 100 milliards de fois dans le processus de calcul de la valeur de la SV pour un million de prêts hypothécaires.

Étant donné que les queues de la courbe ont rarement été touchées, il est fort possible que seuls les 200 à 300 éléments centraux du petit vecteur int aient été conservés dans la mémoire cache, ainsi que 160 à 240 doubles du milieu représentant 1 / 8ème de pourcentages d’intérêt. . Il s’agissait d’une augmentation remarquable des performances, réalisée l’après-midi, d’un programme que j’avais passé sur une année à optimiser.

Je suis d’accord avec Jerry, car c’est mon expérience aussi, dire que pencher le code vers le cache d’instructions a beaucoup moins de succès que l’optimisation pour le / les cache (s) de données. C’est une des raisons pour lesquelles je pense que les caches courants d’AMD ne sont pas aussi utiles que les caches de données et d’instructions distincts d’Intel. IE: vous ne voulez pas que les instructions cachent le cache, cela n’aide en rien. Cela est en partie dû au fait que les jeux d'instructions de l'ICCA ont été créés à l'origine pour compenser la grande différence entre les vitesses de processeur et de mémoire, et à l'exception d'une aberration à la fin des années 80, cela a pratiquement toujours été vrai.

Une autre technique de prédilection que j'utilise pour favoriser le cache de données et le cache d’instructions consiste à utiliser beaucoup de bits-ints dans les définitions de structure et les plus petites tailles de données possibles en général. Masquer un int de 4 bits pour tenir le mois de l'année, ou 9 bits pour tenir le jour de l'année, etc., etc., nécessite que les masques d'utilisation de la CPU masquent les entiers de l'hôte utilisés par les bits, ce qui réduit la augmente la taille du cache et du bus, mais nécessite plus d’instructions. Bien que cette technique produise un code qui ne fonctionne pas aussi bien sur des tests synthétiques, sur

Cela servira principalement de paramètre fictif jusqu'à ce que j'aie le temps de rendre justice à ce sujet, mais je voulais partager ce que je considère être une étape véritablement révolutionnaire: l'introduction d'instructions de manipulation de bits dédiées dans le nouveau microprocesseur Intel Hazwell.

Cela est devenu douloureusement évident lorsque j'ai écrit du code ici sur StackOverflow pour inverser les bits d'un tableau de 4096 bits qui plus de 30 ans après l'introduction du PC, les microprocesseurs ne consacrent tout simplement pas beaucoup d'attention ou de ressources à des bits, et cela J'espère que ça va changer. En particulier, j'aimerais voir, pour commencer, le type bool devenir un type de données de bits réel en C / C ++, au lieu du byte ridiculement inutile qu'il est actuellement.

Les nouvelles instructions de manipulation de bits de Hazwell

UPDATE: 29/12/2013

J'ai récemment eu l'occasion d'optimiser un tampon en anneau qui garde en mémoire la demande de 512 utilisateurs de ressources différents sur un système d'une granularité à la milliseconde. Il existe un minuteur qui déclenche chaque milliseconde, qui ajoute la somme des demandes de ressources de la tranche la plus récente et soustrait les demandes de la tranche de la 1 000e heure, comprenant les demandes de ressources datant maintenant de 1 000 millisecondes.

Les vecteurs Head, Tail étaient côte à côte dans la mémoire, sauf lorsque, d’abord, la tête, puis la queue encapsulée et reprise au début du tableau. La tranche (roulante) Summary se trouvait cependant dans un tableau fixe, alloué statiquement, qui n'était pas particulièrement proche de ceux-ci et qui n'était même pas alloué à partir du tas.

Penser à cela et étudier le code avec quelques détails ont retenu mon attention.

Les demandes entrantes ont été ajoutées simultanément aux sections d'en-tête et de résumé, l'une à côté de l'autre, dans des lignes de code adjacentes.
Lorsque le chronomètre s'est déclenché, la queue a été soustraite de la tranche de résumé et les résultats ont été laissés dans la tranche de résumé, comme vous le souhaitiez
La 2e fonction appelée lors du déclenchement de la minuterie a avancé tous les pointeurs desservant la sonnerie. En particulier.... La tête a écrasé la queue, occupant ainsi le même emplacement mémoire La nouvelle queue occupait les 512 emplacements mémoire suivants, ou encapsulée
L'utilisateur souhaitait plus de flexibilité dans le nombre de demandes gérées, de 512 à 4098, voire davantage. Je pensais que le moyen le plus robuste et le plus sûr pour le faire consistait à allier les 1 000 tranches de temps et la tranche de résumé en un bloc de mémoire contigu, de sorte qu'il serait IMPOSSIBLE que la tranche de résumé prenne une longueur différente. que les 1 000 autres tranches de temps.
Compte tenu de ce qui précède, je me suis demandé si je pouvais obtenir davantage de performances si, au lieu de conserver la tranche Résumé au même endroit, je l'avais "roam". entre la tête et la queue, il était donc toujours juste à côté de la tête pour ajouter de nouvelles demandes, et juste à côté de la queue lorsque le chronomètre était déclenché et que les valeurs de la queue devaient être soustraites du résumé.

J’ai fait exactement cela, mais j’ai trouvé quelques optimisations supplémentaires dans le processus. J'ai changé le code qui calculait le résumé glissant de manière à laisser les résultats dans la queue au lieu de la tranche de résumé. Pourquoi? Parce que la toute prochaine fonction exécutait memcpy () pour déplacer la tranche de résumé dans la mémoire occupée par la queue. (bizarre mais vrai, la queue mène la tête jusqu'au bout de l'anneau quand il s'enroule). En laissant les résultats de la sommation dans la queue, je n'ai pas eu à exécuter le memcpy (), il me suffisait d'assigner pTail à pSummary.

De la même manière, la nouvelle tête occupait l’ancien emplacement de mémoire de la tranche récapitulative désormais obsolète. C’est pourquoi j’ai simplement assigné pSummary à pHead et mis à zéro toutes ses valeurs avec un memset.

Ouvrir la voie au bout de l’anneau (vraiment un tambour, large de 512 pistes) était la queue, mais je

La plupart des compilateurs C / C ++ préfèrent optimiser la taille plutôt que la "vitesse". En d’autres termes, un code plus petit s’exécute généralement plus rapidement que le code non déroulé en raison des effets de cache.

Si j'étais vous, je m'assurerais de savoir quelles parties du code sont des points chauds que je définis comme

une boucle serrée ne contenant aucun appel de fonction, car s'il appelle une fonction, le PC passera le plus clair de son temps dans cette fonction,
représente une fraction importante du temps d'exécution (comme > = 10%) que vous pouvez déterminer à l'aide d'un profileur. (Je viens de goûter la pile manuellement.)

Si vous avez un tel point chaud, alors il devrait tenir dans le cache. Je ne sais pas comment vous le dites, mais je suppose que c'est automatique.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow