Prozessorintern

[Che]

Ich hab da mal eine Frage :)
Handelsübliche L2-Caches sind ja 256-512 KByte groß, und darin werden soweit ich weiß Daten gespeichert. (Die Befehle kommen in den L1 Cache)
Wenn ich nun ein Array von zB 100.000 doubles habe, dann belegt das 800.000 Byte (100.000 mal 8 Byte) = 800 Kbyte, und das passt nicht mehr in den Cache. Ein Teil wird also im vergleichsweise langsamen Arbeitspeicher abgelegt, und wenn ich jetzt das Array Eement für Element kopiere, dann erfolgen die Lese- und Schreibzugriffe zum Teil im Cache (was schnell ist) und zum Teil im Arbeitspeicher (was langsam ist).
Hätte mein Array dagegen nur 10.000 Elemente, dann würde es komplett in den Cache passen und die ganze Aktion müsste spürbar schneller sein.

Läuft das ganze ungefähr so ab oder ist es doch ein bisschen komplizierter?

MfG

[Demirug]

Ein bischen komplizierter ist das schon. Zu erst mal gibt es auch einen L1 Cache für Daten.

Bei Zugriff auf daten "sucht" der Chip zuerst im L1 dann im L2 und am Ende im Hauptspeicher danach. zwichen L2 und Hauptspeicher können dabei im Prinzip noch weitere Caches liegen. Gleichzeitig versucht der Chip auch noch abzuschätzen welche Daten als nächstes gebraucht werden und diese schon mal auf verdacht in einen Cache zu laden. Das Abschätzen läuft aber meistens darauf hinaus das einfach die nähere Umgebung geladen wird. Wenn etwas neues in den Cache geladen wird muss natürlich was anderes dafür entfernt werden.

Was das kalkulieren von Cacheeffekten noch komplizierter macht ist das man den Cache ja nicht für sich aleine hat sondern ihn mit anderen Threads teilen muss.

Die besten Tricks beim optimieren sind:

- Datenmenge reduzieren (müssen es wirklich doubles sein oder reichen auch floats)
- Daten die zusammen verarbeitet werden müssen dicht zusammenspeichern. (Ein Array mit Strukturen ist meisten besser als eine Struktur mit Arrays)

[Muh-sagt-die-Kuh]

So....ich gehe den ganzen Vorgang jetzt anhand deine Beispiels einfach mal schritt für Schritt durch.

Prinzipiell ist das ganze ein einfache Memcopy Schleife, also eine einfache Abfolge von Loads und Stores.

Du hast hier zudem ein eindimensionales Array, also einen zusammenhängenden Speicherblock.

Beim laden des ersten Array-elements in ein Register geschieht nun folgendes: die CPU schaut im L1 Data Cache nach ob die angeforderte Speicheradresse vorhanden ist (ich gehe nun davon aus, sie sich weder im L1 noch im L2 befindet), in unserem Falle ist sie es nicht, also geht die CPU in den L2 Cache und schaut dort nach ob die Speicheradresse vorhanden ist, hier ist die Adresse auch nicht vorhanden, also ist ein Speicherzugriff notwendig und die Adresse und ihre benachbarten Bytes (64 bytes, eine Cacheline beim P4) wird in den L1 + L2 Cache geladen (intel Cachearchitektur, der L2 Cache enthält immer eine Kopie des L1 Caches), der Inhalt der Speicheradresse wird nun in ein Register geladen.

Als nächstes folgt ein store, auch hier gehen wir von L1 und L2 miss aus, und die Zieladresse und Umgebung wird auch in L1 und L2 eingelagert.

Von nun an sollte für das gesamte Array kein einziger L2 Miss mehr auftreten, da die Adressen sequentiell abgearbeitet werden, was für die Prefetch-logik sehr leicht zu erkennen ist und automatisch zum laden der nächsten angeforderten Adresse in den L2 Cache führt. Nur alle 64 byte geteilt durch Datenelementgröße tritt ein L1 miss auf.

Wie du siehst ist dein genanntes Beispiel selbst für einen absolut winzigen Cache kein Problem. ;)

[Muh-sagt-die-Kuh]

Originally posted by Demirug
Was das kalkulieren von Cacheeffekten noch komplizierter macht ist das man den Cache ja nicht für sich aleine hat sondern ihn mit anderen Threads teilen muss.Bei einer Hyperthreading (allgemeiner SMT) CPU ist das so, bei einer normalen CPU erzeugt ein Threadwechsel nur zu Beginn der Ausführung eine ganze Reihe von Cache-misses, da sich normalerweise ausschliesslich Code und Daten des alten Threads im Cache befinden. Während der Laufzeit eines Threads ergeben sich dagegen keine Probleme.

[Demirug]

Originally posted by Muh-sagt-die-Kuh
Bei einer Hyperthreading (allgemeiner SMT) CPU ist das so, bei einer normalen CPU erzeugt ein Threadwechsel nur zu Beginn der Ausführung eine ganze Reihe von Cache-misses, da sich normalerweise ausschliesslich Code und Daten des alten Threads im Cache befinden. Während der Laufzeit eines Threads ergeben sich dagegen keine Probleme.

So war das ja auch gemeint. ;)

Es ging mir darum das man sich nicht darauf verlassen darf das wenn man Daten einmal zum begin einer Funktion in den Cache geladen hat diese später auch noch dort sind da es ja in der zwischenzeit zu einem Thread Wechsel gekommen sein könnte.

[Muh-sagt-die-Kuh]

Originally posted by Demirug


So war das ja auch gemeint. ;)

Es ging mir darum das man sich nicht darauf verlassen darf das wenn man Daten einmal zum begin einer Funktion in den Cache geladen hat diese später auch noch dort sind da es ja in der zwischenzeit zu einem Thread Wechsel gekommen sein könnte. OK, ich dachte wohl an räumliche Teilung, du an zeitliche ;)

[GloomY]

Originally posted by Muh-sagt-die-Kuh
So....ich gehe den ganzen Vorgang jetzt anhand deine Beispiels einfach mal schritt für Schritt durch.

Prinzipiell ist das ganze ein einfache Memcopy Schleife, also eine einfache Abfolge von Loads und Stores.

Du hast hier zudem ein eindimensionales Array, also einen zusammenhängenden Speicherblock.

Beim laden des ersten Array-elements in ein Register geschieht nun folgendes: die CPU schaut im L1 Data Cache nach ob die angeforderte Speicheradresse vorhanden ist (ich gehe nun davon aus, sie sich weder im L1 noch im L2 befindet), in unserem Falle ist sie es nicht, also geht die CPU in den L2 Cache und schaut dort nach ob die Speicheradresse vorhanden ist, hier ist die Adresse auch nicht vorhanden, also ist ein Speicherzugriff notwendig und die Adresse und ihre benachbarten Bytes (64 bytes, eine Cacheline beim P4) wird in den L1 + L2 Cache geladen (intel Cachearchitektur, der L2 Cache enthält immer eine Kopie des L1 Caches), der Inhalt der Speicheradresse wird nun in ein Register geladen.

Als nächstes folgt ein store, auch hier gehen wir von L1 und L2 miss aus, und die Zieladresse und Umgebung wird auch in L1 und L2 eingelagert.

Von nun an sollte für das gesamte Array kein einziger L2 Miss mehr auftreten, da die Adressen sequentiell abgearbeitet werden, was für die Prefetch-logik sehr leicht zu erkennen ist und automatisch zum laden der nächsten angeforderten Adresse in den L2 Cache führt. Nur alle 64 byte geteilt durch Datenelementgröße tritt ein L1 miss auf.

Wie du siehst ist dein genanntes Beispiel selbst für einen absolut winzigen Cache kein Problem. ;) Wobei aber letztlich trotzdem der Hauptspeicher limitiert (genauer: die Bandbreite), da das Lesen / Schreiben in den Cache sehr viel schneller geht, als die Cache Lines aus dem Hauptspeicher zu holen.

[Muh-sagt-die-Kuh]

Originally posted by GloomY
Wobei aber letztlich trotzdem der Hauptspeicher limitiert (genauer: die Bandbreite), da das Lesen / Schreiben in den Cache sehr viel schneller geht, als die Cache Lines aus dem Hauptspeicher zu holen. Mist, da hab ich doch glatt als Vorraussetzung "unendliche Bandbreite" vergessen ;)

Natürlich hast du Recht, nehmen wir an, eine CPU kann pro Takt 4 bytes lesen und schreiben und das dann 2.400.000.000 mal pro Sekunde (in diesem Beispiel 2,4 Ghz) kommt man auf eine astronomisch hohe Bandbreite von 2 * 9,6 GB/sec, der 533 mhz 64 bit FSB kann aber theoretisch nur 4,2 GB/sec liefern und praktisch noch weniger...

Naja, der Zweck des Postes war eigentlich, ihm klarzumachen wie ein Cache arbeiten....irgendwie muss ich dabei die Bandbreite komplett übersehen haben.

[GloomY]

Originally posted by Muh-sagt-die-Kuh
Mist, da hab ich doch glatt als Vorraussetzung "unendliche Bandbreite" vergessen ;)

Natürlich hast du Recht, nehmen wir an, eine CPU kann pro Takt 4 bytes lesen und schreiben und das dann 2.400.000.000 mal pro Sekunde (in diesem Beispiel 2,4 Ghz) kommt man auf eine astronomisch hohe Bandbreite von 2 * 9,6 GB/sec, der 533 mhz 64 bit FSB kann aber theoretisch nur 4,2 GB/sec liefern und praktisch noch weniger...

Naja, der Zweck des Postes war eigentlich, ihm klarzumachen wie ein Cache arbeiten....irgendwie muss ich dabei die Bandbreite komplett übersehen haben. Ich fand deine Erklärung auch ganz gut. Mein Posting war nur als Anmerkung gedacht, weil der Threadstarter gefragt hatte, was passiert, wenn nun nicht alle Daten in die Caches passen und ob damit die Cache-Größe bedeutenden Einfluss hat oder nicht. Und die ist in dem Beispiel realtiv egal.

[Che]

Ok, hab ich soweit alles verstanden. Wenn nun aber die Daten nicht schön in einem einzigen Block liegen (sondern "verstreut"), dannfunktioniert die ganze Sache nicht mehr...

[Muh-sagt-die-Kuh]

Originally posted by Che
Ok, hab ich soweit alles verstanden. Wenn nun aber die Daten nicht schön in einem einzigen Block liegen (sondern "verstreut"), dannfunktioniert die ganze Sache nicht mehr... Generell ist die Cachegröße bei Einmalzugriffen wie du sie hier ansprichst nicht besonders wichtig, bei Memcopy mit verstreuten Daten gibt es eigentlich nur Cache Misses, bei einer reinen Zufallsverteilung bei fast jedem Zugriff...das wird dann richtig übel, die ganzen DRAM Latenzen kommen voll zum Tragen. Solche Fälle sind aber in der Praxis nicht oft anzutreffen, zu der angesprochenen räumlichen Lokalität (hintereinander angeforderte Daten liegen meist in der Nähe des ersten Datums) kommt dann auch noch zeitliche Lokalität (auf die gleichen Adressen wird in einem recht kurzen Zeitraum mehrfach zugegriffen).

Grundsätzlich gilt:
Je komplexer ein Programm (bzw die Kernschleifen) ist und je zufälliger es auf Daten zugreift (bzw. je sprungintensiver sein Code ist) desto wichtiger wird die Cachegröße. Bei einem zu kleinen Cache (Cachegröße < größe Kernschleifen / Daten) kommt es dann zu intensiven Einlagerungs- / Auslagerungsprozessen die zu massig Hauptspeicherzugriffen und somit Wartezyklen für die CPU führen.