Programming Techniques for Supercomputers - Cheatsheet

Grundlagen der Supercomputer-Architekturen

Definition:

Architektonische Grundlagen von Supercomputern, einschließlich Aufbau, Komponenten und Leistungsfaktoren.

Details:

• Skalierbarkeit: Erhöhung der Rechnerleistung durch Hinzufügen von Prozessoren (\textit{horizontal}) oder Verbesserung der einzelnen Komponenten (\textit{vertikal}).
• Parallelität: Gleichzeitige Ausführung mehrerer Berechnungen zur Beschleunigung der Datenverarbeitung. Kann unterteilt werden in \textit{Datenparallelität} und \textit{Aufgabenparallelität}.
• Speicher-Architektur: Nutzung von hierarchischem Speicher (Cache, RAM, Festplatte), \textit{Shared Memory} vs. \textit{Distributed Memory}.
• Netzwerk-Topologie: Physische und logische Struktur der Verbindungen zwischen Prozessorknoten, z.B. \textit{Torus}, \textit{Hypercube}, \textit{Fat-Tree}.
• Leistungskennzahlen: \textit{FLOPS} (Floating Point Operations Per Second) als Maß für die Performance, Benchmarks wie \textit{HPCG} und \textit{HPL}.
• Fehlertoleranz: Techniken zur Sicherstellung von Zuverlässigkeit und Verfügbarkeit, wie z.B. \textit{ECC} (Error Correcting Code) Speicher und \textit{Checkpoint-Restart} Strategien.
• Lastverteilung: Strategien zur effizienten Ressourcennutzung, z.B. \textit{load balancing} und \textit{scheduling}.
• Energieeffizienz: Wichtiger Faktor aufgrund des hohen Energieverbrauchs. Optimierungen durch Hardware-Architektur und Software-Algorithmen.

Leistungsmessung und -analyse

Definition:

Prozesse und Techniken zur Bewertung und Optimierung der Leistungsfähigkeit von Programmen auf Supercomputern.

Details:

• Wichtige Metriken: Durchsatz, Latenz, Rechenleistung, Speicherbandbreite.
• Verwendung von Profiling-Tools (z.B. gprof, Intel VTune).
• Messgeräte: Hardware-Counter, Software-Profiler.
• Analysetechniken: Bottleneck-Identifikation, Skalierbarkeitsanalyse.
• Formeln: \[ \text{Speedup} = \frac{T_{serial}}{T_{parallel}} \] \[ \text{Effizienz} = \frac{Speedup}{N} \]

Shared Memory und Distributed Memory Modelle

Definition:

Shared Memory: Alle Prozessoren greifen auf denselben Speicher zu. Distributed Memory: Jeder Prozessor hat seinen eigenen lokalen Speicher.

Details:

• Shared Memory: Einfachere Programmierung, aber Skalierung limitiert durch Speicherbandbreite und Koordinationskosten.
• Distributed Memory: Bessere Skalierung, aber komplexere Programmierung durch explizite Datenverteilung und Kommunikation.
• Kommunikationsmethoden: Shared Memory nutzt Threads (oft POSIX Threads), Distributed Memory nutzt häufig Message Passing Interface (MPI).
• Performance hängt von Speicherarchitektur und Kommunikationskosten ab.

Techniken zur Lastenverteilung

Definition:

Techniken zur Verteilung der Arbeitslast auf mehrere Prozessoren oder Knoten, um die Gesamtleistung eines Supercomputers zu optimieren.

Details:

• Statische Lastenverteilung: Arbeitslast im Voraus festgelegt, z.B. Round-Robin oder Block-Verteilung.
• Dynamische Lastenverteilung: Arbeitslast basierend auf aktuelle Belastung der Prozessoren verteilt, z.B. Work Stealing oder zentrale Lastverteilung.
• Partitionierungstechniken: Aufteilung der Daten basierend auf Problemstruktur, z.B. Domain Decomposition.
• Load Balancing Algorithmen: Verschiedene Algorithmen wie Kernighan-Lin, Metis für Graphpartitionierung.
• Kommunikation: Overhead minimieren durch asynchrone Kommunikation und Pipelining.

Optimierung von Speicherzugriffsmustern

Definition:

Optimierung von Speicherzugriffsmustern zielt darauf ab, die Effizienz der Speicherzugriffe zu maximieren, um die Gesamtleistung eines Programms auf Supercomputern zu verbessern.

Details:

• Zugriffsmuster analysieren und optimieren: Cache-Effizienz erhöhen
• Vermeiden von Cache-Misses: Datenlokalität, Prefetching
• Speicheralignierung berücksichtigen
• Verwendung von SIMD-Instruktionen zur Verbesserung der Parallelität
• Datenstrukturen so anpassen, dass sie besser mit der Speicherhierarchie interagieren

Parallelisierung von Algorithmen

Definition:

Gleichzeitige Ausführung von Teilen eines Algorithmus auf mehreren Prozessoren zur Reduzierung der Gesamtlaufzeit.

Details:

• Amdahls Gesetz: \[ S = \frac{1}{(1 - P) + \frac{P}{N}} \] beschreibt das theoretische Geschwindigkeitslimit basierend auf dem parallelen Anteil \( P \) und der Anzahl der Prozessoren \( N \).
• Lastverteilung: Effiziente Zuweisung von Aufgaben an Prozessoren, um Überlastung zu vermeiden.
• Kommunikation und Synchronisation: Wichtige Faktoren zur Minimierung von Overhead und zur Gewährleistung der korrekten Reihenfolge der Teilergebnisse.
• Datenabhängigkeiten: Müssen analysiert und minimiert werden, um einen hohen Grad an Parallelisierung zu erreichen.
• Gängige Modelle: Shared Memory (z.B., OpenMP), Distributed Memory (z.B., MPI).

Kommunikationsprotokolle und -techniken

Definition:

Kommunikationsprotokolle und -techniken für die effiziente und parallele Datenverarbeitung auf Supercomputern.

Details:

• MPI (Message Passing Interface): Standard für parallele Programmierung, ermöglicht den Austausch von Nachrichten zwischen Prozessen.
• P2P (Peer-to-Peer): Direktkommunikation zwischen zwei Knoten.
• Collective Communication: Kommunikation zwischen mehreren Prozessen gleichzeitig, z.B. Broadcast, Scatter, Gather.
• Topologien: Struktur der Kommunikation, z.B. Mesh, Torus, Hypercube.
• Übertragungsmodi: Synchronous (blockierend) vs. Asynchronous (nicht blockierend) Kommunikation.
• Netzwerkprotokolle: TCP/IP, InfiniBand.

Strategien zur Minimierung der Latenz

Definition:

Strategien zur Reduzierung der Verzögerung, die bei der Datenübertragung und -verarbeitung auf Supercomputern auftreten.

Details:

• Datenlokalität maximieren: Daten so nah wie möglich an der Verarbeitungseinheit halten
• Asynchrone Kommunikation: Überlappen von Kommunikation und Berechnung
• Pipelining: Aufgaben so aufteilen, dass kontinuierlich gearbeitet wird
• Caching: Zwischenspeicherung von häufig genutzten Daten
• Prefetching: Vorausschauendes Laden von Daten
• Speicherhierarchien nutzen: Effektive Verwendung von Register, Cache und Hauptspeicher
• Vermeidung von Synchronisationspunkten: Reduktion von Wartezeiten zwischen Threads/Prozessen