Journal La mémoire, goulot d'étranglement : optimiser le cache processeur.

Posté par  (site web personnel) .
Étiquettes : aucune
0
12
oct.
2005
Dans un journal d'il y a deux semaines, nous fûmes gratifié d'un beau débat sur les chutes de performances dues à la fragmentation mémoire :
https://linuxfr.org/comments/628360.html#628360(...)


Cédric nous explique, https://linuxfr.org/comments/628662.html#628662(...)

"Or on alloue quand meme de la memoire pour l'utiliser et c'est l'utilisation qui compte. Si tes donnees au moment ou tu les utilises sont completement disperse en memoire (fragmente) et non aligne, et bien tu vas facilement te prendre un facteur 100 voir de plus en plus grand avec le temps puisque le rapport entre la vitesse du CPU et la latence memoire a tendance a grandir."


mdlh renchérit https://linuxfr.org/comments/628768.html#628768(...) :

"Pour eviter les trolls, je ne vais pas preciser l'architecture sur laquelle je travaille. Mais je voudrais juste dire que je suis assez souvent face a des cas ou 30% du temps d'execution de l'appli est perdu du a des problemes de cache. Pour les fixer, il faut soit:
- reduire les latences en travaillant sur l'organisation des donnees en memoire de telles sortes que les donnees susceptibles d'etre utilisee en meme temps soient sur des espaces contigus
- rendre le programme tolerant a ces latences en utilisant le fameux "Prefetch", ce qui necessite de pouvoir calculer en avance les adresses memoires utilisees."


Donc la problématique serait la suivante :
Soit une fonction quelconque appelée par un call [ptr], si toutes les données utilisées par cette fonction sont, en terme d'adresse mémoire physique, contigües, alors le prefetch cache hardware aura tendance à charger ces données, au moins dans le cache L2 (?)

Alors il y a deux ou trois choses qui ne sont pas encore claires dans mon esprit :

La mémoire est une matrice, et le temps d'accès à tel ou tel endroit de la mémoire est le même, j'ai donc du mal à comprendre pourquoi les données doivent être absolument alignées pour être chargé dans le cache ? Et alignées comment ? Alignées de sorte à bien tenir dans un registre 32/64 bit ou aligné à plus grosses granulités, par exemple deux grosses chaînes de caractères de 16 Ko ?
Et qu'est-ce que veut dire contigues ?

Prenons un exemple :
Imaginons qu'à partir de deux images on veuille obtenir une seule qui soit la première plus l'autre en transparence (un calque sous gimp en qq sorte).
Pour stocker mon image de manière contigu, Je peux les stocker les unes à côté des autres. Mais si elles font plus de 512 Ko, c'est comme si elle n'étaient pas contigûes : elles ne tiennent pas dans le cache (moins d'un Mo à l'heure actuelle).

Je peux aussi décider de les découper "ligne à ligne" et mettre les lignes des 2 images 2 à 2 contigües : 1024 octet de l'une et à côté je stocke 1024 octets de l'autre, "ligne par ligne". Là peut-être que ça passe ?

Je me met dans un cadre où je ne veux pas toucher aux instructions prefetch des processeurs récent.

Est-ce que le second cas me permet d'être sûr que les données seront bien chargée dans le cache ?

Quel est exactement la politique de chargement du cache réalisée automatiquement par les cpu modernes ?

(Autre question, lors d'un changement de contexte, le cache est-il bien vidé ? )

  • # Lire la doc d'Intel et d'AMD merci

    Posté par  . Évalué à 10.

    Toutes les réponses sont dans les docs d'Intel et d'AMD, néanmoins pour pas avoir l'air trop méchant (quoique ? :P) :

    Soit une fonction quelconque appelée par un call [ptr], si toutes les données utilisées par cette fonction sont, en terme d'adresse mémoire physique, contigües, alors le prefetch cache hardware aura tendance à charger ces données, au moins dans le cache L2 (?)

    Je vois pas le rapport avec un call [ptr]. Si les données utilisées par la fonction sont contigues et si la fonction les utilisent dans l'ordre ou du moins dans un ordre régit par quelques fonctions affines adresse = f(numéro de l'acces mémoire) potentiellement entrelacées (si il n'y en a pas trop), alors le proc detecte qu'il peut etre judicieux de prefetcher et ce met à le faire tout seul comme un grand.
    La chargement dans le cache L2 ou L1 est indépendant de lorigine de la décision de mise en cache (conseil de prefetching ou pas, prefetching automatique, mise en cache classique, etc...).
    Il y a principalement 2 systèmes : inclusif ou les données de L1 sont obligatoirement aussi dans L2 et exclusif, ou les données de L1 ne sont pas dans L2 (sur certains proc il y a moins de L2 que de L1 donc dans ce cas l'exclusivité est obligatoire).
    Les niveaux de cache ont des temps d'accès et potentielement un tas d'auters paramètres qui diffèrent (associativité, taille de lignes, ...).
    Le choix de l'emplacement dans le cache à utiliser pour stocker un truc dans le cache dépend de l'adresse mémoire du truc à stocker, de l'associativité, et généralement d'un algorithme de type pseudo-LRU.

    La mémoire est une matrice, et le temps d'accès à tel ou tel endroit de la mémoire est le même, j'ai donc du mal à comprendre pourquoi les données doivent être absolument alignées pour être chargé dans le cache ?

    Déjà le temps d'accès n'est pas le même pour des accès contigus ou aléatoire. En contigu ca va plus vite, parce que tu n'a pas à transmettre la nouvelle adresse que tu veux charger / stocker et que ya surrement du matos de prefetching aussi dans les controleurs de RAM.

    Et alignées comment ? Alignées de sorte à bien tenir dans un registre 32/64 bit ou aligné à plus grosses granulités, par exemple deux grosses chaînes de caractères de 16 Ko ?
    Et qu'est-ce que veut dire contigues ?

    Les données doivent en général être alignées sur la taille du registre dans lesquels elles vont attérir pour que ca aille plus vite, sinon le proc doit utiliser une unitée de décalage binaire pour les remettre ou il faut. Certains jeu d'instruction (principalement sur RISC et le SIMD de nos braves x86) n'acceptent même pas les accès non alignés (sauf des fois avec des instructions spéciales qui rament encore plus).
    Il y a aussi le problème de la disposition en mémoire (faut-il faire un tableau de structures ou une structure de tableaux ?) et de l'associativité du cache (n-voix, full associative ?) mais j'ai pas spécialement le temps de détailler tout ca.

    Prenons un exemple :
    Imaginons qu'à partir de deux images on veuille obtenir une seule qui soit la première plus l'autre en transparence (un calque sous gimp en qq sorte).
    Pour stocker mon image de manière contigu, Je peux les stocker les unes à côté des autres. Mais si elles font plus de 512 Ko, c'est comme si elle n'étaient pas contigûes : elles ne tiennent pas dans le cache (moins d'un Mo à l'heure actuelle).

    Le cache n'est pas obligé de sotcker des données contigues, y a toutes les notions de tailles de lignes et d'associativité qu'il faut connaitre. Pour une zone mémoire données de la taille d'une ligne, il y a plusieurs lignes de cache dans lesquelles tu peux la stocker (ou tu peux eventuellement la mettre n'importe ou si tu a un cache pleinement associatif).

    Je peux aussi décider de les découper "ligne à ligne" et mettre les lignes des 2 images 2 à 2 contigües : 1024 octet de l'une et à côté je stocke 1024 octets de l'autre, "ligne par ligne". Là peut-être que ça passe ?

    Je me met dans un cadre où je ne veux pas toucher aux instructions prefetch des processeurs récent.

    Sur deux gros blocs comme ça soit contigus soit entrelacés je present que le stockage en ram ne va pas changer grand chose. Le prefteching automatique est capable de gerer plusieurs flux d'accès simultannément. Les problèmes d'associativité ne joueront pas si lalgo accède aux mémoires une seule fois puisque seul leffet de prefetching va apporter une acceleration. Si par contre une succession d'algo est appliqué sur plusieurs images, il peut être interressant de découper en morceau le traitement de l'image pour que les données sur lesquels vont s'appliquer tous les traitements successifs restent en cache. Selon les cas et selon l'associativité une reorganisation en mémoire peut parfois etre necessaire mais c'est rare (c'est surtout lorganisation en arborescences des données multidimensionneles qu'il faut optimiser, nottement en SIMD).

  • # Beaux raisonnements

    Posté par  . Évalué à 10.

    J'admire tous ces beaux raisonnements sur la gestion de la mémoire. Ils sont amha parfaitement pertinents sur une installation temps réel, mono-tâche, ou multi-tâche non préemptif.

    Mais, préemption, segmentation, pagination et mémoire virtuelle remettent, amha, en question tous ces raisonnements ?

    Par exemple, cette assertion:

    ... La mémoire est une matrice, et le temps d'accès à tel ou tel endroit de la mémoire est le même, ...

    n'est plus vraie dans ce mode de fonctionnement. La notion de localité prend une importance considérable: les unités logicielles (au sens sémantique et non pas syntaxique) devraient être contenues dans les limites d'une page (sous Intel et Cie: 4 K0) pour éviter de trop nombreux défauts de pages. Celà tendrait à promouvoir l'utilisation de langage évolué de type objet, malheureusement la localisation dans ce type de langage est, la plupart du temps, uniquement syntaxique. Lors de l'exécution, code et données sont, en général, dans des pages séparées.

    Toujours dans ce mode de fonctionnement, mémoire physique et mémoire logique n'ont pas de correspondance directe: la mémoire physique est obligatoirement fragmentée. Et comme les caches de type L2 travaillent au niveau de la mémoire physique ... C'est le type de fonctionnement sous Linux: 2 segments (kernel, user) et mémoire paginée à 2 niveaux.

    Il est beaucoup plus dommageable pour les performances de gérer de nombreux défauts de page que de gérer des "défaut de cache" (néologisme de mon cru ?). Les défauts de page se gèrent en terme de dizaines de ms, les défaut de cache en terme de dizaines de nanos secondes.

    De toute façon, dans le contexte d'un système d'exploitation multi-tâche préemptif, il ne s'agit pas d'optimiser telle ou telle application, mais d'optimiser l'utilisation globale du couple matériel-logiciel.

  • # remarques

    Posté par  (site web personnel) . Évalué à 5.

    Je peux aussi décider de les découper "ligne à ligne" et mettre les lignes des 2 images 2 à 2 contigües : 1024 octet de l'une et à côté je stocke 1024 octets de l'autre, "ligne par ligne". Là peut-être que ça passe ?

    oui par exemple, ou découper une image en blocs de 8x8 (ça permet aussi d'accelerer en passage non horizontal)

    Je me met dans un cadre où je ne veux pas toucher aux instructions prefetch des processeurs récent.

    tu peux aussi lire un octet tout les 32 (ou 64, suivant la taille d'une ligne de cache) là ou tu vas écrire, pour le mettre en cache.
    (ça permet souvent d'aller jusqu'a 2x plus vite)

    et j'avais remarqué que le MMX pouvait charger ses registres avec des acces mémoires non alignés sans perte de vitesse... mais hum c'était du temps des pentiumII ( vieux con inside (tm) :) )

    et heu evidement, il faut etre sur que le cache soit bien le goulet d'étranglement, sinon tu perds ton temps.

  • # Fonctionnement des mecanismes de cache

    Posté par  . Évalué à 6.

    L'acces a la memoire ce fait quasi exclusivement par ligne. On demande une addresse, et on recupere les n octets suivant qui sont directement mis dans une ligne du cache. La plus part des memoire aujourd'hui sont capables de gerer plusieurs requetes en simultannees de maniere asynchrone (vive le pipeline) qui sont souvent utilises par le prefetch.

    C'est vraiment simplifier car il y a plein de mecanique supplementaire qui rentre en ligne de compte. Par exemple les TLB miss qui peuvent aussi impacter lourdement les requetes memoires si jamais les donnees ne sont pas toutes dans la meme page de memoire virtuelle.

    Enfin tu as souvent des caches differents pour les data et les instructions, aussi bien au niveau de la TLB que des caches memoire proprement dit, donc grosso modo les meme regles existe quand on ecrit du code (compact avec le moin de saut inutile possible, dans l'ideal des sauts que sur des boucles, car dans ce cas la on arrive a maintenir dans le cache la ligne du debut de la boucle). Par contre, il faut eviter de mettre des grosses data dans le code (typiquement des chaines de caractere), car elles seront dans ce cas la dans les caches instructions et non data (Ca ne concerne pas les constantes numeriques qui peuvent tenir sous la forme d'une valeur immediate dans une instruction). Ca arrive des fois lorsqu'on initialize des variables dans des fonctions.

    Bon, c'est super simplifie encore comme description du systeme memoire, car il y a vraiment beaucoup de chose qui peuvent intervenir, mais pour simplifier, plus tu utilises la memoire de maniere contigue et compact, aussi bien pour les instructions que les data plus tu es efficace. Et ne pas oublier que lorsque tu alloues de la memoire, c'est pour l'utiliser.

    PS: L'approche la plus extremiste de cette demarche est de compresser les donnees en RAM comme explique lors de [1]. Ca marche exessivement bien sur les bases de donnees, mais ca n'est pas forcement trivial a utiliser.

    [1]: http://wiki.whatthehack.org/index.php/Database_Compression_Between_(...)

  • # flemme de tout lire ...

    Posté par  (site web personnel) . Évalué à 0.

    j ai grave la flemme de lire tous ces beaux articles techniques, mais apres avoir bosse a cote d un mec qui codais en assembleur sur P3 800, je comprends pourquoi j ai bien fait de ne jamais apprendre l ASM x86.

    Par contre, je propose a tous les alternatives suivantes:

    - acheter un bi-alpha d occasion (on en trouve en tour server a partire de 75 euros piece, ou il manque juste les disques SCSI et ca roulle). C est un double CPU 64b vrai, sur une archi compatible 8/16/32/64 cote hard, mais avec un bus memoire de 128b, et un crossbar 256 ...

    c est vieux, c est tres puissant, ca decoiffe.

    - haxorer une PS3 et jouer avec un Cell; selon http://www.presence-pc.com/tests/Le-processeur-Cell-366/ ca dechire pas mal comme archi, mais comme on a pas encore vu l ISA ... enfin j attends deja avec impatience l annonce d un Cell.v2

    - sortire son vim/emacs, et participer a http://www.f-cpu.org/. Si vous ne maitrisez ni vim, ni emacs, ni VHDL, les contributions en nature sont aussi acceptees: license Xilinx pro complete, quadri Xeon ou PPC g5 2Go pour les simulations, ou meme si vous avez dans votre jardin une fonderie ca pourrait beaucoup les aider.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.