Wie funktionieren Cache-Zeilen?

Ich verstehe, dass der Prozessor Daten über Cache-Zeilen in den Cache bringt, was - zum Beispiel auf meinem Atom-Prozessor - ungefähr 64 Bytes gleichzeitig einbringt, unabhängig von der Größe der tatsächlich gelesenen Daten.

Meine Frage ist:

Stellen Sie sich vor, Sie müssen ein Byte aus dem Speicher lesen. Welche 64 Bytes werden in den Cache gebracht?

Die zwei Möglichkeiten, die ich sehen kann, sind, dass entweder die 64 Bytes an der nächsten 64-Byte-Grenze unterhalb des interessierenden Bytes beginnen oder die 64 Bytes auf eine vorbestimmte Weise um das Byte verteilt sind (z. B. halb unter, halb über oder alles oben).

Welches ist es?

Wenn die Cache-Zeile mit dem von Ihnen geladenen Byte oder Wort nicht bereits im Cache vorhanden ist, fordert Ihre CPU die 64 Bytes an, die an der Cache-Zeilengrenze beginnen (die größte Adresse unter der von Ihnen benötigten Adresse ist ein Vielfaches von 64). .

Moderne PC-Speichermodule übertragen 64 Bit (8 Byte) gleichzeitig in einem Burst von acht Übertragungen , sodass ein Befehl das Lesen oder Schreiben einer vollständigen Cache-Zeile aus dem Speicher auslöst. (Die DDR1 / 2/3/4 SDRAM-Burst-Übertragungsgröße kann bis zu 64B konfiguriert werden. CPUs wählen die Burst-Übertragungsgröße entsprechend ihrer Cache-Zeilengröße aus, 64B ist jedoch üblich.)

Als Faustregel gilt: Wenn der Prozessor keinen Speicherzugriff vorhersagen (und vorab abrufen) kann, kann der Abrufvorgang ~ 90 Nanosekunden oder ~ 250 Taktzyklen dauern (von der CPU, die die Adresse kennt, bis zur CPU, die Daten empfängt).

Im Gegensatz dazu hat ein Treffer im L1-Cache eine Lastverwendungslatenz von 3 oder 4 Zyklen, und ein Store-Reload hat eine Store-Forwarding-Latenz von 4 oder 5 Zyklen auf modernen x86-CPUs. Bei anderen Architekturen ist es ähnlich.

Lesen Sie weiter: Ulrich Dreppers Was jeder Programmierer über das Gedächtnis wissen sollte . Der Software-Prefetch-Rat ist etwas veraltet: Moderne HW-Prefetchers sind intelligenter und Hyperthreading ist viel besser als in P4-Tagen (ein Prefetch-Thread ist also normalerweise eine Verschwendung). Auch derx86 Das Tag-Wiki enthält viele Leistungslinks für diese Architektur.

Wenn Cache-Zeilen 64 Byte breit sind, entsprechen sie Speicherblöcken, die an Adressen beginnen, die durch 64 teilbar sind. Die niedrigstwertigen 6 Bits einer Adresse sind ein Versatz in der Cache-Zeile.

Für jedes gegebene Byte kann die Cache-Zeile, die abgerufen werden muss, gefunden werden, indem die am wenigsten signifikanten sechs Bits der Adresse gelöscht werden, was einer Abrundung auf die nächste Adresse entspricht, die durch 64 teilbar ist.

Obwohl dies durch Hardware erfolgt, können wir die Berechnungen anhand einiger Referenz-C-Makrodefinitionen anzeigen:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

Erstens ist ein Hauptspeicherzugriff sehr teuer. Derzeit hat eine 2-GHz-CPU (die langsamste einmal) 2G-Ticks (Zyklen) pro Sekunde. Eine CPU (heutzutage virtueller Kern) kann einmal pro Tick einen Wert aus ihren Registern abrufen. Da ein virtueller Kern aus mehreren Verarbeitungseinheiten besteht (ALU - arithmetische Logikeinheit, FPU usw.), kann er bestimmte Anweisungen nach Möglichkeit tatsächlich parallel verarbeiten.

Ein Zugriff auf den Hauptspeicher kostet etwa 70 ns bis 100 ns (DDR4 ist etwas schneller). Diese Zeit besteht im Wesentlichen darin, den L1-, L2- und L3-Cache nachzuschlagen und dann den Speicher zu drücken (Befehl an den Speichercontroller senden, der ihn an die Speicherbänke sendet), auf die Antwort zu warten und fertig.

100ns bedeutet ungefähr 200 Zecken. Wenn ein Programm also immer die Caches übersehen würde, auf die jeder Speicher zugreift, würde die CPU ungefähr 99,5% ihrer Zeit (wenn sie nur Speicher liest) im Leerlauf auf den Speicher warten.

Um die Dinge zu beschleunigen, gibt es die Caches L1, L2, L3. Sie verwenden Speicher, der direkt auf dem Chip platziert ist, und verwenden eine andere Art von Transistorschaltungen, um die gegebenen Bits zu speichern. Dies kostet mehr Platz, mehr Energie und ist teurer als der Hauptspeicher, da eine CPU normalerweise mit einer fortschrittlicheren Technologie hergestellt wird und ein Produktionsfehler im Speicher L1, L2, L3 die Möglichkeit hat, die CPU wertlos zu machen (defekt) Große L1-, L2-, L3-Caches erhöhen die Fehlerrate, wodurch die Ausbeute verringert wird und der ROI direkt verringert wird. Es gibt also einen großen Kompromiss, wenn es um die verfügbare Cache-Größe geht.

(Derzeit werden mehr L1-, L2-, L3-Caches erstellt, um bestimmte Teile deaktivieren zu können, um die Wahrscheinlichkeit zu verringern, dass ein tatsächlicher Produktionsfehler darin besteht, dass die Cache-Speicherbereiche den CPU-Fehler als Ganzes darstellen.)

Um eine Timing-Idee zu geben (Quelle: Kosten für den Zugriff auf Caches und Speicher )

• L1-Cache: 1 ns bis 2 ns (2-4 Zyklen)
• L2-Cache: 3 ns bis 5 ns (6-10 Zyklen)
• L3-Cache: 12 ns bis 20 ns (24-40 Zyklen)
• RAM: 60 ns (120 Zyklen)

Da wir verschiedene CPU-Typen mischen, handelt es sich nur um Schätzungen, die jedoch eine gute Vorstellung davon geben, was wirklich passiert, wenn ein Speicherwert abgerufen wird und in einer bestimmten Cache-Schicht möglicherweise ein Treffer oder ein Fehler auftritt.

Ein Cache beschleunigt also den Speicherzugriff erheblich (60 ns gegenüber 1 ns).

Das Abrufen eines Werts und das Speichern im Cache für die Möglichkeit des erneuten Lesens ist gut für Variablen, auf die häufig zugegriffen wird. Für Speicherkopiervorgänge wäre es jedoch immer noch zu langsam, da man nur einen Wert liest, den Wert irgendwo schreibt und den Wert nie liest wieder ... keine Cache-Treffer, absolut langsam (außerdem kann dies parallel geschehen, da die Ausführung nicht in Ordnung ist).

Diese Speicherkopie ist so wichtig, dass es verschiedene Möglichkeiten gibt, sie zu beschleunigen. In der Anfangszeit war der Speicher häufig in der Lage, Speicher außerhalb der CPU zu kopieren. Es wurde direkt vom Speichercontroller verarbeitet, sodass ein Speicherkopiervorgang die Caches nicht verschmutzte.

Aber neben einer einfachen Speicherkopie war ein anderer serieller Speicherzugriff durchaus üblich. Ein Beispiel ist die Analyse einer Reihe von Informationen. Ein Array von ganzen Zahlen zu haben und die Summe, den Mittelwert, den Durchschnitt oder noch einfacher einen bestimmten Wert zu berechnen (Filter / Suche), war eine weitere sehr wichtige Klasse von Algorithmen, die jedes Mal auf einer Allzweck-CPU ausgeführt wurden.

Durch die Analyse des Speicherzugriffsmusters wurde deutlich, dass Daten sehr oft nacheinander gelesen werden. Es bestand eine hohe Wahrscheinlichkeit, dass, wenn ein Programm den Wert am Index i liest, das Programm auch den Wert i + 1 liest. Diese Wahrscheinlichkeit ist geringfügig höher als die Wahrscheinlichkeit, dass dasselbe Programm auch den Wert i + 2 usw. liest.

Angesichts einer Speicheradresse war (und ist) es daher eine gute Idee, vorauszulesen und zusätzliche Werte abzurufen. Dies ist der Grund, warum es einen Boost-Modus gibt.

Speicherzugriff im Boost-Modus bedeutet, dass eine Adresse gesendet wird und mehrere Werte nacheinander gesendet werden. Jeder zusätzliche Sendewert benötigt nur etwa 10 ns (oder sogar weniger).

Ein weiteres Problem war eine Adresse. Das Senden einer Adresse braucht Zeit. Um einen großen Teil des Speichers zu adressieren, müssen große Adressen gesendet werden. In den frühen Tagen bedeutete dies, dass der Adressbus nicht groß genug war, um die Adresse in einem einzigen Zyklus (Tick) zu senden, und dass mehr als ein Zyklus erforderlich war, um die Adresse zu senden, was zu einer größeren Verzögerung führte.

Eine Cache-Zeile von 64 Bytes bedeutet beispielsweise, dass der Speicher in verschiedene (nicht überlappende) Speicherblöcke mit einer Größe von 64 Bytes unterteilt ist. 64 Bytes bedeuten, dass die Startadresse jedes Blocks die niedrigsten sechs Adressbits hat, die immer Nullen sind. Das Senden dieser sechs Nullbits jedes Mal ist also nicht erforderlich, um den Adressraum für eine beliebige Anzahl von Adressbusbreiten 64-mal zu erhöhen (Begrüßungseffekt).

Ein weiteres Problem, das die Cache-Zeile löst (neben dem Vorauslesen und dem Speichern / Freigeben von sechs Bits auf dem Adressbus), ist die Art und Weise, wie der Cache organisiert ist. Wenn beispielsweise ein Cache in 8-Byte-Blöcke (64-Bit-Blöcke) aufgeteilt wird, muss die Adresse der Speicherzelle gespeichert werden, für die diese Cache-Zelle den Wert enthält. Wenn die Adresse auch 64-Bit wäre, bedeutet dies, dass die Hälfte der Cache-Größe von der Adresse verbraucht wird, was zu einem Overhead von 100% führt.

Da eine Cache-Zeile 64 Byte groß ist und eine CPU möglicherweise 64 Bit - 6 Bit = 58 Bit verwendet (die Null-Bits müssen nicht zu richtig gespeichert werden), können wir 64 Byte oder 512 Bit mit einem Overhead von 58 Bit (11% Overhead) zwischenspeichern. In Wirklichkeit sind die gespeicherten Adressen noch kleiner als diese, aber es gibt Statusinformationen (wie ist die Cache-Zeile gültig und genau, schmutzig und muss in RAM zurückgeschrieben werden usw.).

Ein weiterer Aspekt ist, dass wir einen satzassoziativen Cache haben. Nicht jede Cache-Zelle kann eine bestimmte Adresse speichern, sondern nur eine Teilmenge davon. Dies macht die erforderlichen gespeicherten Adressbits noch kleiner und ermöglicht den parallelen Zugriff auf den Cache (auf jede Teilmenge kann einmal zugegriffen werden, jedoch unabhängig von den anderen Teilmengen).

Dies gilt insbesondere für die Synchronisierung des Cache- / Speicherzugriffs zwischen den verschiedenen virtuellen Kernen, ihren unabhängigen mehreren Verarbeitungseinheiten pro Kern und schließlich mehreren Prozessoren auf einem Mainboard (auf dem sich Boards mit bis zu 48 Prozessoren und mehr befinden).

Dies ist im Grunde die aktuelle Idee, warum wir Cache-Zeilen haben. Der Vorteil des Vorauslesens ist sehr hoch und der schlimmste Fall, ein einzelnes Byte aus einer Cache-Zeile zu lesen und den Rest nie wieder zu lesen, ist sehr gering, da die Wahrscheinlichkeit sehr gering ist.

Die Größe der Cache-Zeile (64) ist ein klug gewählter Kompromiss zwischen größeren Cache-Zeilen. Daher ist es unwahrscheinlich, dass das letzte Byte davon auch in naher Zukunft gelesen wird. Dies ist die Dauer, die zum Abrufen der vollständigen Cache-Zeile benötigt wird aus dem Speicher (und um es zurückzuschreiben) und auch den Overhead in der Cache-Organisation und die Parallelisierung von Cache und Speicherzugriff.

Prozessoren können mehrstufige Caches (L1, L2, L3) haben, die sich in Größe und Geschwindigkeit unterscheiden.

Um jedoch zu verstehen, was genau in jedem Cache gespeichert ist, müssen Sie den von diesem bestimmten Prozessor verwendeten Verzweigungsprädiktor untersuchen und wie sich die Anweisungen / Daten Ihres Programms dagegen verhalten.

Lesen Sie mehr über Branch Predictor , CPU Cache und Ersatzrichtlinien .

Dies ist keine leichte Aufgabe. Wenn Sie am Ende des Tages nur einen Leistungstest wünschen, können Sie ein Tool wie Cachegrind verwenden . Da es sich jedoch um eine Simulation handelt, kann das Ergebnis in gewissem Maße abweichen.

Ich kann es nicht mit Sicherheit sagen, da jede Hardware anders ist, aber es ist normalerweise "64 Bytes beginnen an der nächsten 64-Bytes-Grenze darunter", da dies eine sehr schnelle und einfache Operation für die CPU ist.