Datenzugriffsmuster, die eine CPU wirklich wütend machen

 (blog.weineng.me)
1 Punkte von GN⁺ 4 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • Selbst bei derselben Schleife zur Summierung von Ganzzahlen kann sich die Laufzeit stark ändern, wenn nur die Zugriffsreihenfolge verändert wird; das Experiment zeigt, dass sich eine Permutation erzeugen lässt, die mehr als 30 % langsamer als zufälliger Zugriff ist
  • Linearer Zugriff ist mit 132,75 Millionen Zyklen schnell, während zufälliger Zugriff sich bis auf 1,57 Milliarden Zyklen verlangsamt, weil die CPU die nächste Position schwer vorhersagen kann
  • Wenn Zugriffe über Cache-Line- und Seitengrenzen verteilt werden, werden Prefetcher und Cache-Wiederverwendung geschwächt, und wegen der Eigenschaften eines set-assoziativen Caches sinkt die effektiv nutzbare Kapazität des L1d auf etwa 768 B
  • Bei einer Seiten-Stride von 8 wird sogar die Cache-Line-Lokalität der PTEs zerstört, was zu 2,06 Milliarden Zyklen führt und damit ein noch schlechteres Muster als ein einfaches zufälliges Shuffle ergibt
  • Ein angenähertes Muster, das auf DRAM-Bank-/Zeilenkonflikte abzielt, war mit 2,08 Milliarden Zyklen noch etwas langsamer, ließ sich aber nur schwer vollständig kontrollieren, da das DRAM-Mapping physischer Adressen plattformabhängig ist

Versuchsaufbau und Grundlagen

  • Ziel ist es, in einer festen accumulator-Funktion, die die Ganzzahlen im Array data aufsummiert, nur die Permutation positions zu verändern, um die langsamstmögliche Laufzeit zu erzeugen
  • Die Zeit für die Erzeugung von positions wird ausgeschlossen; gemessen wird nur die Laufzeit der Akkumulationsfunktion mit dem Zykluszähler rdtsc
  • Die Datengröße beträgt 2^26 uint32_t-Ganzzahlen
    • 65.536 Seiten werden verwendet
    • Jede Seite ist 4.096 Byte groß
    • Jede Seite enthält 1.024 Ganzzahlen
  • Huge Pages sind deaktiviert
  • Der Messrechner ist ein x86_64-System auf Basis eines Intel Core Ultra 7 268V
    • 8 CPUs
    • L1d gesamt 320 KiB, L1i gesamt 512 KiB
    • L2 gesamt 14 MiB
    • L3 12 MiB
  • Der gesamte Code liegt im GitHub-Repository; das Beispiel wird mit g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out ausgeführt
  • Die Kernschleife hat die einfache Form, dass data[pos], auf das positions[i] zeigt, der Reihe nach addiert wird

Unterschied zwischen linearem und zufälligem Zugriff

  • Das einfachste linear-Muster setzt positions[i] = i und greift vom Anfang des Arrays an der Reihe nach zu
  • Der lineare Zugriff brauchte 132.752.394 Zyklen und gehört zu den schnellsten Varianten, weil die CPU stark für sequentiellen Zugriff optimiert ist
  • Wenn positions mit fisher_yates_shuffle als zufällige Permutation erzeugt wird, kann die CPU schwer vorhersagen, auf welche Daten als Nächstes zugegriffen wird
  • Der zufällige Zugriff benötigte 1.572.108.618 Zyklen und war damit mehr als zehnmal langsamer als linearer Zugriff
  • Das Experiment geht noch weiter und prüft, ob sich absichtlich eine Permutation konstruieren lässt, die noch schlechter als zufällig ist

Zugriffe über Cache-Lines und Seiten verteilen

  • Das erste verschlechterte Muster ordnet positions so an, dass aufeinanderfolgende Zugriffe immer genau um eine Cache-Line versetzt sind
  • Bei diesem Muster wird in einer 64-Byte-Cache-Line nur eine einzige 4-Byte-Ganzzahl verwendet, bevor zur nächsten Cache-Line gewechselt wird
    • Wenn dieselbe Cache-Line wieder erreicht wird, ist es sehr wahrscheinlich, dass die wiederverwendbaren Daten bereits aus dem Cache verdrängt wurden
  • Der Zugriff in Cache-Line-Abständen benötigte 718.804.156 Zyklen und war damit mehr als viermal langsamer als ein linearer Scan
  • Dennoch kann der Hardware-Prefetcher hier noch ein einfaches Streaming-Muster in data erkennen und zukünftige Cache-Lines vorab laden
  • Viele Intel Hardware Data Prefetcher führen kein Prefetching über 4-KiB-Seitengrenzen hinweg durch
  • Das nächste Muster vergrößert den Zugriffsabstand nicht auf eine Cache-Line, sondern auf eine ganze Seite
    • Jede Seite ist 4.096 Byte groß
    • Es wird zunächst auf denselben Offset innerhalb jeder Seite zugegriffen, in der Form page_index * elements_per_page + element_index
  • Der Zugriff in Seitenabständen verlangsamte sich deutlich auf 1.411.153.154 Zyklen

Set-assoziativer Cache und Wiederverwendungsdistanz

  • Der L1d-Cache pro Kern des Versuchsrechners hat 48 KB, 12 Wege und 64 Sets
  • Da der L1d 64 Sets hat, werden die Adressen A und A + 4096 Byte auf dasselbe L1d-Set abgebildet
    • 4.096 Byte entsprechen 64 sets * 64-byte cache line
  • Eine seitenweise Stride sorgt dafür, dass sich jede innere Schleife nicht gleichmäßig über alle 64 Sets verteilt, sondern wiederholt dasselbe Set trifft
  • Ein Set hat nur 12 Wege; konkurrieren also mehr als 12 aktive Cache-Lines, muss die CPU Zeilen ständig verdrängen und erneut laden
  • Obwohl der gesamte L1d 48 KB groß ist, beträgt die in diesem Zugriffsmuster sinnvoll nutzbare L1d-Kapazität nur etwa 768 B, also 12 ways * 64B
  • Das Muster separated_by_a_page greift auf 65.536 Cache-Lines zu, bevor es zur selben Cache-Line zurückkehrt; die Cache-Line-Wiederverwendungsdistanz beträgt also 65.536
  • Das Muster separated_by_a_page_and_cacheline, das zusätzlich die Cache-Lines innerhalb einer Seite trennt, vergrößert die Wiederverwendungsdistanz auf 65536 pages * 4096 page size / 64 cacheline size
  • Das Ergebnis lag jedoch mit 1.408.519.172 Zyklen fast gleichauf mit dem rein seitenweisen Zugriff
  • Das Experiment lief auf Core 3, und dieser Kern hat 2,5 MB L2 und 48 KB L1
    • Ein vollständiger Durchlauf über 65.536 Seiten greift auf 4 MB Daten zu
    • Das ist größer als die private L1-/L2-Kapazität dieses Kerns
    • Daher ist es unwahrscheinlich, dass die später erneut benötigte Cache-Line noch im privaten Cache liegt
  • Wiederverwendung im privaten Cache ist nur zu erwarten, wenn die Cache-Line-Wiederverwendungsdistanz grob kleiner als ((2560+48)*1024/64) ist, also etwa 40.000

Seiten-Stride, PTEs und sogar DRAM quälen

  • Die nächste Variante ist das Muster separated_by_stride_pages_and_cacheline, das nicht auf aufeinanderfolgende Seiten, sondern in Abständen von N Seiten zugreift
  • Bei Messungen mit verschiedenen Strides ergab sich das schlechteste Ergebnis bei einer Seiten-Stride von 8, und sie war langsamer als zufälliger Zugriff
  • Bei einem Einzelstart mit -DSTRIDE=8 wurden 2.058.425.640 Zyklen gemessen
  • Ein möglicher Grund für das Maximum bei Stride 8 ist die Adressübersetzung
    • Bei Zugriffen auf virtuelle Adressen übersetzt die MMU diese in physische Adressen
    • Für die Übersetzung werden Page Table Entries (PTEs) verwendet
    • Ein PTE ist 8 Byte groß, und in eine Cache-Line passen 8 PTEs
    • Bei einer Stride von 8 Seiten müssen offenbar nicht nur Daten-Cache-Lines, sondern jedes Mal auch separate Cache-Lines für die Seitenabbildung geholt werden
  • Die letzte Stufe ist der Versuch, sogar die Arbeitsweise des DRAM-Controllers zu stören
  • DRAM ist in Channel, Rank, Chip, Bank, Row und Column organisiert
    • Innerhalb einer Bank gibt es mehrere Rows
    • Um auf eine bestimmte Row zuzugreifen, wird sie aktiviert und in den Row Buffer kopiert
    • Wenn in derselben Bank auf eine andere Row zugegriffen wird, muss die bisherige Row per Precharge geschlossen und die neue Row aktiviert werden
  • Wenn in derselben Bank abwechselnd auf verschiedene Rows zugegriffen wird, entsteht ein Row-Buffer-Konflikt, und der DRAM-Controller reagiert langsamer
  • Umgekehrt ergibt ein Zugriff auf eine bereits geöffnete Row einen Row-Buffer-Hit, und wenn mehrere Banks parallel genutzt werden, kann der Memory Controller Arbeit überlappend ausführen
  • Die Strategie zur Erzeugung eines langsamen Musters ist wie folgt
    • Die virtuelle Seitennummer wird über die Seitentabelle in eine physische Frame-Nummer (PFN) übersetzt
    • Der Seitenoffset bleibt erhalten, und daraus wird die physische Adresse gebildet
    • Die physische Adresse wird als DRAM-Channel, Rank, Bank Group, Bank, Row und Column interpretiert
    • Durch wiederholte Zugriffe auf verschiedene Rows innerhalb derselben Bank werden fast bei jeder Anfrage Precharge und Aktivierung erzwungen
  • Allerdings ist das Mapping von physischer Adresse auf DRAM-Channel, Rank, Bank und Row nicht dokumentiert und plattformabhängig
    • Es kann je nach CPU, Speichertyp, BIOS-/Firmware-Einstellungen, Channel-/Rank-Konfiguration und Address Hashing variieren
    • Werkzeuge wie DRAMA oder Sudoku könnten verwendet werden, ließen sich auf diesem Testsystem aber nicht zum Laufen bringen
  • Basierend auf dem DRAMA-Paper und lokalen Experimenten wird mit 4 Bank Groups, 4 Banks pro Group und DRAM_ROW_SHIFT = 18 angenähert
  • Das Muster unter Berücksichtigung von DRAM-Bank-/Zeilenkonflikten erreichte 2.082.308.014 Zyklen und war damit konsistent etwas langsamer als Stride 8, aber der Unterschied war nicht groß
  • Dass kein vollständiger Row-Konflikt erzeugt werden konnte, hat mehrere mögliche Gründe
    • Die Schätzungen für Bank-Group-Hash, Bank-Hash und Row-Shift könnten ungenau sein
    • Eine Stride von 8 Seiten entspricht einem Zugriffsabstand von etwa 32 KB, wodurch es schwer ist, in derselben DRAM-Row zu bleiben
    • Wegen Intels Bank Hashing werden tatsächlich womöglich mehrere Banks gleichzeitig verwendet
  • Ein vollständiger Beispiel-Lauf zeigte folgende Ergebnisse
    • 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
  • Wenn Cache, Prefetcher, Cache-Line-Wiederverwendung, PTE-Zugriffe und DRAM-Bank-/Zeileneigenschaften der Reihe nach verschlechtert werden, lässt sich ein Summierungsmuster erzeugen, das 33 % langsamer ist als zufälliger Zugriff
  • Es gibt auch andere Möglichkeiten, eine Akkumulation zu verlangsamen, etwa durch das Umschalten in Stromsparmodi, aber das ist ein anderes Thema als ein Experiment, das nur das Zugriffsmuster verändert

Verwandte Beiträge

1 Kommentare

 
GN⁺ 4 시간 전
Kommentare auf Lobste.rs

  • Interessant zu lesen, so sieht also interne Windows-11-Entwicklungsforschung aus /s

  • Das habe ich gelernt, als ich https://github.com/ob/cache gebaut habe

    • Ich frage mich, wie die zwei Sätze im README zu verstehen sind
      Der eine sagt, die Technik zur Erzeugung der Latenzzahlen habe er zuerst in Übung 5.2 auf Seite 476 von Computer Architecture: A Quantitative Approach gesehen, der andere sagt, die Idee stamme aus der Doktorarbeit von Rafael Héctor Saavedra‑Barrera
      Ich möchte herausfinden, ob es um unterschiedliche Dinge geht, ob das ein Widerspruch ist oder ob es dasselbe ist und Saavedra-Barrera in CA:AQA zitiert wird
      Unklar ist auch, ob ein Claude-Programm beim Schreiben des README außen vor war; da es auch als Contributor im Repository angezeigt wird, möchte ich erst prüfen, ob die Referenz echt ist

  • Wenn ihr mit einem eigenen Cache-Hierarchie-Zugriff experimentieren wollt, kann ich auch meinen Simulator empfehlen
    https://github.com/TheCloudlet/Stratum

  • Ich frage mich, wie der Overhead für die Berechnung der Indizes von den tatsächlichen Zugriffskosten getrennt wurde

    • Falls du meinst, wie man nur die Accumulator-Zyklen misst, ohne die Zeit zum Erzeugen von positions mitzurechnen: Ich habe zuerst reset und arrange_positions ausgeführt und dann ein Makro verwendet, das zwischen rdtsc_start() und rdtsc_end() nur accumulator(data, positions) ausführt
      Danach habe ich das Ergebnis ausgegeben, sum == linear_scan_sum verifiziert und mit do_not_optimize(sum) verhindert, dass es wegoptimiert wird

  • Wenn wir es mit den Datenzugriffsmustern machen, die Professoren einem beibringen, müsste man zuerst eine Klasse SafeNumber.java bauen und ein Member add(SafeNumber b) hinzufügen
    Nächstes Semester lernen wir dann wahrscheinlich eine Architektur, bei der man das hinter Redis platziert, um Webscale-Performance zu bekommen
    Dank Claude habe ich den Benchmark nach Java portiert: Java SafeNumber[] war bei linearem Zugriff etwa 3,6-mal langsamer als C++ uint32_t[], und beim Fisher-Yates-Shuffle 52,2-mal langsamer als lineares C++
    In absoluten Zeiten waren es bei 67 Millionen Elementen: C++ linear 10.258.584 ns, Java linear 36.740.667 ns, C++ Shuffle 264.856.042 ns, Java Shuffle 535.724.208 ns; beeindruckend, dass es entgegen meiner Erwartung „nur etwa Faktor 4“ war

    • Der Java-Faktor ist nicht gerade großartig, aber mit Project Valhalla könnte es näher herankommen