Parallele und Funktionale Programmierung - Cheatsheet

Datenparallelität vs. Task-Parallelität

Definition:

Datenparallelität: Gleiche Operation auf verschiedenen Daten gleichzeitig. Task-Parallelität: Verschiedene Operationen gleichzeitig auf unterschiedlichen Daten.

Details:

• Datenparallelität: Verwendet SIMD (Single Instruction, Multiple Data), basiert auf Datenpartitionierung
• Task-Parallelität: Verwendet MIMD (Multiple Instructions, Multiple Data), basiert auf Aufgabenpartitionierung
• Beispiel Datenparallelität: Matrixmultiplikation
• Beispiel Task-Parallelität: Web-Server, der verschiedene Anfragen bearbeitet
• Optimierungskriterien: Datenparallelität - Datenverteilung, Task-Parallelität - Lastverteilung

Techniken zur Synchronisation: Mutex, Semaphore, Locks

Definition:

Verfahren zur Steuerung des gleichzeitigen Zugriffs auf gemeinsame Ressourcen in parallelen Programmierungen.

Details:

• Mutex: Erlaubt nur einem Thread gleichzeitig den Zugriff. Wird mit lock() und unlock() gesteuert.
• Semaphore: Stellt eine gezählte Anzahl an gleichzeitigen Zugriffen bereit. Wird mit wait() und signal() kontrolliert. In seiner einfachsten Form ist ein Binärsemafor (0 oder 1) ein Mutex.
• Locks: Allgemeine Methode zur Ressourcen-Synchronisation, implementiert mittels Mutex, Reader-Writer-Locks, oder Spinlocks.

Fehlersuche in parallelen Programmen: Race Conditions und Deadlocks

Definition:

Fehlersuche in parallelen Programmen konzentriert sich auf die Identifikation und Behebung von Race Conditions und Deadlocks.

Details:

• Race Condition: Tritt auf, wenn der Output eines Programms von der nicht-deterministischen Reihenfolge abhängt, in der Threads oder Prozesse ausgeführt werden.
• Vermeidung: Verwende Synchronisationsmechanismen wie Locks, Semaphoren, oder Mutex.
• Deadlock: Erhält Zwei oder mehr Threads sind gegenseitig blockiert, weil jeder auf eine Ressource wartet, die der andere hält.
• Verhinderung: Vermeidung zyklischen Wartens durch Ressourcenzuweisung in einer festen Reihenfolge oder durch Verwendung von Deadlock-Erkennungs-Algorithmen.

Einführung und Syntax von Erlang

Definition:

Einführung in die Grundlagen von Erlang und dessen grundlegende Syntax.

Details:

• Erlang ist eine funktionale Programmiersprache, besonders geeignet für parallele und verteilte Systeme.
• Kein Zustand und keine Nebenwirkungen - reine Funktionen.
• Hauptmerkmale: Pattern Matching, Rekursion, Leichtigkeit bei der Erstellung von nebenläufigen Prozessen.
• Variablen sind einmal zuweisbar (immutable).
• Syntax Beispiele:
• Zuweisung: Var = Ausdruck
• Funktionendefinition: funktionsname(Parameter) -> Ausdruck.
• Modulerstellung: -module(modulname). -export([funktionsname/anzahl_der_parameter]).
• Prozess-Erstellung: spawn(fun() -> Ausdruck end)
• Pattern Matching: [H|T] = [1,2,3] (H=1, T=[2,3])

Architekturen moderner Prozessoren und deren Parallelitätsfeatures

Definition:

Architekturen moderner Prozessoren und deren Parallelitätsfeatures - wichtig für effizientes paralleles und funktionales Programmieren.

Details:

• Multicore-Prozessoren: Mehrere Kerne zur gleichzeitigen Ausführung von Threads.
• SIMD (Single Instruction, Multiple Data): Eine Anweisung auf mehrere Datenobjekte gleichzeitig anwenden.
• Hyper-Threading: Simuliert zusätzliche Kerne durch parallele Thread-Bearbeitung.
• Cache-Kohärenz: Konsistenz des Cache-Speichers bei Verwendung mehrerer Kerne.
• Speicherzugriffsmodelle: NUMA (Non-Uniform Memory Access) vs. UMA (Uniform Memory Access).
• GPGPU (General-Purpose computing on Graphics Processing Units): Nutzung von GPUs für allgemeine Rechenaufgaben.

Lazy Evaluation und ihre Vorteile

Definition:

Lazy Evaluation bedeutet, dass Ausdrücke nur dann ausgewertet werden, wenn sie tatsächlich benötigt werden.

Details:

• Verzögerte Berechnung: Berechnungen nur bei Bedarf ausgeführt.
• Speichereffizienz: Reduzierung des Speicherkonsums, da unnötige Berechnungen vermieden werden.
• Unendliche Datenstrukturen: Ermöglicht die Verwendung von unendlichen Listen und Streams.
• Leichtere Fehleranalyse: Probleme können oft frühzeitig erkannt und behoben werden.
• Beispiel in Haskell: let x = [1..] in take 5 x liefert [1, 2, 3, 4, 5]

Verteilte Algorithmen: Leader Election, Konsensus-Algorithmen

Definition:

Verteilte Algorithmen zur Leader-Wahl und Konsensus-Algorithmen ermöglichen es, dass mehrere Prozesse in einem verteilten System koordiniert zusammenarbeiten und sich auf gemeinsame Entscheidungen einigen.

Details:

• \textbf{Leader Election}: Bestimmt einen einzelnen Prozess (Leader), der bestimmte Aufgaben ausführt und das System koordiniert. Wichtige Algorithmen: Bully-Algorithmus, Ring-Algorithmus.
• \textbf{Bullying-Algorithmus}: Der Prozess mit der höchsten ID gewinnt, Kommunikation zwischen Prozessen zur Bestimmung des höchsten.
• \textbf{Ring-Algorithmus}: Prozesse sind in einem Ring verbunden, jeder Prozess gibt seine ID weiter, der höchste gewinnt.
• \textbf{Konsensus-Algorithmen}: Stellen sicher, dass alle Knoten eine einheitliche Entscheidung treffen, selbst bei ausfallenden Knoten. Wichtige Algorithmen: Paxos, Raft.
• \textbf{Paxos}: Erfordert eine Mehrheit der Knoten, um eine Entscheidung zu treffen, besteht aus Propose, Prepare und Accept Phasen.
• \textbf{Raft}: Einfachere Implementierung von Paxos in praktischen Systemen, teilt in Leader- und Follower-Rollen, benutzt Log-Replikation zur Konsenfindung.
• \textbf{Verwendung}: Wesentlich in verteilten Datenbanken, Fault-Tolerance-Systemen und verteilten Anwendungen.

Werkzeuge und Bibliotheken für parallele Programmierung (OpenMP, MPI)

Definition:

Werkzeuge und Bibliotheken für parallele Programmierung (OpenMP, MPI) bieten APIs und Laufzeitumgebungen zum Schreiben paralleler Programme; wichtig für effiziente Ressourcennutzung auf Multicore-Prozessoren und verteilten Systemen.

Details:

• OpenMP: API für paralleles Programmieren in C, C++ und Fortran; nutzt Compiler-Direktiven.
• Merkmale von OpenMP: Parallel Regionen, Schleifenparallelisierung, Tasking, Synchronisation.
• MPI (Message Passing Interface): Standard für paralleles Programmieren auf verteilten Systemen; basiert auf Nachrichtenaustausch.
• Funktionen von MPI: Punkt-zu-Punkt-Kommunikation, kollektive Kommunikation, Synchronisation, Gruppierung von Prozessen.
• Verwendete Formel: \texttt{ #pragma omp parallel for } in OpenMP für parallele Schleifen.