Practical parallel algorithms with MPI - Cheatsheet

Dekompositionsstrategien in parallelen Algorithmen

Definition:

Methoden zur Aufteilung eines Problems in Teilprobleme zur parallelen Verarbeitung.

Details:

• Domänenzerlegung: Aufteilung des Datenbereichs in kleinere Teilbereiche.
• Funktionszerlegung: Aufteilung des Problems basierend auf unterschiedlichen Funktionen oder Operationen.
• Datenzentrierte Dekomposition: Jede Aufgabe arbeitet auf einem anderen Teil des Datensatzes.
• Taskzentrierte Dekomposition: Unterschiedliche Aufgaben werden parallel ausgeführt.
• Zentrale Fragen: Granularität (Feinkörnigkeit der Teilprobleme), Lastverteilung, Kommunikationsaufwand.
• Ziel: Minimierung von Overhead und Kommunikation, Maximierung der Parallelität.

MPI-Umgebung initialisieren und beenden

Definition:

Initialisierung und Beendigung der MPI-Umgebung, notwendig für die Ausführung paralleler Programme.

Details:

• MPI Initialisierung: \texttt{MPI\textunderscore Init(\textbackslash &argc, \textbackslash &argv);}
• Überprüfen der MPI Umgebung: \texttt{MPI\textunderscore Initialized(\textbackslash &flag);}, \textbackslash flag ist ein \texttt{int}
• MPI Beendigung: \texttt{MPI\textunderscore Finalize();}
• Überprüfen, ob MPI beendet ist: \texttt{MPI\textunderscore Finalized(\textbackslash &flag);}, \textbackslash flag ist ein \texttt{int}

Punkt-zu-Punkt-Kommunikation in MPI

Definition:

Direkte Kommunikation zwischen zwei Prozessen in MPI

Details:

• Funktionen: MPI_Send, MPI_Recv
• Blockierend vs. nicht-blockierend: MPI_Send, MPI_Isend
• Protokoll: Standard, synchron, gepuffert, ready Mode
• Kommunikationspartner spezifizieren mit rank und tag
• MPI_Status für Empfangsinformationen
• Vermeidung von Deadlocks durch Reihenfolge beachten

Kollektive Kommunikation und ihre Protokolle

Definition:

Kollektive Kommunikation in MPI: Mechanismus für Datenkommunikation zwischen Gruppen von Prozessen. Für Synchronisation und Datenaustausch in parallelen Algorithmen.

Details:

• Wichtige Operationen: Broadcast, Scatter, Gather, Allgather, Alltoall, Reduce, Allreduce
• Broadcast (\texttt{MPI\textunderscore Bcast}): Verteilung von Daten von einem Prozess an alle anderen
• Scatter (\texttt{MPI\textunderscore Scatter}): Verteilung von Daten von einem Prozess an eine Gruppe
• Gather (\texttt{MPI\textunderscore Gather}): Sammlung von Daten von einer Gruppe zu einem Prozess
• Allgather (\texttt{MPI\textunderscore Allgather}): Sammlung von Daten von allen Prozessen und anschließende Verteilung an alle
• Alltoall (\texttt{MPI\textunderscore Alltoall}): Vollständiger Datenaustausch zwischen allen Prozessen
• Reduce (\texttt{MPI\textunderscore Reduce}): Aggregation von Daten mittels einer Operation (z.B. Summe)
• Allreduce (\texttt{MPI\textunderscore Allreduce}): Kombination von \texttt{MPI\textunderscore Reduce} und \texttt{MPI\textunderscore Bcast}

Fehlertoleranzstrategien in verteilten Systemen

Definition:

Strategien zur Sicherstellung der Funktionalität und Verfügbarkeit eines verteilten Systems trotz Fehlern bei Hardware, Software oder Netzwerk.

Details:

• Wichtige Strategien: Checkpointing, Replikation, Heartbeats, Erkennen und Wiederherstellen von Fehlern.
• Checkpointing: Zwischenspeichern des Zustands eines Prozesses; bei Fehlern Neustart von letztem gesicherten Zustand.
• Replikation: Mehrfache Ausführung von kritischen Komponenten zur Erhöhung der Verfügbarkeit und Fehlertoleranz.
• Heartbeats: Regelmäßige Signale zur Überwachung der Betriebsbereitschaft von Knoten.
• Fehlererkennung und -wiederherstellung: Mechanismen zur Erkennung von Fehlern und automatischer oder manueller Wiederherstellung.
• Beispiel in MPI: Verwendung von MPI-Bibliotheken, die Checkpointing und Wiederherstellung unterstützen wie z.B. ULFM (User-Level Failure Mitigation).

Cache-Optimierungen und effizientes Ressourcenmanagement

Definition:

Optimierung der Datenspeicherung und -verarbeitung, um die Effizienz zu maximieren und Ressourcenverschwendung zu minimieren.

Details:

• Cache-Lokalisierung: Nutzung von lokalem Speicher zur Verringerung der Zugriffszeiten.
• Ressourcenverteilung: Ausgleich der Arbeitslast über mehrere Prozessoren zur Maximierung der Gesamteffizienz.
• Algorithmische Techniken: Verwendung cachefreundlicher Algorithmen zur Reduzierung von Cache-Misses.
• Datenpräfektierung: Vorausladen von Daten in den Cache, um Zugriffszeiten zu minimieren.
• Speicherausgleich: Vermeidung von Speicherengpässen durch effiziente Speicherverwaltung und -nutzung.
• Verwendung von MPI-Datenverteilungsfunktionen zur Optimierung der Speicher-Nutzung und -Verteilung.

Debugging-Tools für parallele Programme und Deadlock-Vermeidung

Definition:

Werkzeuge zur Fehlersuche in parallelen Programmen und Strategien zur Vermeidung von Deadlocks; kritisch für Effizienz und Stabilität.

Details:

• Laut MPI-Standard bieten Bibliotheken wie TotalView, DDT, und MARMOT erweiterte Debugging-Funktionen.
• TotalView: Debugger für verteilte und parallele Programme, unterstützt C, C++, und Fortran.
• DDT (Distributed Debugging Tool): Interaktives Debugging-Tool für parallele Anwendungen.
• MARMOT: MPI-Debugging-Tool zur Überwachung von MPI-Aufrufen und Erkennung von Deadlocks.
• Strategien zur Deadlock-Vermeidung: Ressourcenhierarchien, Timeouts und Prioritäten nutzen.
• Ressourcen-Hierarchie: Einhaltung einer festen Reihenfolge beim Ressourcen-Zugriff vermeidet zirkuläre Abhängigkeiten.
• Timeouts: Prozesse terminieren, wenn bestimmte Zeit überschritten wird.
• Prioritäten: Zuweisung von Prioritäten an Prozesse/Threads, um Ressourcenanfragen effizient zu organisieren.