Parallele Systeme - Cheatsheet

SIMD, MIMD und SPMD Architekturen

Definition:

Details:

• SIMD (Single Instruction, Multiple Data): Ein Befehl verarbeitet mehrere Daten gleichzeitig, ideal für Vektor- und Matrixoperationen.
• MIMD (Multiple Instruction, Multiple Data): Mehrere Befehle werden auf mehreren Daten gleichzeitig ausgeführt, geeignet für komplexe, parallele Berechnungen.
• SPMD (Single Program, Multiple Data): Ein Programm verarbeitet mehrere Datenströme gleichzeitig, oft in verteilten Systemen verwendet.

Speichermodelle und -hierarchien

Definition:

Arten der Speicherorganisation und deren Strukturen in parallelen Systemen.

Details:

• Speichermodelle definieren Sichtweise auf die Speicherverteilung
• Hierarchie: Register > Cache > Hauptspeicher > Sekundärspeicher
• Cache-Kohärenz notwendig für Konsistenz
• Memory-Systeme: NUMA, UMA
• Datenplatzierung und -verteilung wichtig für Performance
• Konsistenzmodelle: z.B. Strong, Eventual

Cache-Kohärenz und Speicherordnung

Definition:

Konsistenz von Daten in mehreren Caches eines Mehrprozessorsystems sicherstellen.

Details:

• Drei Entscheidungsaspekte: Schreibstrategie, Speicherordnung, Cache-Kohärenzprotokoll
• Schreibstrategien: Write-Through vs. Write-Back
• Speicherordnungsmodelle: Sequentielle Konsistenz, Locker Modelle (z. B. TSO, PSO, RMO)
• Kohärenzprotokolle: MSI, MESI, MOESI, Dragon
• Kohärenzprotokoll überwacht und koordiniert Cache-Operationen (z.B. Invalidierung, Aktualisierung)
• Cache-Linien: Granularität der Datenverwaltung in Caches
• Einfluss auf Performance und Komplexität des Systems

Thread-basierte Programmierung und Thread-Bibliotheken

Definition:

Thread-basierte Programmierung nutzt Threads, um paralleles Rechnen zu ermöglichen; Threads laufen innerhalb eines Prozesses und teilen sich Ressourcen.

Details:

• Threads ermöglicht parallele Ausführung im gleichen Adressraum.
• Vorteile: Effizientere Nutzung von Mehrkernprozessoren, geringere Erstellungskosten verglichen mit Prozessen.
• Herausforderungen: Synchronisation (z.B. Deadlocks), gemeinsame Nutzung von Ressourcen.
• Wichtige Bibliotheken:
  • Pthreads (POSIX Threads)
  • Java Threads
  • C++11 Threads
• Thread-Synchronisation: Mutex, Semaphore, Condition Variables.
• Wichtige Funktionen: pthread_create, pthread_join, std::thread (C++)

Message Passing Interface (MPI) und OpenMP

Definition:

Kommunikationsprotokoll für paralleles Rechnen; MPI: Nachrichten zwischen Prozessen, OpenMP: parallele Threads in gemeinsamem Speicher

Details:

• MPI: Skalierbare Kommunikation für parallele Programme, geeignet für verteilte Systeme
• OpenMP: Direktivesatz zur Parallelisierung in gemeinsamen Speichermodellen, einfacher Zugang über Compiler-Direktiven
• MPI Wichtige Funktionen: \texttt{MPI\textunderscore Init}, \texttt{MPI\textunderscore Comm\textunderscore Size}, \texttt{MPI\textunderscore Comm\textunderscore Rank}, \texttt{MPI\textunderscore Send}, \texttt{MPI\textunderscore Recv}
• OpenMP Direktiven: \texttt{\text#pragma omp parallel}, \texttt{\text#pragma omp for}, \texttt{\text#pragma omp critical}
• Ziel von beiden: Performance-Steigerung durch parallele Ausführung

GPGPU-Programmierung mit CUDA und OpenCL

Definition:

GPGPU-Programmierung mit CUDA und OpenCL bezieht sich auf die Nutzung von GPUs zur allgemeinen Berechnung (nicht nur Grafik). CUDA von NVIDIA und OpenCL (offener Standard) sind Frameworks zur Programmierung von GPUs für parallele Berechnungen.

Details:

• CUDA: Proprietäres Framework von NVIDIA, erlaubt direkte Programmierung der NVIDIA-GPUs.
• OpenCL: Offener Standard für heterogene Systeme (CPUs, GPUs).
• Wichtig: Speicherhierarchie, Synchronisation, Thread-Management.
• CUDA-Kernels: Funktionen, die auf der GPU ausgeführt werden.
• OpenCL: Plattformmodell, Ausführungsmodell, Speichermodell.
• Performance-Optimierung: Speicherzugriffsmuster, Thread-Divergenz.

Mutexe, Semaphoren und Lock-Free Programmierung

Definition:

Mechanismen zur Synchronisierung und Steuerung des Zugriffs auf gemeinsame Ressourcen in parallelen Systemen.

Details:

• Mutexe: Sicherstellen, dass nur ein Thread zur gleichen Zeit eine Ressource nutzt.
• Implementierung: lock() und unlock() Methoden.
• Semaphoren: Verwalten des Zugriffs auf eine begrenzte Anzahl von Resourcen mit Zähler; binäre (1 Resource) oder zählende (n-Resourcen) Semaphoren.
• Operationen: wait() bzw. P() und signal() bzw. V().
• Lock-Free Programmierung: Algorithmen, die auf Sperren verzichten, um Deadlocks zu vermeiden und parallele Effizienz zu steigern.
• Technik: Vergleiche und Tausch (CAS), compare-and-swap Operation.

Performance Metriken, Benchmarking und Optimierungstechniken

Definition:

Bewertung und Verbesserung der Leistung paralleler Systeme durch spezifische Metriken, Vergleichsmaßstäbe und Optimierungsmethoden.

Details:

• Wichtige Metriken:
  • Durchsatz (\textit{throughput})
  • Ausführungszeit (\textit{execution time})
  • Skalierbarkeit
  • Effizienz
  • Lastverteilung
• Benchmarking:
  • Standardisierte Tests zur Bewertung der Systemleistung
  • Verwendung von Benchmarks wie LINPACK, NAS Parallel Benchmarks
• Optimierungstechniken:
  • Lastverteilung und Lastbalancierung
  • Parallelisierungstechniken
  • Kommunikationsreduzierung
  • Verwendung von leistungsstarken Bibliotheken und Algorithmen