Beginn: Folie 33 Pause: Ende von OpenMP Ende: Hardware Caching Folie
Vorlesung: Gemeinsame Speichersysteme und Speicherkonsistenz
Inhaltsverzeichnis
- Einführung in Gemeinsame Speichersysteme
- NUMA vs. UMA
- Cache-Kohärenz
- Cache-Kohärenz-Protokolle
- Wahre und Falsche Teilung
- Speicherkonsistenz
- Sequential Consistency
- Moderne Hardware und Konsistenzmodelle
- Programmierung unter Berücksichtigung der Konsistenz
- Beispiele und Anwendungsfälle
- Zusammenfassung
Einführung in Gemeinsame Speichersysteme
Was sind Gemeinsame Speichersysteme?
Gemeinsame Speichersysteme ermöglichen mehreren Prozessoren oder Kernen den Zugriff auf denselben physischen Speicher. Dies erleichtert die Kommunikation und den Datenaustausch zwischen den Prozessoren, birgt jedoch Herausforderungen hinsichtlich der Konsistenz und der Performance.
Aufbau eines Gemeinsamen Speichersystems
Ein typisches gemeinsames Speichersystem besteht aus:
- Mehreren Prozessoren/Kernen: Diese teilen sich den Zugriff auf den physischen Speicher.
- Speicherhierarchie: Enthält Caches auf verschiedenen Ebenen (L1, L2, L3) und den Hauptspeicher (RAM).
- Kommunikationsmechanismen: Ermöglichen den Prozessoren den Austausch von Daten und Befehlen.
Vorteile
- Einfache Programmierung: Gemeinsamer Zugriff auf Daten erleichtert die Implementierung paralleler Algorithmen.
- Flexibilität: Dynamische Datenfreigabe und -verwaltung sind möglich.
Herausforderungen
- Cache-Kohärenz: Sicherstellung, dass alle Prozessoren konsistente Datenansichten haben.
- Speicherkonsistenz: Ordnung und Sichtbarkeit von Speicheroperationen müssen garantiert werden.
- Performance: Gemeinsamer Speicher kann zu Engpässen und erhöhtem Kommunikationsaufwand führen.
NUMA vs. UMA
UMA (Uniform Memory Access)
- Beschreibung: In UMA-Architekturen haben alle Prozessoren denselben Zugriff auf den gesamten Speicher mit gleicher Latenz und Bandbreite.
- Vorteile:
- Einfache Programmierung, da alle Speicherzugriffe gleich behandelt werden.
- Konsistente Performance bei Speicherzugriffen.
- Nachteile:
- Skalierbarkeit ist begrenzt, da der Speicherzugriff für alle Prozessoren gleich bleibt, was bei vielen Prozessoren zu Engpässen führen kann.
NUMA (Non-Uniform Memory Access)
- Beschreibung: NUMA-Architekturen verteilen den Speicher physisch auf verschiedene Knoten, wobei jeder Knoten lokalen Speicher hat, auf den seine eigenen Prozessoren schneller zugreifen können.
- Vorteile:
- Bessere Skalierbarkeit durch lokale Speicherzugriffe mit geringerer Latenz.
- Verbesserte Performance bei großskaligen Systemen.
- Nachteile:
- Komplexere Programmierung, da Speicherzugriffe je nach Standort variieren.
- Notwendigkeit von Optimierungstools wie
numactlzur Speicherzuweisung.
Vergleich
| Merkmal | UMA | NUMA |
|---|---|---|
| Speicherzugriff | Gleichmäßig für alle Prozessoren | Unterschiedlich je nach Knoten |
| Latenz | Einheitlich | Variabel, lokal schneller |
| Skalierbarkeit | Begrenzte Skalierbarkeit | Hohe Skalierbarkeit |
| Programmierung | Einfacher | Komplexer, erfordert Optimierungen |
Cache-Kohärenz
Was ist Cache-Kohärenz?
Cache-Kohärenz bezieht sich auf die Konsistenz der Daten in den verschiedenen Caches eines gemeinsamen Speichersystems. Wenn mehrere Caches dieselben Datenblöcke enthalten, müssen diese Daten konsistent gehalten werden, um Inkonsistenzen zu vermeiden.
Probleme ohne Cache-Kohärenz
- Inkonsistente Daten: Unterschiedliche Caches können unterschiedliche Werte für denselben Datenblock halten.
- Datenrennen: Gleichzeitige Schreibzugriffe können zu unvorhersehbaren Ergebnissen führen.
Cache-Kohärenz-Protokolle
Cache-Kohärenz wird durch spezielle Protokolle implementiert, die sicherstellen, dass Änderungen in einem Cache anderen Caches bekannt gemacht werden. Bekannte Protokolle sind MESI (Modified, Exclusive, Shared, Invalid) und MOESI (Modified, Owner, Exclusive, Shared, Invalid).
Cache-Kohärenz-Protokolle
Snooping
- Funktionsweise: Jeder Cache überwacht die Bus-Transaktionen (snoopt) und reagiert auf relevante Änderungen.
- Sequenzielle Sichtbarkeit: Alle Caches sehen die Transaktionen in der gleichen Reihenfolge.
- Aktionen: Bei relevanten Transaktionen können Caches ihre eigenen Kopien invalidieren oder aktualisieren.
Invalidation-Based vs. Update-Based Protokolle
Invalidation-Based Protokolle
- Beschreibung: Wenn ein Cache eine Schreiboperation auf einen Datenblock durchführt, werden alle anderen Caches, die diesen Block enthalten, invalidiert.
- Vorteile:
- Geringerer Kommunikationsaufwand bei Schreibvorgängen.
- Nachteile:
- Kann zu häufigen Invalidierungen führen, was die Performance beeinträchtigen kann.
Update-Based Protokolle
- Beschreibung: Bei einer Schreiboperation wird der neue Wert direkt an alle Caches, die den betreffenden Datenblock halten, übertragen.
- Vorteile:
- Reduziert die Anzahl der Invalidierungen.
- Nachteile:
- Höherer Kommunikationsaufwand bei jeder Schreiboperation.
Beispiel: MESI-Protokoll
Das MESI-Protokoll definiert vier Zustände für einen Datenblock in einem Cache:
- Modified (M): Der Cache besitzt die einzige Kopie des Datenblocks, der modifiziert wurde.
- Exclusive (E): Der Cache besitzt die einzige Kopie des Datenblocks, der nicht modifiziert wurde.
- Shared (S): Mehrere Caches besitzen unveränderte Kopien des Datenblocks.
- Invalid (I): Der Datenblock ist nicht mehr gültig im Cache.
Zustandsübergänge
- Shared zu Modified: Bei einer Schreiboperation wird der Datenblock modifiziert.
- Exclusive zu Shared: Wenn ein anderer Cache den Datenblock liest.
- Shared zu Invalid: Bei einer Schreiboperation in einem anderen Cache.
Wahre und Falsche Teilung
Wahre Teilung (True Sharing)
-
Definition: Mehrere Threads greifen gleichzeitig auf dasselbe Datenobjekt zu.
-
Problem: Erhöhter Cache-Kohärenz-Verkehr und potenzielle Leistungsprobleme aufgrund häufigerer Invalidationen und Aktualisierungen.
-
Beispiel:
// Gemeinsame Variable int counter = 0; // Thread 1 counter++; // Thread 2 counter++;
Falsche Teilung (False Sharing)
-
Definition: Unabhängige Datenobjekte, die jedoch auf derselben Cache-Line liegen, werden von mehreren Threads bearbeitet.
-
Problem: Unnötige Invalidation und Updates der Cache-Line, was die Performance verschlechtert, obwohl die Datenobjekte unabhängig sind.
-
Beispiel:
struct Data { int A; int B; }; Data data; // Thread 1 data.A++; // Thread 2 data.B++;Obwohl
AundBunabhängig sind, können sie auf derselben Cache-Line liegen, was zu False Sharing führt.
Lösung für False Sharing
-
Datenstruktur-Anordnung: Sicherstellen, dass unabhängige Datenobjekte auf unterschiedlichen Cache-Lines liegen.
-
Padding: Einfügen von Padding zwischen Variablen, um gemeinsame Cache-Lines zu vermeiden.
struct Data { int A; char padding[64 - sizeof(int)]; // Annahme: Cache-Line-Größe ist 64 Bytes int B; };
Speicherkonsistenz
Was ist Speicherkonsistenz?
Speicherkonsistenz definiert die Reihenfolge und Sichtbarkeit von Speicheroperationen in einem parallelen System. Sie stellt sicher, dass die Ausführung paralleler Programme vorhersehbar und korrekt ist.
Arten von Speicherkonsistenz
- Sequential Consistency
- Relaxed Consistency Models
Sequential Consistency
Definition
Eine Ausführung ist sequential konsistent, wenn die Operationen aller Prozessoren so ausgeführt werden, als ob sie in einer sequentiellen Reihenfolge stattfinden, und die Operationen jedes einzelnen Prozessors in der vom Programm spezifizierten Reihenfolge erscheinen.
Formell von Leslie Lamport definiert:
Eigenschaften
- Globale Reihenfolge: Es existiert eine globale, sequentielle Reihenfolge aller Speicheroperationen.
- Programmreihenfolge: Die Reihenfolge der Operationen innerhalb eines einzelnen Threads entspricht der Programmierspezifikation.
Vorteile
- Einfaches Verständnis: Erleichtert das Reasoning über parallele Programme.
- Vorhersagbare Ergebnisse: Garantiert konsistente und erwartete Ergebnisse.
Herausforderungen
- Reihenfolge der Operationen: Moderne CPUs führen oft Umordnungen von Operationen durch, um die Performance zu verbessern, was Sequential Consistency verletzen kann.
- Performance-Einbußen: Strikte Einhaltung kann die Performance einschränken.
Beispiel
Betrachten wir zwei Threads, die auf gemeinsame Variablen zugreifen:
// Gemeinsame Variablen
int X = 0;
int Y = 0;
// Thread 1
X = 1;
flag = true;
// Thread 2
while (!flag) {}
print(Y);Frage: Ist garantiert, dass print(Y) den Wert 1 anzeigt?
Sequential Consistency garantiert dies, da die Operationen in einer konsistenten Reihenfolge ausgeführt werden.
Moderne Hardware und Konsistenzmodelle
Relaxed Consistency Models
- Beschreibung: Lockerere Konsistenzmodelle erlauben Umordnungen von Speicheroperationen, um die Performance zu steigern.
- Beispiele:
- PSO (Partial Store Order): Erlaubt Umordnungen bei Speicheroperationen, die keine Abhängigkeiten haben.
- TSO (Total Store Order): Gewährleistet eine globale Reihenfolge von Schreiboperationen, erlaubt jedoch bestimmte Umordnungen.
Unterschiede zu Sequential Consistency
- Reihenfolge: Sequential Consistency erzwingt eine strikte Reihenfolge, während Relaxed Models dies nicht tun.
- Performance: Relaxed Models ermöglichen höhere Performance durch Optimierungen wie Out-of-Order Execution.
Synchronisationsmechanismen
- Memory Barriers: Befehle, die die Reihenfolge von Speicheroperationen erzwingen.
- Atomare Operationen: Operationen, die unteilbar sind und konsistente Speicherzugriffe sicherstellen.
Programmierung unter Berücksichtigung der Konsistenz
Atomare Typen und Operationen
-
C++ Atomics: Verwendung von
std::atomicTypen und Operationen, um atomare und konsistente Speicherzugriffe sicherzustellen.#include <atomic> std::atomic<int> counter(0); void increment() { counter.fetch_add(1, std::memory_order_seq_cst); } -
Memory Orders:
std::memory_order_seq_cst: Sequenzielle Konsistenz.std::memory_order_relaxed: Relaxed Order.- Weitere:
memory_order_acquire,memory_order_release, etc.
Best Practices
- Minimierung von Datenrennen: Verwendung von Synchronisationsmechanismen wie Mutexen oder atomaren Operationen, um gleichzeitigen Zugriff auf gemeinsame Daten zu kontrollieren.
- Vermeidung von False Sharing: Strukturierung von Daten, um unabhängige Daten auf unterschiedlichen Cache-Lines zu platzieren.
- Einsatz von Memory Barriers: Sicherstellung der gewünschten Reihenfolge von Speicheroperationen.
Beispiele und Anwendungsfälle
Beispiel 1: Cache-Kohärenz und Sequential Consistency
Betrachten wir drei Schritte, bei denen zwei Prozessoren auf dieselbe Variable U zugreifen:
- Initialisierung:
U = 5im Hauptspeicher. - Prozessor 1 liest
U: Kopie in Cache von Prozessor 1 (U_P1 = 5). - Prozessor 2 liest
U: Kopie in Cache von Prozessor 2 (U_P2 = 5). - Prozessor 1 schreibt
U = 7: AktualisiertU_P1und den Hauptspeicher. - Prozessor 2 liest
U: Je nach Protokoll und Timing könnteU_P2entweder5oder7sein.
Sequential Consistency
Wenn das System sequential konsistent ist, muss die Reihenfolge der Operationen so sein, dass alle Prozessoren konsistente Ansichten haben. Daher sollte U_P2 nach der Schreiboperation 7 sein.
Beispiel 2: False Sharing
struct Data {
int A;
int B;
};
Data data;
// Thread 1
data.A++;
// Thread 2
data.B++;Obwohl A und B unabhängig sind, können sie auf derselben Cache-Line liegen. Dies führt zu False Sharing, da Änderungen an A die Cache-Line für Thread 2 invalidieren und umgekehrt.
Lösung
struct Data {
int A;
char padding[64 - sizeof(int)]; // Annahme: Cache-Line-Größe ist 64 Bytes
int B;
};Durch Padding werden A und B auf unterschiedlichen Cache-Lines platziert, wodurch False Sharing vermieden wird.
Zusammenfassung
- Gemeinsame Speichersysteme bieten hohe Performance durch gemeinsame Nutzung von Daten, bringen jedoch Herausforderungen wie Cache-Kohärenz und False Sharing mit sich.
- NUMA und UMA sind Architekturen zur Speicherzugriffsverwaltung, wobei NUMA realistischere Zugriffszeiten in modernen Systemen widerspiegelt.
- Cache-Kohärenz-Protokolle wie Snooping stellen sicher, dass alle Caches konsistente Daten halten.
- Speicherkonsistenzmodelle definieren die Reihenfolge und Sichtbarkeit von Speicheroperationen, wobei Sequential Consistency einfach zu verstehen, aber in modernen CPUs oft nicht vollständig gewährleistet ist.
- Programmierung in parallelen Systemen erfordert den Einsatz von Synchronisationsmechanismen und bewährten Methoden, um Konsistenz und Performance sicherzustellen.
- Beispiele verdeutlichen die Bedeutung von Cache-Kohärenz und die Probleme von False Sharing.