Qu'est-ce qui est important lors de l'optimisation du cache CPU (en C)?

13

En lisant ces deux questions , je vois que la compréhension du comportement de mise en cache du processeur peut être importante lorsqu'il s'agit de grandes quantités de données en mémoire. Je voudrais comprendre le fonctionnement de la mise en cache pour ajouter un autre outil à ma boîte à outils d'optimisation.

Quels sont les points essentiels sur le fonctionnement du cache CPU pour que je puisse écrire du code qui l'utilise de manière raisonnable? De même, existe-t-il un moyen de profiler le code pour voir si une mauvaise utilisation du cache ralentit les choses?

Timothy Jones
la source
Les caches ne sont pas les mêmes partout; le plus évidemment, ils varient en taille. Ne vous attendez pas à apprendre des secrets profonds, seulement de bonnes pratiques (comme les conseils de Michael Borgwardt).
David Thornley

Réponses:

17
  • Gardez vos données petites si possible
  • Gardez en mémoire les éléments qui seront accessibles ensemble (ou juste après l'autre) les uns à côté des autres
  • En savoir plus sur les paramètres d'optimisation de votre compilateur
  • Lisez ce que chaque programmeur doit savoir sur la mémoire pour plus de détails que vous ne le souhaiteriez
Michael Borgwardt
la source
+1 pour «Gardez les choses accessibles à côté les unes des autres»; c'est celui qu'il est facile d'oublier.
Donal Fellows
Et dites au compilateur d'optimiser.
droite
@WTP: droit - ajouté.
Michael Borgwardt
Aussi, gardez les mutex bien séparés. La modification d'un mutex (doit) vider toutes les lignes de cache dans lesquelles il se trouve, sur tous les CPU. Cela peut être un gros coup de performances si vous avez réussi à obtenir 2-3 mutex dans une seule ligne de cache.
Vatine
12

La complexité de ce problème dépasse la compréhension humaine ces jours-ci. (C'est ainsi depuis les 5 dernières années.) Combinez cela avec le parallélisme à vecteur court (SIMD) et vous avez le sentiment désespéré que l'optimisation du code à la main n'est plus économiquement faisable - non pas que ce ne soit pas possible, mais ce serait ne plus être rentable.

L'approche actuelle consiste à s'appuyer sur l'enseignement des ordinateurs pour optimiser - en faisant des variations de code qui calculent les mêmes réponses avec différentes structures (boucles, structure de données, algorithmes) et en évaluant automatiquement les performances. Les règles pour les transformations de code sont spécifiées avec un modèle mathématique très rigoureux, de sorte que c'est quelque chose que les informaticiens peuvent comprendre et que les ordinateurs peuvent exécuter.

Ce qui suit est un lien publié par Larry OBrien dans l'une de ses réponses .

http://onward-conference.org/2011/images/Pueschel_2011_AutomaticPerformanceProgramming_Onward11.pdf

rwong
la source
2
l'implémentation BLAS de fasttest (GotoBLAS) utilise un code optimisé à la main pour assurer une utilisation maximale du cache pour la multiplication matricielle
quant_dev
2

Il est tout à fait possible de comprendre et d'optimiser les caches. Cela commence par la compréhension du matériel et se poursuit par le contrôle du système. Moins vous aurez de contrôle sur le système, moins vous aurez de chances de réussir. Linux ou Windows exécutant un tas d'applications / threads qui ne sont pas inactifs.

La plupart des caches sont quelque peu similaires dans leurs propriétés, utilisent une partie du champ d'adresse pour rechercher des hits, ont une profondeur (voies) et une largeur (ligne de cache). Certains ont des tampons d'écriture, certains peuvent être configurés pour écrire ou contourner le cache lors des écritures, etc.

Vous devez être parfaitement conscient de toutes les transactions de mémoire en cours qui atteignent ce cache (certains systèmes disposent d'instructions indépendantes et de caches de données facilitant la tâche).

Vous pouvez facilement rendre un cache inutile en ne gérant pas soigneusement votre mémoire. Par exemple, si vous avez plusieurs blocs de données que vous traitez, en espérant les garder en cache, mais ils sont en mémoire à des adresses qui sont même multiples par rapport à la vérification des caches hit / miss, disons 0x10000 0x20000 0x30000, et vous avez plus de ces façons que dans le cache, vous pouvez très rapidement finir par faire quelque chose qui fonctionne assez lentement avec le cache activé, plus lent qu'avec le cache désactivé. Mais changez cela en peut-être 0x10000, 0x21000, 0x32000 et cela pourrait être suffisant pour profiter pleinement du cache, réduisant les expulsions.

En fin de compte, la clé de l'optimisation d'un cache (enfin, à part bien connaître le système) est de conserver toutes les choses dont vous avez besoin de performances dans le cache en même temps, en organisant ces données de sorte qu'il soit possible d'avoir tout cela dans le cache à la fois. Et empêcher des choses comme l'exécution de code, les interruptions et autres événements réguliers ou aléatoires d'expulser des parties importantes de ces données que vous utilisez.

Il en va de même pour le code. C'est un peu plus difficile, car vous devez contrôler les emplacements où se trouve le code pour éviter les collisions avec d'autres codes que vous souhaitez conserver dans le cache. Lors du test / profilage de tout code passant par un cache qui ajoute une seule ligne de code ici et là ou même un seul nop, tout ce qui décale ou modifie les adresses où le code vit d'une compilation à une autre pour le même code, change où les lignes de cache tombent dans ce code et modifient ce qui est expulsé et ce qui ne l'est pas pour les sections critiques.

old_timer
la source
1

Les réponses de nwong et de Michael Borgwardt donnent de bons conseils.

Aussi, faites d'abord confiance aux optimisations du compilateur sur ces problèmes.

Si vous utilisez un compilateur GCC récent, vous pouvez utiliser (avec parcimonie) sa __builtin_prefetchfonction. Voir cette réponse sur stackoverflow.

Basile Starynkevitch
la source