Optimisations vis-à-vis de la hiérarchie mémoire ------------------------------------------------ La hiérarchie mémoire: ---------------------- Plus une mémoire est rapide, plus elle coûte cher à capacité égale. ``Idéalement, on voudrait une mémoire de capacité illimitée... Nous sommes ... contraints d'admettre la possibilité de construire une hiérarchie de mémoires, chacune ayant une capacité supérieure à la précédente, mais étant accessible moins rapidement.'' [Burks, Goldstine, von Neumann, 1946] Efficace en pratique en raison du principe de localité: - Localité temporelle: si un objet est accédé, il a de bonnes chances d'être accédé à nouveau dans un futur proche. - Localité spatiale: si un objet est accédé, les objets voisins en mémoire ont de bonnes chances d'être accédés bientôt. La hiérarchie mémoire sur une machine moderne: Niveau Capacité Tps accès typique typique registres du processeur 256 octets 0 cycles cache primaire 8K + 8K 2 cycles (souvent séparé en instructions et données) cache secondaire 256 K 10 cycles (évt) cache tertiaire mémoire principale 128 Mo 50 cycles mémoire virtuelle sur disque 1 Go millions de cycles Les mémoires caches (antémémoires): ----------------------------------- Organisées en blocs (aussi appelés lignes), les blocs étant groupés en ensembles: - 2^n blocs - chaque bloc contient 2^b octets - les blocs sont groupés en 2^s ensembles contenant chacun 2^d blocs (donc 2^n = 2^s * 2^d) - 2^d est le degré d'associativité du cache: d = 0, s = n -> cache du type "accès direct" (direct mapped) d = n, s = 0 -> cache du type complètement associatif (fully associative) Pour accéder à l'adresse A: - décomposer A en (T, S, B) B à b bits position dans le bloc S à s bits numéro de l'ensemble T le "tag" - Examiner tous les blocs de l'ensemble numéro S - Si l'un des blocs est valide et porte le tag T: (cache hit) accéder à l'adresse B dans ce bloc - Sinon: (cache miss) charger 2^b octets depuis le niveau suivant de la hiérarchie à l'adresse (T, S, 0) et les écrire dans un des blocs de l'ensemble numéro S, avec le tag T. Puis accéder à l'adresse B dans ce bloc. Stratégie de choix du bloc dans lequel on écrit les données: généralement LRU (least recently used) -- le bloc de l'ensemble S qui n'a pas été accédé depuis le plus longtemps -- ou pseudo-aléatoire. Ceci exploite à la fois - la localité temporelle: la donnée qu'on vient d'accéder remplace une donnée plus ancienne - la localité spatiale: on va chercher dans le niveau suivant de la hiérarchie non seulement la donnée à l'adresse A, mais tout un bloc de données voisines. (Aussi, les transferts par bloc permettent d'atteindre un débit plus élevé.) Cas particuliers: - Cache en accès direct (s = 0): plus simple et plus rapide, car un seul bloc du cache peut convenir => une seule comparaison de tag. - Cache complètement associatif (s = n): contient exactement les 2^n blocs accédés les plus récemment. Irréalisable en pratique (trop de comparaisons de tags à effectuer en parallèle). Les sources de ratés (cache misses): - Raté obligatoire (compulsory miss): premier accès au bloc pendant l'exécution du programme. Inévitable. - Raté par capacité insuffisante (capacity miss): accès à un bloc qui a été remplacé par un autre dans le cache car la capacité du cache est insuffisante. Exemple: balayage circulaire d'un grand tableau loop for i = 0 to N-1 do ... a[i] ... done end Si N est supérieur à la taille du cache, et que celui-ci suit une stratégie LRU, tous les accès a[i] ratent. - Raté par collision ou par associativité insuffisante (collision miss): accès à un bloc qui a été remplacé par un autre dans le cache car la taille d'un ensemble est insuffisante. Exemple: si les adresses A et B ont le même S et le même B (i.e. sont égales modulo la taille du cache en octets) loop ... *A ... *B ... end Dans un cache en accès direct, tous les accès à A et à B ratent. Avec une associativité >= 2, tous les accès sauf les deux premiers réussissent. Influence de la taille des blocs: à taille totale du cache égale, de plus gros blocs diminuent les ratés par capacité (en raison de la localité spatiale) mais augmentent les ratés par collision. En pratique: de 16 à 64 octets pour le cache de niveau 1 de 32 à 256 octets pour le cache de niveau 2. Optimiser l'utilisation du cache de code: ---------------------------------------- Quelques règles simples permettent d'augmenter la localité des accès aux instructions composant le programme: * Ne pas augmenter exagérément la taille du code. En particulier, ne pas abuser de: - l'expansion en ligne (inlining) du corps d'une fonction - le déroulage des boucles * Faire en sorte que le plus possible d'instructions amenées dans le cache primaire de code soient exécutées. En particulier: - Aligner les points d'entrée de fonctions et les destinations de branchements sur des frontières de blocs. Sinon, on risque de recharger le bloc entier depuis le niveau de mémoire suivant, et de ne pas utiliser certaines des instructions contenues dans le bloc. branchif r, L I1 \ I2 | dans un même bloc de cache L: I3 | I4 / L'alignement ne coûte rien en temps d'exécution si les instructions précédentes ne s'exécutent pas en séquence (p.ex. branchement inconditionnel, ou retour de fonction). Sinon, les "nop" introduits ralentissent l'exécution d'une des branches. branchif r, L ... branch L' branchif r', L' nop nop nop nop L: ... L: ... (pas de surcoût) (surcoût si r' = false) - Les branches du code peu employées peuvent être mises "hors-ligne" pour augmenter la densité du flot d'instruction. Exemple: if (cond) { e } dans le cas où la condition est rarement vraie. Code naïf Code optimisé pour la densité <évaluer cond dans r> <évaluer cond dans r> branchifnot r, L branchif r, L1 L2: L: L1: branch L2 * Réordonnancement global du code pour éviter les collisions. P.ex. si deux fonctions f et g sont mutuellement récursives et fortement utilisées, essayer de les placer à des adresses différentes modulo la taille du cache (surtout pour un cache à accès direct). Cette transformation ne peut s'effectuer que sur des programmes complets, et s'appuie en général sur des profils d'exécution (option "-cord" des compilateurs Mips et Alpha). Optimiser l'utilisation du cache de données: -------------------------------------------- Accès aux tableaux: ------------------ Cas le plus étudié pour plusieurs raisons: - important pour le calcul numérique - motifs d'accès mémoire détectables à la compilation - écart important entre le meilleur comportement en cache et le pire. * Transformation 1: ajustement des tailles des tableaux et des matrices Des tailles égales à une puissance de 2 entraînent des collisions. Exemple: a : matrice 1024 * 1024 loop ... a[i][0] ... end En supposant que le cache fait 2048 ensembles, tous les accès a[i][0] se font dans les mêmes deux ensembles (numéros 0 et 1024), et donc au plus 2 * 2^d mots du tableau sont mis dans le cache. Si on ajoute un élément par colonne: a : matrice 1024 * 1025 les accès a[i][0] balayent tous les ensembles du cache (car 1024 est premier avec 1025) et donc toute la colonne a[i][0] peut résider dans le cache. * Transformation 2: tiling / blocking Découper les boucles en plus petites boucles avec une meilleure localité spatiale. Exemple: transposition de matrice for i = 0 to N-1 do for j = 0 to N-1 do a[i][j] <- b[j][i] done done Les accès a[i][j] ont une très bonne localité spatiale (balayage linéaire de la mémoire), mais pas b[j][i] (accès à 1 mot tous les N mots => les données dans le même bloc que b[j][i] sont amenées dans le cache, mais pas utilisées dans l'immédiat). Après tiling: for i = 0 to N-1 step K do for j = 0 to N-1 step K do for i2 = i to i + K - 1 do for j2 = j to j + K - 1 do a[i2][j2] <- b[j2][i2] done done done done (avec K divise N). Pour K bien choisi (p.ex. K = taille des blocs de cache), toutes les données amenées dans le cache sont utilisées pendant une exécution de l'intérieur de la boucle j. * Transformation 3: permutation de boucles Mettre comme boucle la plus interne celle qui permet la plus grande localité. Exemple: multiplication de matrice for i = 0 to 499 do for j = 0 to 499 do for k = 0 to 499 do C[i][j] <- C[i][j] + A[i][k] * B[k][j] done done done On suppose un cache avec des blocs de 16 mots. Pendant une exécution complète de la boucle interne (k): la référence à C accède à 1 bloc du cache la référence à A accède à 500/16 = 32 blocs différents la référence à B accède à 500 blocs différents Total: 533 blocs. Si on permute les boucles k et j de sorte que j devient la boucle la plus interne: Pendant une exécution complète de la boucle interne (j): la référence à C accède à 500/16 = 32 blocs la référence à A accède à 1 bloc la référence à B accède à 500/16 = 32 blocs Total: 65 blocs. La localité est bien meilleure. Structures chaînées dans le tas: -------------------------------- * Allocation par liste libre (GC à marquage ou à compte de références): Localité spatiale très faible, car les adresses des blocs alloués sont pseudo-aléatoires. Ex: une liste chaînée (blocs de 2 mots + 1 mot d'en-tête) avec un cache ayant des blocs de 4 mots. - Probabilité pour que le champ 2 soit dans le même bloc de cache que le champ 1: 75%. Cette proba est indépendante pour tous les "cons" de la liste (hypothèse de répartition aléatoire des "cons"). - Probabilité pour que le "cons" suivant soit dans le même bloc de cache que le "cons" courant: proche de 0. D'où en moyenne 1.25 ratés par "cons" lors d'un parcours linéaire de la liste pour la première fois. En conséquence de ce manque de localité spatiale: les caches avec de gros blocs sont inefficaces. * Allocation linéaire (GC à copie): Beaucoup de ratés lors de l'écriture dans un objet nouvellement alloué (puisqu'on alloue toujours à un endroit inutilisé depuis longtemps). Mais: astuces hardware (write buffer, subblock placement) pour éviter de bloquer sur un raté en écriture. En lecture: les objets alloués récemment sont à des adresses contiguës, la localité temporelle implique donc une certaine localité spatiale. - Préserver la localité lors de la copie: Une copie en largeur d'abord ne préserve pas la localité des objets (p.ex. les éléments d'une liste peuvent se trouver complètement séparés après une copie). On a proposé des schémas "plutôt en profondeur d'abord" (mostly depth-first) qui essayent de grouper dans une même page un objet et ses descendants immédiats. Remarque: ces schémas ainsi que la plupart des études sur le GC s'attachent plutôt à améliorer le comportement vis-à-vis de la mémoire virtuelle (organisée en pages de 4-16 Ko). Ne s'appliquent sans doute pas aux caches primaires (blocs de 16 octets), peut-être aux caches secondaires. * Idées de bon sens: - Réduire la quantité de mémoire accédée (ainsi, un GC à marquage peut avoir un meilleur comportement de cache qu'un GC à copie, simplement parce qu'il accède à deux fois moins de mémoire). - Réduire la taille des objets dans le tas. Exemple: stocker l'en-tête (rarement accédé en dehors du GC) séparément des objets. - Dans un GC à générations, prendre une génération jeune qui rentre dans le dernier niveau de cache (secondaire ou tertiaire). Produire du code qui prend en compte les caches: ----------------------------------------------- * Faire l'ordonnancement avec en supposant p.ex. que tous les "load" vont rater le cache primaire -> latence de 10 au lieu de 2. Problème: pas assez de parallélisme dans un bloc de base pour trouver des choses à faire pendant les 10 cycles de latence. Il faut donc faire du trace scheduling, en particulier remonter les "load" avant les branchements conditionnels. Problème 1: il faut être sûr que l'adresse accédée est valide. Ex: if (i > 0) { ... *p ... } Il se peut très bien que si i <= 0 alors p = NULL. Cependant, le typage statique apporte certaines garanties. Ex: if i = 0 then let (x,y) = p in ... ==> let (x,y) = p in if i = 0 then ... L'adresse de la paire p est toujours valide. Problème 2: on fait de l'exécution spéculative, d'où risque d'encombrer le sous-système mémoire avec des accès inutiles. * Utiliser les instructions de préchargement de certains processeurs: Alpha: FETCH r précharge 512 octets autour de r dans le cache secondaire FETCH_M r idem, dans l'intention de les modifier PowerPC: DCBT r précharge 1 bloc (32 octets) autour de r dans le cache primaire DCBTST r idem, dans l'intention de les modifier DCBZ r écrit des zéros dans le bloc d'adresse r (évite de le charger dans le cache primaire à la première écriture si on a l'intention d'écrire dans tout le bloc) À la différence d'un "load", ces instructions ne font rien si l'adresse référencée est invalide (pas d'erreur). Elles peuvent aussi s'exécuter avec une priorité inférieure aux vrais "load". ---------------------------------------------------------------------- Annexe: mesure du comportement d'un programme de calcul symbolique sur deux machines Dec Alpha 21064 ayant des caches différents Estimated clock frequency: 178.8Mhz Estimated clock frequency: 150.0Mhz Primary cache miss: 18 cycles Primary cache miss: 10 cycles Secondary cache miss: 74 cycles Secondary cache miss: 35 cycles Instructions issued: 3444M Instructions issued: 3426M Cycles used: 14140M Cycles used: 7711M Cycles per instruction: 4.1 Cycles per instruction: 2.3 Branch mispredictions: 14.4% Branch mispredictions: 14.4% Instruction cache misses: 1.9% Instruction cache misses: 1.9% Data cache misses: 24.5% Data cache misses: 22.9% Secondary cache misses: NOT MEASURED Secondary cache misses: 18.0% Cycle breakdown: Cycle breakdown: 4.4% dual issue 8.0% dual issue 15.6% single issue 28.4% single issue 16.2% pipe dry (instruction cache miss) 17.7% pipe dry (instruction cache miss) 4.6% pipe dry (branch) 5.6% pipe dry (branch) 58.5% pipe freeze (data cache miss) 39.0% pipe freeze (data cache miss) 0% pipe freeze (resource conflicts) 0% pipe freeze (resource conflict) 0.7% other 1.4% other