Des schémas d’accès aux données qui mettent vraiment le CPU en colère

 (blog.weineng.me)
1 points par GN⁺ 3 시간 전 | 1 commentaires | Partager sur WhatsApp
  • Même pour une boucle d’addition sur des entiers identique, le simple fait de changer l’ordre d’accès modifie fortement le temps d’exécution, et l’expérience montre qu’il est possible de créer une permutation plus de 30 % plus lente qu’un accès aléatoire
  • L’accès linéaire est rapide avec 133 millions de cycles, tandis que l’accès aléatoire, où le CPU a du mal à prédire la position suivante, ralentit jusqu’à 1,57 milliard de cycles
  • En espaçant les accès selon les limites de ligne de cache et de page, on affaiblit le préfetcher et la réutilisation du cache, et, à cause des caractéristiques d’un cache associatif par ensembles, la capacité réellement exploitable du L1d tombe à environ 768 o
  • Avec un stride de page de 8, on casse aussi la localité des lignes de cache des PTE, ce qui mène à 2,06 milliards de cycles, un schéma encore pire qu’un simple mélange aléatoire
  • Un schéma approximatif visant des conflits de bank/row en DRAM était légèrement plus lent à 2,08 milliards de cycles, mais le mapping DRAM des adresses physiques dépend de la plateforme et reste difficile à contrôler complètement

Conditions de l’expérience et référence

  • L’objectif est de produire le temps d’exécution le plus lent possible en ne modifiant que la permutation positions, dans une fonction accumulator fixe qui additionne les entiers du tableau data
  • Le temps de génération de positions est exclu, et seul le temps d’exécution de la fonction d’accumulation est mesuré avec le compteur de cycles rdtsc
  • La taille des données est de 2^26 entiers uint32_t
    • 65 536 pages utilisées
    • chaque page fait 4 096 octets
    • chaque page contient 1 024 entiers
  • Les huge pages sont désactivées
  • La machine de mesure est un système x86_64 basé sur un Intel Core Ultra 7 268V
    • 8 CPU
    • L1d total : 320 KiB, L1i total : 512 KiB
    • L2 total : 14 MiB
    • L3 : 12 MiB
  • Le code complet est disponible dans le dépôt GitHub, et l’exemple s’exécute avec g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • La boucle principale est une forme simple qui additionne dans l’ordre les data[pos] pointés par positions[i]

Différence entre accès linéaire et accès aléatoire

  • Le motif linear, le plus simple, définit positions[i] = i pour parcourir le tableau séquentiellement depuis le début
  • L’accès linéaire a pris 132 752 394 cycles, et fait partie des plus rapides car le CPU est fortement optimisé pour les accès séquentiels
  • Si l’on crée une permutation aléatoire de positions avec fisher_yates_shuffle, le CPU a du mal à prédire les données auxquelles il accédera ensuite
  • L’accès aléatoire a pris 1 572 108 618 cycles, soit plus de 10 fois plus lent que l’accès linéaire
  • L’expérience va plus loin en vérifiant s’il est possible de construire intentionnellement une permutation pire que l’aléatoire

Espacer les accès par ligne de cache et par page

  • Le premier motif dégradé place positions de sorte que les accès successifs soient toujours séparés par une ligne de cache
  • Avec ce motif, sur une ligne de cache de 64 octets, on n’utilise qu’un seul entier de 4 octets avant de passer à la ligne suivante
    • lorsqu’on revient à la même ligne de cache, il est très probable que les données réutilisables aient déjà été évincées du cache
  • L’accès espacé d’une ligne de cache a pris 718 804 156 cycles, soit plus de 4 fois plus lent qu’un balayage linéaire
  • Même dans ce cas, le préfetcher matériel peut détecter un simple motif de streaming sur data et précharger les futures lignes de cache
  • Beaucoup de préfetchers matériels de données Intel ne font pas de prefetch au-delà des frontières de pages de 4 KiB
  • Le motif suivant espace les accès non plus d’une ligne de cache, mais d’une page entière
    • chaque page fait 4 096 octets
    • on accède d’abord au même offset de chaque page sous la forme page_index * elements_per_page + element_index
  • L’accès espacé d’une page ralentit fortement, à 1 411 153 154 cycles

Cache associatif par ensembles et distance de réutilisation

  • Le cache L1d par cœur de la machine testée est de 48 Ko, 12-way, avec 64 ensembles
  • Comme le L1d a 64 ensembles, les adresses A et A + 4096 octets se retrouvent dans le même ensemble du L1d
    • 4 096 octets correspondent à 64 sets * 64-byte cache line
  • Un stride d’une page fait que chaque boucle interne ne se répartit pas uniformément sur les 64 ensembles, mais frappe toujours le même ensemble
  • Comme un ensemble ne dispose que de 12 ways, si plus de 12 lignes de cache actives entrent en concurrence, le CPU doit évincer et recharger les lignes de manière répétée
  • Bien que la capacité totale du L1d soit de 48 Ko, la capacité utile du L1d pour ce motif d’accès tombe à environ 768 o, soit 12 ways * 64B
  • Le motif separated_by_a_page touche 65 536 lignes de cache avant de revenir à la même ligne, ce qui donne une distance de réutilisation de 65 536
  • Le motif separated_by_a_page_and_cacheline, qui sépare aussi les lignes de cache à l’intérieur des pages, augmente encore la distance de réutilisation jusqu’à 65536 pages * 4096 page size / 64 cacheline size
  • Pourtant, le résultat était presque identique à l’accès par page, avec 1 408 519 172 cycles
  • L’expérience a été exécutée sur le cœur 3, qui dispose de 2,5 Mo de L2 et de 48 Ko de L1
    • un parcours complet des 65 536 pages touche 4 Mo de données
    • c’est plus que la capacité privée L1/L2 de ce cœur
    • il est donc peu probable que la ligne de cache nécessaire ensuite soit encore présente dans le cache privé
  • On ne peut espérer une réutilisation dans le cache privé que lorsque la distance de réutilisation des lignes de cache est inférieure à environ 40 000, soit approximativement ((2560+48)*1024/64)

Maltraiter aussi le stride de page, les PTE et la DRAM

  • La variante suivante est le motif separated_by_stride_pages_and_cacheline, qui accède non pas à des pages consécutives, mais à des pages espacées de N pages
  • Après mesure de plusieurs strides, c’est un stride de page de 8 qui a donné le pire résultat, plus lent que l’accès aléatoire
  • Exécuté seul avec -DSTRIDE=8, il prend 2 058 425 640 cycles
  • Une des explications possibles du pic à stride 8 concerne la traduction d’adresses
    • lors d’un accès à une adresse virtuelle, la MMU la convertit en adresse physique
    • cette conversion utilise des page table entries (PTE)
    • une PTE fait 8 octets, et une ligne de cache peut contenir 8 PTE
    • avec un stride de 8 pages, l’idée est qu’il faut aussi charger à chaque fois une ligne de cache distincte pour le mapping des pages, en plus de la ligne de cache des données
  • La dernière étape tente de perturber jusqu’au fonctionnement du contrôleur DRAM
  • La DRAM est organisée en channel, rank, chip, bank, row et column
    • chaque bank contient plusieurs row
    • pour accéder à une row donnée, il faut l’activer et la copier dans le row buffer
    • pour accéder à une autre row du même bank, il faut fermer la row existante avec un precharge puis activer la nouvelle
  • Alterner des accès entre différentes row d’un même bank provoque un row-buffer conflict, ce qui ralentit la réponse du contrôleur DRAM
  • À l’inverse, accéder à une row déjà ouverte produit un row-buffer hit, et l’utilisation simultanée de plusieurs banks permet au contrôleur mémoire de recouvrir les opérations
  • La stratégie pour construire un motif lent est la suivante
    • convertir le virtual page number en physical frame number (PFN) via la table des pages
    • conserver le page offset pour reconstruire l’adresse physique
    • interpréter l’adresse physique en channel, rank, bank group, bank, row et column DRAM
    • accéder de façon répétée à des row différentes dans un même bank afin de forcer un precharge et une activation presque à chaque requête
  • Mais le mapping entre adresse physique et channel, rank, bank ou row DRAM n’est pas documenté et dépend de la plateforme
    • il peut varier selon le CPU, le type de mémoire, les réglages BIOS/firmware, la configuration channel/rank ou l’address hashing
    • des outils comme DRAMA ou Sudoku peuvent être utilisés, mais ils n’ont pas pu être exécutés sur cette machine de test
  • En s’appuyant sur l’article DRAMA et sur des expériences locales, l’approximation utilise 4 bank groups, 4 banks par groupe et DRAM_ROW_SHIFT = 18
  • Le motif prenant en compte les conflits DRAM bank/row a atteint 2 082 308 014 cycles, de manière constante un peu plus lente que le stride 8, mais sans grand écart
  • Plusieurs contraintes expliquent pourquoi il n’a pas été possible de provoquer un conflit de row parfait
    • l’estimation du bank group hash, du bank hash et du row shift peut être imprécise
    • un stride de 8 pages correspond à un espacement d’environ 32 Ko, donc il est difficile de rester dans la même row DRAM
    • à cause du bank hashing d’Intel, plusieurs banks peuvent en pratique être utilisés en parallèle
  • Un exemple d’exécution complet donne les résultats suivants
    • linear: 132,752,394
    • fisher_yates_shuffle: 1,572,108,618
    • separated_by_a_cacheline: 718,804,156
    • separated_by_a_page: 1,411,153,154
    • separated_by_a_page_and_cacheline: 1,408,519,172
    • stride=8 separated_by_stride_pages_and_cacheline: 2,058,425,640
    • separated_by_stride_bank_conflicts_and_cacheline: 2,082,308,014
  • En dégradant successivement le cache, le préfetcher, la réutilisation des lignes de cache, les accès aux PTE et les propriétés bank/row de la DRAM, on peut créer un motif d’addition 33 % plus lent qu’un accès aléatoire
  • Il existe aussi d’autres moyens de ralentir davantage l’accumulation, comme les bascules en mode économie d’énergie, mais cela sort du cadre de cette expérience centrée uniquement sur le motif d’accès

À lire aussi

1 commentaires

 
GN⁺ 3 시간 전
Commentaires sur Lobste.rs

  • C’était amusant à lire : on dirait à quoi ressemble une étude interne de développement de Windows 11 /s

  • J’ai appris tout ça en créant https://github.com/ob/cache

    • Je me demande comment comprendre les deux phrases du README.
      L’une dit que la technique pour générer les chiffres de latence a été vue pour la première fois dans l’exercice 5.2, page 476, de Computer Architecture: A Quantitative Approach, tandis que l’autre dit que l’idée vient de la thèse de doctorat de Rafael Héctor Saavedra‑Barrera.
      J’aimerais vérifier s’il s’agit de deux choses différentes, d’une contradiction, ou bien de la même chose et que Saavedra-Barrera est cité dans CA:AQA.
      Il n’est pas clair non plus si le programme Claude a été exclu de la rédaction du README, et comme il apparaît aussi parmi les contributeurs du dépôt, j’aimerais d’abord vérifier que la référence est bien réelle.

  • Si vous voulez expérimenter un accès à une hiérarchie de cache personnalisée, je recommande aussi le simulateur que j’ai créé :
    https://github.com/TheCloudlet/Stratum

  • Je me demande comment ils ont séparé le surcoût du calcul des index du coût réel des accès.

    • Si la question est de savoir comment mesurer uniquement les cycles de l’accumulateur sans inclure le temps nécessaire à la création de positions, j’ai utilisé une macro qui exécute d’abord reset et arrange_positions, puis ne place que accumulator(data, positions) entre rdtsc_start() et rdtsc_end().
      Ensuite, le résultat est affiché, sum == linear_scan_sum est vérifié, et do_not_optimize(sum) empêche l’optimisation de le supprimer.

  • Si on essaye aussi avec les patterns d’accès aux données enseignés par les profs, il faut commencer par créer une classe SafeNumber.java, puis ajouter une méthode membre add(SafeNumber b).
    Au semestre prochain, je suppose qu’on apprendra une architecture qui place ça derrière Redis pour obtenir des performances webscale.
    Grâce à Claude, j’ai porté le benchmark en Java : Java SafeNumber[] était environ 3,6 fois plus lent que le uint32_t[] C++ en accès linéaire, et 52,2 fois plus lent que le linéaire C++ avec un mélange Fisher-Yates.
    En temps absolu, pour 67 millions d’éléments, cela donnait 10 258 584 ns pour le linéaire C++, 36 740 667 ns pour le linéaire Java, 264 856 042 ns pour le mélange C++, et 535 724 208 ns pour le mélange Java ; c’est impressionnant, car c’est finalement « seulement 4 fois » plus lent que ce à quoi je m’attendais.

    • Le facteur côté Java n’est pas franchement excellent, mais avec l’arrivée de Project Valhalla, cela pourrait se rapprocher.