parallelrechnerparallelprogrammierung.tex

\chapter{Parallelrechner und Parallelprogrammierung}

Zusammenfassung der Vorlesung "`Parallelrechner und Parallelprogrammierung"' aus dem Sommersemester 2017.\footnote{\url{https://www.scc.kit.edu/personen/11185.php}}



\section{Einführung}

\begin{itemize}
	\item \textbf{Klassifikation nach Flynn}
	\begin{description}
		\item[Single Instruction Single Data (SISD):] von-Neumann-Architektur (Einprozessorrechner)
		\item[Single Instruction Multiple Data (SIMD):] Vektorrechner
		\item[Multiple Instruction Single Data (MISD):] In der Praxis irrelevant. Ausnahme: Mehrere Geräte, die zur Berechnungsverifikation das selbe Datum mehrfach parallel berechnen
		\item[Multiple Instruction Multiple Data (MIMD):] Multiprozessorsystem
	\end{description}
	\item \textbf{Multiprozessorsysteme}
	\begin{description}
		\item[Speichergekoppelter:] Gemeinsamer Adresseraum; Kommunikation über gemeinsame Variablen; skalieren mit \(>1000\) Prozessoren
		\begin{description}
			\item[Uniform Memory Access Model (UMA):] Alle Prozessoren greifen gleichermaßen mit gleicher Zugriffszeit auf einen gemeinsamen Speicher zu (symmetrische Multiprozessoren)
			\item[Non-uniform Memory Access Modell (NUMA):] Speicherzugriffszeiten variieren, da Speicher physikalisch auf verschiedene Prozessoren verteilt ist (Distributed Shared Memory System (DSM))
		\end{description}
		\item[Nachrichtengekoppelt:] Lokale Adresseräume; Kommunikation über Nachrichten (No-remote Memory Access Model); theoretisch unbegrenzte Skalierung
		\begin{description}
			\item[Uniform Communication Architecture Model (UCA):] Einheitliche Nachrichtenübertragungszeit
			\item[Non-uniform Communication Architecture Model (NUCA):] Unterschiedliche Nachrichtenübertragungszeiten in Abhängigkeit der beteiligten Prozessoren
		\end{description}
	\end{description}
\end{itemize}



\section{Parallelrechner}
\begin{itemize}
	\item \textbf{Leistungsfähigkeit}
	\begin{itemize}
		\item Maßzahl: Floating Point Operations per Second (FLOPS)
		\item Nicht notwendigerweise proportional zur Taktgeschwindkeit: Eventuell mehrere Zyklen zur Berechnung notwendig; Vektorprozessoren verarbeiten viele Floating Point Operations gleichzeitig (Grafikkarten)
		\item Messstandard: \texttt{LINPACK}-Benchmark
	\end{itemize}
\end{itemize}

\subsection{Shared Memory Multiprozessoren}
\begin{itemize}
	\item Programmierung durch effiziente automatische Parallelisierungswerkzeuge einfach und attraktiv
	\item \textbf{Cache-Kohärenz}
	\begin{itemize}
		\item Problem: Replikate in Caches verschiedener Prozessoren müssen kohärent gehalten werden (Lesezugriffe müssen immer den Wert des zeitlich letzten Schreibzugriffs liefern)
		\item Lösung: Verzicht auf strikte Konsistenz. Replikate müssen nicht zu jedem Zeitpunkt identisch sein
	\end{itemize}
\end{itemize}


\subsection{Distributed Memory Multiprozessoren}
\begin{itemize}
	\item Aufbau: Rechenknoten mit (mehreren) CPU(s), lokalem Speicher und ggf. lokaler Festplatte. Kopplung über Verbindungsnetzwerk
	\item Kriterien: Geschwindkeit, Parallelitätsgrad, Kosten, Latenz
\end{itemize}

\subsubsection{IBM RS/6000 SP (1990-2000)}
\begin{itemize}
	\item Nachrichtengekoppelter Multiprozessor mit \(2-512\) superskalaren, \(64\)-bit \texttt{POWER}-Knoten (\texttt{POWER3-II} mit \(1,5 \) GFLOPS Spitzenleistung auf)
	\item Verbindungsstruktur: High-Performance-Omega-Netzwerk (\(4 \times 4\)) bidirektionale Kreuzschinen
	\item Skalierbares IO-System über FileServer-Knoten
	\item Betriebssystem: \texttt{IBM AIX}
	\item \textbf{Aufbau}
	\begin{itemize}
		\item Frames: Jeweils \(16\) Knoten mit reduntanter Stromversorgung/Steuerungslogik sowie Hochleistungsnetzwerk
		\item High-Performance Switch
	\end{itemize}
\end{itemize}

\subsubsection{IBM Power 4 in der IBM p690 eSeries 1600 Cluster}
\begin{itemize}
	\item \textbf{\texttt{POWER4}-Prozessor}
	\begin{itemize}
		\item Erster Dual-Core Prozessor mit gemeinsamen \texttt{L2}-Cache und \(10,4\) GFLOPS
		\item \textit{Fabric Controller} zum Zusammenschalten von mehreren Chips \(\rightarrow\) \textit{Multi-Chip-Module} (MCM)
		\begin{itemize}
			\item interne Kommunikation über unidirektionalen Ring mit \(40\) GBit/s
			\item Gemeinsames Memory-Subsystem für \(8-32\) GB
		\end{itemize}
		\item \textit{Central Electronics Complex} (CEC) zum Zusammenschalten von bis zu \(4\) MCMs und bis zu \(8\) Speicherkarten
	\end{itemize}
	\item \textbf{Logical Partitions (LPARs)}
	\begin{itemize}
		\item Partitionierung von Ressourcen in physikalische Maschinen
		\item Volle Flexibilität bei voller Isolation; jede Kopie führt \texttt{AIX/Linux} aus
	\end{itemize}
	\item Speicherkonfiguration pro Rack: Bis zu \(8\) Speicherslots
	\item Beispiel: Juelich-Multi-Processor (JUMP) mit \(41\) \texttt{p690+} Schränken
\end{itemize}


\subsection{Distributed Shared Memory Multiprozessoren}
\begin{itemize}
	\item \textbf{Überblick}
	\begin{itemize}
		\item Gemeinsamer Adressraum, einzelne Speichermodule sind auf die einzelnen Prozessoren verteilt
		\item Oft Cache-Kohärenz bei (lokalem) Speicherzugriffen
	\end{itemize}
	\item \textbf{Zugriff}
	\begin{itemize}
		\item Mikrobefehlsebene
		\begin{itemize}
			\item Transparent für das Maschinenprogramm
			\item Explizite Befehle für entfernten Speicherzugriff
		\end{itemize}
		\item Software DSM
		\begin{itemize}
			\item Jeder Prozessor kann immer auf gemeinsame Daten zugreifen. Synchronisation mittels Schloss,- Semaphor- oder Bedigungsvariablen
			\item DSM-System regelt Kommunikation selbständig über (zumeist) Message-Passing
			\item Vorteile: Entlastung des Programmierers; leichte Portierbarkeit von/zu eng gekoppelten Multiprozessoren
			\item Datenverwaltung
			\begin{description}
				\item[Seitenbasiert:] Nutzung der virtuellen Speicherverwaltung des Betriebssystems zur expliziten Platzierung der Daten (unterschiedliche Granularität der Seiten: \(16\) Byte bis \(8\) kByte)
				\item[Objektbasiert:] % TODO
			\end{description}
			\item Probleme bei seitenbasierter Datenverwaltung
			\begin{itemize}
				\item Geringe Effizienz beim Nachladen über das Verbindungsnetz
				\item Lineares, strukturloses Feld von Speicherwort
				\item False Sharing und Flattern (Trashing)
				\begin{itemize}
					\item False Sharing: Eine Speicherseite beinhaltet mehrere Datenwörter, die von verschiedenen Prozessoren benötigt werden (Kohärenz auf Seitenebene) \(\rightarrow\) nach jedem Schreibzugriff eines Datenwortes muss die komplette Seite neu zu den anderen Prozessoren übertragen werden
					\item Flattern (Trashing): Bei mehrfachen Schreibzugriffen wird die Seite immer wieder übertragen
					\item Gegenmaßnahmen
					\begin{itemize}
						\item Verkleinerung der Seitengröße. Allerdings steigt damit der Seitenverwaltungsaufwand
						\item Objektbasiertes Software SDM-System: Gemeinsame Variablenzugriffe werden vom Precompiler erkannt und durch Bibliotheksfunktionen für entfernte Zugriffe ersetzt \(\rightarrow\) es werden nur Datenobjekte verschoben, die benötigt werden \(\rightarrow\) \textit{False Sharing} wird ausgeschlossen
					\end{itemize}
				\end{itemize}
			\end{itemize}
			\item Datenlokation und Datenzugriff
			\begin{itemize}
				\item Jeder Knoten muss Daten finden können (Datenlokation) und darauf zugreifen (Datenzugriff)
				\item Statische Verwaltung der Daten
				\begin{itemize}
					\item Daten werden zentral auf einem oder mehreren Servern verwaltet (Verteilung wird nicht verändert)
					\item Datenlokalisierung funktionsbasiert
					\item Konsistenz durch Sequentialisierung auf dem zuständigen Server
				\end{itemize}
				\item Dynamische Verwaltung der Daten
				\begin{itemize}
					\item Datum wird vor Zugriff auf zugreifenden Knoten verschoben \(\rightarrow\) alle Zugriffe sind lokal (single-reader-single-writer-Konzept)
					\item \textit{False Sharing} bei seitenbasiertem System
					\item Konsistenz durch Verschieben der Seiten
				\end{itemize}
			\end{itemize}
			\item Replizierte Daten
			\begin{itemize}
				\item Bisher: Knoten können nur sequentiell auf Daten zugreifen
				\item Replikation ähnelt Caching
				\begin{description}
					\item[Lesereplikation:] Reine Lesekopie, kann nicht geändert und zurückgeschrieben werden
					\item[Leseanfrage:] Falls vorhanden, Verwerfen einer Schreibkopie; danach Anfordern einer neuen Lesekopie
					\item[Schreibanfrage:] Verwerfen aller Kopien; danach Anlegen der Schreibkopie so wie zurückschreiben
				\end{description}
				\item Volle Replikation: multiple readers/multiple writers
				\begin{itemize}
					\item Jeder Knoten kann lokal Änderungen vornehmen \(\rightarrow\) Konsistenz schwierig
					\item Ansatz potentiell am effizientesten, da alle Zugriffe lokal sind
				\end{itemize}
			\end{itemize}
		\end{itemize}
	\end{itemize}
\end{itemize}

\subsubsection{Beispielsystem: Cray T3E}
\begin{itemize}
	\item NCC-NUMA-Konzept: Puffern von Cache-Blöcken nur bei prozessorlokalen Speicherzugriffen (keine Kohärenz über alle Cache-Speicher)
	\item Erster Supercomputer, der \(>1\) TFLOPS bei einer wissenschaftlichen Anwendung erzielte (1998)
	\item Verwendung von \(8-2176\) Alpha-Mikroprozessoren mit 3D-Torus-Nutzwerk
	\item \textbf{Adressierung}
	\begin{itemize}
		\item Aufbau einer globalen Adresse: Verarbeitungselementnummer (PE-Nummer) und lokaler Offset
		\item Adressumsetzung in Hardware (virtuelle \(\rightarrow\) logische \(\rightarrow\) physische Adresse)
	\end{itemize}
	\item \textbf{Verbindungsnetzwerk}
	\begin{itemize}
		\item Dreidimensionaler Torus (dreidimensionales, ringförmig geschlossenes Gitter)\footnote{\url{https://en.wikipedia.org/wiki/Torus_interconnect}}
		\item Daten können gleichzeitig über separate Kommunikationspfade ohne Beteiligung der Verarbeitungselemente (unabhängige Hardware-Unterstützung für den Nachrichtenaustausch) in alle drei Richtungen transportiert werden \(\rightarrow\) kurze Verbindungswege, schnelle Übertragung
	\end{itemize}
	\item \textbf{Mechanismen zur Synchronisation}
	\begin{description}
		\item[Barrier-Synchronisation:] Barrier-Modus (\texttt{UND}-Verknüpfung) und Eureka-Modus (\texttt{ODER}-Verknüpfung)
		\item[Fetch-and-Increment:] Atomares Lesen eines Werts und Inkrementieren eines speziellen lokalen Registers
		\item[Atomic-Swap:] Atomares Tauschen von lokalem Registerinhalt mit dem Inhalt einer (entfernten) Speicherzelle
	\end{description}
	\item Betriebssystem: Microkernel pro Verarbeitungselement
\end{itemize}

\subsubsection{Beispielsystem: SGI Altix (LRZ)}
\begin{itemize}
	\item CC-NUMA auf Basis von Intel Itanium Dual-Cores mit insgesamt \(9728\) cores (Platz 10, 06/2007)
	\item Leistung: \(56,5\) TFLOS (Linpack) bei ca. \(1\) MW Energiebedarf
	\item Nachfolgesystem \texttt{SuperMUC}: \(3,2\) PFLOPS bei \(2\) MW Energiebedarf
\end{itemize}


\subsection{Cluster Systeme}
\begin{itemize}
	\item Hintergrund: Zu Beginn häufig Spezialprozessoren in Supercomputern (Consumermarktentwicklung noch zu langsam). Später vermehrt Nutzung von \texttt{x86}-Standardprozessoren
	\item \textbf{Charakterisierung}
	\begin{itemize}
		\item Jeder Knoten als eigenes System mit eigenem OS
		\item Nachrichtenaustausch früher: Interprozesskommunikation über Netzwerk
		\item Nachrichtenaustausch heute: Cluster sind durch Multicore-Prozessoren hybride Systeme
		\begin{itemize}
			\item Gemeinsamer Speicher in einem Knoten (OpenMP)
			\item Verteilter Speicher zwischen den Knoten (MPI)
			\item Somit zwei Parallelitätsebenen
		\end{itemize}
	\end{itemize}
\end{itemize}

\subsubsection{HPC Cluster am KIT}
\begin{itemize}
	\item \textbf{HC3: HP XC3000 (seit Februar 2010)}
	\begin{itemize}
		\item \(356\) Rechenknoten mit jeweils zwei \texttt{Intel Xeon E5540} Quad Core (\(27,04\) TFLOPS Spitzenleistung) und insgesamt \(\approx 10\) TB Hauptspeicher
		\item OS: \texttt{HP XC Linux}
		\item Infiniband Netzwerk
		\item Nutzung durch KIT Institute
	\end{itemize}
	\item \textbf{InstitutsCluster 2 (IC2)}
	\begin{itemize}
		\item \(6560\) Xeon-Cores mit \(135,7\) TFLOPS Spitzenleistung und \(\approx 28\) TB Hauptspeicher
		\item OS: \texttt{SLES 11} mit \texttt{KITE} Managementsoftware
		\item Infiniband Netzwerk
		\item Nutzung durch KIT Institute
	\end{itemize}
	\item \textbf{bwUniCluster}
	\begin{itemize}
		\item Gemeinsames System aller Landesuniversitäten Baden Württembergs
		\item Systemarchitektur: \texttt{64bit x86} MultiCore-Prozessoren (sandy bridge); Infiniband FDR (\(56\) GBit/s)
		\item Kennzahlen Cluster: \(8448\) Cores mit \(175\) TFLOPS Spitzenleistung bei \(\approx 200\) KW Energieverbrauch
		\item Kennzahlen Speichersystem: \(900\) TB Speicher bei \(\approx 20\) KW Energieverbauch
	\end{itemize}
	\item \textbf{ForHLR Stufe 1}
	\begin{itemize}
		\item Landeshöchstleistungsrechner: System der Ebene Tier-2; Rechenzeitvergabe nach wissenschaftlichem Begutachtungsprozess
		\item \(528\) Xeon Prozessoren mit insgesamt \(10752\) Cores, \(\approx 41\) TB Hauptspeicher und \(232\) TFLOPS Spitzenleistung bei einem Energieverbauch von \(226\) KW
		\item Infiniband 4X FDR
		\item Benchmarks
		\begin{description}
			\item[Top500:] 243 (06/2014)
			\item[Green500:] 69 (06/2014)
		\end{description}
	\end{itemize}
\end{itemize}


\subsection{Vektorrechner}
\begin{itemize}
	\item Rechner mit pipelineartig aufgebautem Rechenwerk zur Verarbeitung von Vektoren von Gleitkommazahlen
	\item Skalarverarbeitung: Verknüpfung von Vektoren mit einzelnen Operanden
	\item \textbf{Beispiel: Vektor-Addition in vierstufiger Pipeline}
	\begin{description}
		\item[Stufe 1:] Laden von Gleitkommazahlen aus dem Vektorregister
		\item[Stufe 2:] Exponenten vergleichen und Mantisse verschieben
		\item[Stufe 3:] Addieren der ausgerichteten Mantisse
		\item[Stufe 4:] Ergebnis normalisieren und zurückschreiben
	\end{description}
	\item \textit{Chaining}: Verketten von (spezialisierten) Pipelines. Ergebnisse der vorderen Pipeline werden direkt der nächsten Pipeline zur Verfügung gestellt
	\item \textbf{Möglichkeiten zur Parallelisierung}
	\begin{description}
		\item[Vektor-Pipeline-Parallelität:] Durch die Pipeline selbst gegeben
		\item[Mehrere Pipelines pro Vektoreinheit:] Parallelität durch \textit{Chaining} von Pipelines
		\item[Vervielfachen der Pipelines:] Verwendung mehrerer parallel arbeitender, gleichartiger Pipelines
		\item[Mehrere Vektoreinheiten:] Mehrere unabhängige Vektoreinheiten
	\end{description}
	\item Vektorrechner heutzutage: Keine Relevanz mehr, da Standardprozessoren \texttt{SIMD}-Operationen effizient ausführen können
\end{itemize}

\subsubsection{NEC SX Serie}
\begin{itemize}
	\item \textbf{Beispielsystem am SCC (NEC SX-9)}
	\begin{itemize}
		\item Ein \texttt{SX-9} Knoten enthält \(16\) Vektorprozessoren (mit jeweils \(8\) Vektorpipelines) mit \(1\) TB Hauptspeicher und \(1,6\) TFLOPS Spitzenleistung
		\item Sehr gut geeignet für Strömungsberechnungen
		\item Größtmögliches System: \(512\) Knoten mit \(970\) TFLOPS Spitzenleistung
	\end{itemize}
	\item \textbf{Weitere \texttt{SX-9} Systeme}
	\begin{itemize}
		\item HLRS Stuttgart: \(12\) Knoten mit \(19,2\) TFLOPS Spitzenleistung
		\item Der Deutsche Wetterdienst besitze zwei unabhängige Systeme mit jeweils \(14\) Knoten und \(23\) TFLOPS Spitzenleistung
	\end{itemize}
\end{itemize}


\subsection{Ressourcenmanagement}
\begin{itemize}
	\item Typischerweise Knappheit von Parallelrechnerressourcen \(\rightarrow\) Ressourcenmanagement/Job Scheduling notwendig
	\item \textbf{Job Scheduling}
	\begin{enumerate}
		\item[Time-Sharing:] Simultane Ausführung mehrerer Jobs auf der gleichen Ressource nach einem \textit{Round-Robin}-Verfahren. Anwendung bei PCs
		\item[Space-Sharing:] Jobs bekommen exklusiv Ressourcen zur Ausführung zugewiesen, müssen allerdings ggf. warten bis genügend Ressourcen frei sind (Batch-System). Laufzeiten müssen abgeschätzt werden, meist gibt es Obergrenzen. Anwendung bei Clustern/Supercomputern
	\end{enumerate}
\end{itemize}



\section{Programmiermodelle und Grundlagen}

\subsection{Parallelitätsebenen/Parallelitätstechniken}
\begin{itemize}
	\item \textbf{Ebenen der Parallelität}
	\begin{enumerate}
		\item Programmebene (Jobebene): Beispielsweise gleichzeitig, von einander unabhängige Programme auf einem Betriebssystem
		\item Prozessebene (Taskebene): Beispielsweise Linux-Prozesse eines Programms, die auf gemeinsamen Daten arbeiten
		\item Blockebene (Threadebene): Beispielsweise parallel ausgeführte Schleifeniteration
		\item Anweisungsebene: Beispielsweise einzelne Maschinenbefehle, die parallel ausgeführt werden (beispielsweise bei superskalaren Prozessoren oder VLIW) 
		\item Suboperationsebene: Beispielsweise Vektorbefehle in einer Vektropipeline; setzt vektorisierende Compiler und komplexe Datenstrukturen voraus
	\end{enumerate}
	\item \textbf{Körnigkeit/Granularität}
	\begin{itemize}
		\item Verhältnis von Rechenaufwand zu Kommunikations-/Synchronisationsaufwand
		\item Klassifizierung
		\begin{description}
			\item[Grobkörnig:] Programm-, Prozess- und Blockebene
			\item[Mittelkörnig:] Blockebene, jedoch selten verwendet
			\item[Feinkörnig:] Anweisungsebene
			\item[Noch feinkörniger:] Supoperationsebene
		\end{description}
	\end{itemize}
\end{itemize}


\subsection{Maschinenmodelle}
\begin{itemize}
	\item \textbf{Random-Access Machine (RAM)}
	\begin{itemize}
		\item Einprozessorrechner mit jeweils einmal: Recheneinheit, Programm, RW-Speicher, Eingabeband, Ausgabeband
		\item Befehle mit Zielregister und zwei Operandenregistern
	\end{itemize}
\end{itemize}

\subsubsection{Parallel Random-Access Machine (PRAM)}
\begin{itemize}
	\item Modell eines idealen speichergekoppelten Parallelrechners. Keine Beachtung von Synchronisations-/Zugriffskosten
	\item \texttt{n}-Prozessor-PRAMs bestehen aus \texttt{n} identischen Prozessoren, mit gemeinsamen Speicher/Takt
	\item Praktische Bedeutung: PRAMs idealisieren Parallelrechner (s.o.) ohne Beachtung der Lokalität des global adressierbaren Speichers (Zugriff aller Prozessoren auf jede Speicherzelle immer in Einheitszeit)
	\item \textbf{Zugriffskonflikte}
	\begin{itemize}
		\item Typen von Zugriffskonflikten
		\begin{description}
			\item[Exclusive Read (ER):] Pro Zyklus kann höchstens ein Prozessor die selbe Speicherzelle lesen
			\item[Exclusive Write (EW):] Pro Zyklus kann höchstens ein Prozessor die selbe Speicherzelle beschreiben
			\item[Concurrent Read (CR):] Pro Zyklus können mehrere Prozessoren die selbe Speicherzelle lesen
			\item[Concurrent Write (CW):] Pro Zyklus können mehrere Prozessoren die selbe Speicherzelle beschreiben \(\rightarrow\) Schreibkonflikte müssen gelöst werden
		\end{description}
		\item Kombinationen von Zugriffskonflikten
		\begin{description}
			\item[EREW-PRAM:] Keine gemeinsamen Zugriffe
			\item[CWER-PRAM:] Gemeinsames Lesen erlaubt, gemeinsames Schreiben verboten
			\item[ERCW-PRAM:] Exklusiver Lesezugriff, gemeinsamer Schreibzugriff
			\item[CRCW-PRAM:] Gemeinsame Lese-/Schreibzugriffe erlaubt
		\end{description}
		\item Lösen von Schreibkonflikten
		\begin{description}
			\item[Common (C-CRCW):] Gemeinsamer Schreibzugriff nur erlaubt, wenn alle Prozessoren den selben Wert schreiben wollen
			\item[Arbitrary (A-CRCW):] Ein Prozessor gewinnt, alle anderen werden ignoriert
			\item[Priority (P-CRCW):] Der Prozessor mit dem kleinsten Index gewinnt
		\end{description}
	\end{itemize}
	\item Zusammenfassung: Speichergekoppelt; taktsynchron; gut zu programmieren
\end{itemize}

\subsubsection{Bulk Synchronous Parallel (BSP)}
\begin{itemize}
	\item Nachrichtengekoppeltes Maschinenmodell
	\item Aufbau: Prozessoren (mit oder ohne lokalem Speicher); Kommunikationsnetz; Barrierensynchronisation
	\item Definiert über Anzahl der Prozessoren \(p\), Kommunikationskostenfaktor \(g\) und die minimale Zeit für die Ausführung eines Superschrittes \(L\)
	\item \textit{Super-Step} Betrieb
	\begin{itemize}
		\item Sequentielle Ausführung von Superschritten. Pro Superschritt arbeiten die Prozessoren unabhängig von einander
		\item Bestandteile pro Superstep
		\begin{itemize}
			\item Berechnungsschritte auf lokalen Variablen, die zu Beginn des Superschritts zur Verfügung stehen
			\item Senden/Empfangen von Nachrichten
			\item Am Ende: Barrierensynchronisation aller Prozessoren vor dem nächsten Superschritt
		\end{itemize}
	\end{itemize}
	\item Zusammenfassung: Nahrichtengekoppelt, Superschritt-Synchronisation
\end{itemize}

\subsubsection{LogP-Modell}
\begin{itemize}
	\item Prozessoren arbeiten unabhängig und tauschen Nachrichten aus
	\item \textbf{Definition einer Maschine}
	\begin{description}
		\item[L:] Maximale Latenz einer Übertragung einer kurzen Nachricht (weniger Wörter umfassend)
		\item[o:] Zeitbedarf zum Übertragen der Nachricht. Keine weitere Befehlsausführung während Senden oder Empfangen
		\item[g:] Untere Zeitschranke, die pro Prozessor zwischen zwei Übertragungen eingehalten werden muss
		\item[P:] Anzahl Prozessoren mit optionalem lokalen Speicher
	\end{description}
	\item Endliche Netzwerkbandbreite: Es können immer nur \(\frac{L}{g}\) Nachricht zeitgleich ausgetauscht werden
	\item \(L\) ist obere Schranke pro Nachrichtenübertragung aufzufassen
	\item Zusammenfassung: Nachrichtengekoppelt; explizite Kommunikation; geeignet für Laufzeitabschätzungen
\end{itemize}


\subsection{Quantitative Maßzahlen für Parallelrechner}
\begin{itemize}
	\item Prozessorzustände während Programmausführung: \textit{rechnend}, \textit{kommunizierend}, \textit{wartend} (auf Kommunikation)
	\item \textbf{Laufzeitmessung von \(T(1)\)}
	\begin{description}
		\item[Relative Beschleunigung (Algorithmenabhängig):] Paralleler Algorithmus wird auf Multiprozessorsystem so ausgeführt, als sei er sequentiell
		\item[Absolute Beschleunigung (Algorithmenunabhängig):] Verwenden des besten bekannten sequentiellen Algorithmus
	\end{description}
	\item \textbf{Skalierbarkeit}
	\begin{itemize}
		\item Definition: Das Hinzufügen von Verarbeitungselementen führt zur Verkürzung der Ausführungszeit, ohne dass das Programm geändert wird
		\item Annahme: Konstante Problemgröße
		\item Skalierung ist immer beschränkt: Sättigung ab einer bestimmten Prozessorzahl
		\item Skaliert ein System, so tritt das Problem bei einer wachsenden Problemgröße nicht auf
	\end{itemize}
	\item \textbf{Amdahls Gesetz}
	\begin{itemize}
		\item Aufteilung eines Programms in einen parallelen und einen sequentiellen Anteil. Speedup-Berechnung unter der Annahme, das kein Programm komplett parallelisiert werden kann
		\item Es gilt: \(0 \le S(p) \le p\)
		\item Superlinearer Speedup: \(S(p) > p\)
		\begin{itemize}
			\item Tritt nur selten auf, sorgt für Konfusion
			\item Gründe: Cache-Effekte durch die Speicherhierarchie; mit steigender Prozessorzahl steigt wächst die Cache-Hierarchie \(\rightarrow\) Reduzierung der Hauptspeicherzugriffe \(\rightarrow\) kürzere Laufzeit bei paralleler Ausführung
		\end{itemize}
	\end{itemize}
\end{itemize}


\subsection{Prozesse und Threads}
\begin{itemize}
	\item Parallelität ist eine spezielle Form von Nebenläufigkeit. Nebenläufige Anweisungen sind nur dann parallel, wenn zur Ausführung mehrere Prozessoren zur Verfügung stehen
	\item \textbf{Definitionen}
	\begin{description}
		\item[Prozessumgebung:] Geschützter Adressbereich eines Prozesses mit individuellem Code-/Datenbereich im Speicher \(\rightarrow\) Prozesswechsel bedingt somit (i.d.R.) einen Umgebungswechsel
		\item[Prozesskontext:] Registerwerte des Prozessors während der Prozessausführung. Beeinhaltet u.a. Befehlszähler, Stackpointer, etc. \(\rightarrow\) Prozesswechsel bedingt immer auch einen Kontextwechsel
	\end{description}
	\item Laufzeitbetrachtung: Erheblicher Aufwand durch Prozesserzeugung; Zugriffsschutzmechanismen (wenn Prozesse mehrerer Benutzer ausgeführt werden); Prozesswechsel; Kommunikations-/Synchronisationsoperationen
	\item \textbf{Prozesstypen}
	\begin{description}
		\item[Schwergewichtige Prozesse (Prozesse):] Klassische Prozesse
		\item[Leichtgewichtige Prozesse (Threads):] Mehrere \textit{Threads} teilen sich eine gemeinsame Prozessumgebung (Adressraum, Filepointer, geschützten Speicherbereich, etc.). Threadwechsel erzeugen keinen Umgebungswechsel, lediglich einen Kontextwechsel
	\end{description}
\end{itemize}


\subsection{Synchronisation und Kommunikation über gemeinsame Variablen}
\begin{itemize}
	\item \textbf{Synchronisation}
	\begin{itemize}
		\item Koordination zwischen Prozessen/Threads
		\item Einseitige Synchronisation: Abhängige Aktivitäten müssen in der richtigen Reichenfolge ausgeführt werden
		\item Mehrseitige Synchronisation: Zeitliche Reihenfolge der Ausführung unerheblich, Ausführung darf allerdings nicht parallel erfolgen (gemeinsamer Ressourcenzugriff) \(\rightarrow\) \textit{Mutual Exclusion} (gegenseitiger Ausschluss)
		\item \textit{Critical Section}: Anweisungen, deren Ausführung einen gegenseitigen Ausschluss erfordern
	\end{itemize}
	\item \textbf{Deadlocks (Verklemmungen)}
	\begin{itemize}
		\item Deadlock: Prozesse warten auf Ereignisse, die nicht mehr eintreten können \(\rightarrow\) Prozess wird undefinierbar verzögert (Aussperrung)
		\item Voraussetzungen für Deadlocks
		\begin{enumerate}
			\item Mutual Excklusion: Betriebsmittel sind nur exklusiv nutzbar
			\item No Preemption: Betriebsmittel können nicht entzogen werden
			\item Hold and Wait: Es werden Betriebsmittel gehalten während auf andere Betriebsmittel gewartet wird
			\item Circular Wait: Zirkuläre Abhängigkeit von Betriebsmittel von mindestens zwei Prozessen
		\end{enumerate}
		\item Vermeidung von Deadlocks
		\begin{itemize}
			\item Schlossvariable
			\begin{itemize}
				\item Abstrakte Datenstruktur, auf die alle Prozesse zugreifen müssen, die einen kritischen Abschnitt betreten wollen
				\item Operationen
				\begin{description}
					\item[lock:] Verschließt den kritischen Abschnitt von innen. Prozesse warten bis der kritische Abschnitt frei ist. Ist selbst ein kritischer Abschnitt \(\rightarrow\) Implementierung über atomare Befehle (\texttt{TEST\_AND\_SET}, \texttt{RESET}) oder der spezielle Maschineninstruktion \texttt{swap} (tauscht den Inhalt eines Registers und eines Speicherplatzes ohne untebrochen werden zu können). \textit{Spinlock} zum zyklischen Prüfen, ob ein Bereich wieder frei ist (ebenfalls per \texttt{swap})
					\item[unlock:] Gibt den Bereich wieder frei
				\end{description}
			\end{itemize}
			\item Semaphor
			\begin{itemize}
				\item Aufbau: Nicht-negative Integer-Variable; atomare Operationen "`passieren"' und "`verlassen"'
				\item Initialisierung über maximale Anzahl Prozesse, die eine Ressource zeitgleich nutzen dürfen. Bei Betreten wird der interne Zähler dekrementiert, beim Verlassen inkrementiert. Ist der Zähler Null, so muss auf Freigabe durch einen anderen Prozess gewartet werden
				\item Spezialfall: \texttt{new Semaphore(1)} wird als binäre Semaphore/Mutex Lock bezeichnet
				\item Nachteil: Kann bei fehlerhafter Implementierung (Vergessen von \textit{Verlassen}) das ganze System lahmlegen
				\item Unterschied zu \textit{Schlossvariable}: \textit{Verlassen} kann von allen Prozessen/Threads aufgerufen werden
			\end{itemize}
			\item Kritischer Abschnitt
			\begin{itemize}
				\item Zu jedem Zeitpunkt darf sich höchstens ein Prozess/Thread im kritischen Abschnitt befinden
				\item Bedingter kritischer Abschnitt: Kritischer Abschnitt kann nur betreten werden, wenn die Bedingung wahr ist (Implementierung von Fairness/Prioritäten/etc.)
				\item Wird der kritische Bereich freigegeben, bewerben sich alle wartenden Prozesse (bei denen die Bedingung wahr ist) um den kritischen Bereich
			\end{itemize}
			\item Monitor
			\begin{itemize}
				\item Zugriff exklsuiv einem Prozess vorbehalten. Abstrahiert die Zugriffsfunktionen/Realisierung des gegenseitigen Ausschlusses
				\item Im Monitor vereinbarte Variablen sind exklusiv und können nie gleichzeitig benutzt werden
				\item Innerhalb des Monitors haben Funktionen ledigleich Zugriff auf Monitorvariablen
				\item Auf monitorgebundene Variablen kann von außen nicht zugegriffen werden
				\item \textit{Verlassen} kann nur innerhalb des Monitors aufgerufen werden
				\item Vorteil gegenüber Semaphor: Kann nicht durch weitere hinzugekommene Anwenderprozesse gestört werden, wenn einmal korrekt programmiert
				\item Vorteil gegenüber bedingtem kritischen Abschnitt: Kann nicht nur Befehlsfolgen sondern auch Funktionen enthalten
			\end{itemize}
			\item Barriere
			\begin{itemize}
				\item Synchronisationspunkt für mehrere Prozesse
				\item Verwendung
				\begin{itemize}
					\item Initialisierung von Barrier-Variable mit Anzahl der Prozesse, auf die gewartet werden muss
					\item \texttt{wait-barrier} muss von jedem dieser Prozesse ausgeführt werden. Dabei wird der Zahler der Barriere dekrementiert bis sie Null ist
				\end{itemize}
				\item Verbindungsstruktur von Parallelrechner werden zur Implementierung sehr schneller Barriere-Sync-Operationen genutzt
			\end{itemize}
		\end{itemize}
	\end{itemize}
\end{itemize}


\subsection{Kommunikation über Nachrichten}
\begin{itemize}
	\item Verbrauchbarkeit: Nachrichten existieren nur für die Zeit des Übertragungsvorgangs
	\item Sequentialbeziehung (implizite Synchronisation): Nachrichten können erst nach dem Senden empfangen werden
	\item Bestandteile einer Nachticht: Ziel; Nummer; Speicherbereich, der verschickt werden soll; Anzahl und Datentyp der Datenelemente im Sendepuffer
	\item Sendeoptionen: Asynchron/Synchron; Gepuffert/Ungepuffert; Blockierend/Unblockierend
	\item Empfangsoptionen: Konsumierend (zerstörend)/konservierend; Asynchron/Synchron
	\item Adressierungsarten: Direkte Bennenung; Briefkasten; Port (global bekannt); Verbindung/Kanal (lokal in Prozessen vereinbart)
\end{itemize}


\subsection{Parallele Programmstrukturen}
\begin{itemize}
	\item \textbf{Fork-Join Modell}
	\begin{itemize}
		\item Prozesse werden zu Beginn eines parallelen Codeteils durch \texttt{fork}-Operationen erzeugt
		\item Diese arbeiten unabhängig weiter und erreichen am Ende eine \texttt{join}-Operation zur Synchronisation mit Erzeugerthread (\texttt{T1})
		\item Nachteil: Aufwand zur Threaderzeugung
	\end{itemize}
	\item \textbf{SPMD Modell}
	\begin{itemize}
		\item Ziel: Vermeidung des Aufwands zur Thread-Erzeugung \(\rightarrow\) Threads werden nur einmal beim Programmstart erzeugt und terminieren erst am Programmende
		\item Sequentielle Codeteile werden von allen Prozessen ausgeführt; parallele Codeteile individuell
	\end{itemize}
	\item \textbf{Reusable-Thread-Pool Modell}
	\begin{itemize}
		\item Idee: Kombinieren von Fork-Join Modell (Vermeiden der Mehrfachgenerierung der Prozesse) und SPMD Modell (Vermeidung der Mehrfachausführung der sequentiellen Codeteilen)
		\item Threads werden nur einmal erzeugt (wenn sie benötigt werden) und "`schlafen gelegt"', wenn sie gerade nicht gebraucht werden \(\rightarrow\) sequentieller Code wird nur einmal ausgeführt
	\end{itemize}
\end{itemize}



\section{Entwurf paralleler Programme}
\begin{itemize}
	\item Startproblem? Welche Programmabläufe lassen sich parallelisieren? Erstellung manuell, halbautomisch (werkzeuggestützt) oder automatisch (parallelisierender Compiler)
	\item Designziel: Datenverteilung sollte derart vorgenommen werden, dass die Mehrzahl der Datenzugriffe lokal sind
\end{itemize}

\subsection{Phasen der Entwicklung paralleler Programme nach Foster}
\begin{enumerate}
	\item \textbf{Partitionierungsphase}
	\begin{itemize}
		\item Finde bestmögliche Aufteilung der Berechnungsschritte/zugehörigen Daten
		\item Gebietszerlegung/Datenzerlegung
		\begin{itemize}
			\item Daten werden in Bereiche, die nur minimale Kommunikation erfordern aufgeteilt. Anweisungen/Funktionen/Programme werden gleichzeitig auf diese Bereiche angewendet
			\item Statische Struktur: Compiler oder Programmierer legt Unterteilung fest
			\item Dynamische Struktur: Lastverteilung zur Laufzeit. Benötigt u.U. weiteren Zeitbedarf für die Unterteilung
		\end{itemize}
		\item Funktionszerlegung
		\begin{itemize}
			\item Aufteilung entsprechend der Berechnungsschritte
			\item Idealerweise können Daten disjunkt den Berechnungsschritten zugeordnet werden
			\item Wird seltener verwendet
		\end{itemize}
	\end{itemize}
	\item \textbf{Kommunikationsphase}
	\begin{itemize}
		\item Berechnungen eines Tasks werden meist von anderen Tasks benötigt \(\rightarrow\) (un)gerichtete Kommunikation zwischen Tasks
		\item Kommunikationsanforderungen bei \textit{Gebietszerlegung} häufig schwer zu bestimmen; bei \textit{Funktionszerlegung} meist trivial
		\item Kommunikationsmuster
		\begin{description}
			\item[Lokale Kommunikation:] Tasks kommunizieren nur mit wenigen, direkten Nachbarn (Bsp.: Gebietszerlegung von matrixstrukturierten Daten)
			\item[Globale Kommunikation:] Tasks kommunizieren mit einer Vielzahl anderer Tasks (Bsp.: Zentralisierter Algorithmus mit Master-Worker)
			\item[Strukturierte Kommunikation:] Kommunikationsanforderungen erzeugen ein geordnetes Muster (Bsp.: Netz, Baum, Ring, etc.)
			\item[Unstrukturierte Kommunikation:] Erzeugt einen beliebigen Graphen (Verkompliziert meist die Bündelungsphase)
			\item[Statische Kommunikation:] Kommunikationspartner bleiben während der Laufzeit die selben
			\item[Dynamische Kommunikation:] Kommunikationspartner wechseln während der Laufzeit (und werden zur Laufzeit bestimmt)
			\item[Synchrones Kommunikationsmuster:] Tasks arbeiten koordiniert, Kommunikation entsteht gleichzeitig
			\item[Asynchrone Kommunikationsmuster:] Kommunikation entsteht unregelmäßig
		\end{description}
		\item Checkliste
		\begin{itemize}
			\item Gleiche Anzahl (weniger) Kommunikationsanforderungen pro Tasks?
			\item Können Kommunikationsoperationen parallel 
		\end{itemize}
	\end{itemize}
	\item \textbf{Bündelungsphase}
	\begin{itemize}
		\item Evaluierung der Aufgaben und Kommunikationsstrukturen bezüglich Leistungsanforderungen und Implementierungskosten in Abhängigkeit der Zielarchitektur
		\item Zielkonflikte
		\begin{enumerate}
			\item Reduzierung der Kommunikationskosten durch Erhöhung der Berechnungskosten
			\item Erhalten der Flexibilität bzgl. Skalierung
			\item Reduzierung der Software-Engineeringskosten
		\end{enumerate}
		\item Heuristiken zur Senkung der Kommunikationskosten
		\begin{description}
			\item[Oberfläche-versus-Volumen-Effekt:] Kommunikationsanforderungen eines Tasks sind proportional zur Oberfläche des Teilbereichs auf dem er arbeitet; Berechnungsanforderungen sind proportional zum Volumen des Teilbereichs
			\item[Replizierte Berechnungen:] Reduzierung des Kommunikationsaufwands durch Mehrfachberechnung
			\item[Verschmelzen nacheinander auszuführender Tasks:] Reduziert Kommunikationskosten
			\item[Erhalten der Flexibilität:] Skalierung des Algorithmus sollte nicht beeinträchtigt werden (eventuell Zielkonflik mit \textit{Verschmelzen nacheinander auszuführender Tasks})
		\end{description}
		\item Checkliste
		\begin{itemize}
			\item Hat die Bündelungsphase die Kommunikationskosten durch Erhöhung der Lokalität reduziert?
			\item Falls Daten replizeirt werden: Wird die Skalierbarkeit durch Problemgrößenbeschränkung/Prozessorzahl reduziert?
			\item Skaliert die Anzahl Tasks weiterhin mit der Problemgröße?
			\item Falls Bündelung paralleler Abläufe: Genügend Parallelität für die Zielarchitektur vorhanden?
			\item Softwareerstellungkosten berücksichtigt?
		\end{itemize}
	\end{itemize}
	\item \textbf{Abbildungsphase}
	\begin{itemize}
		\item Festlegung auf welchen Prozessoren die Tasks ausgeführt werden. Tasks, die häufig kommunizieren, werden auf demselben/benachbarten Prozessoren platziert
		\item Heuristiken für die Tasks-Prozessorabbildung
		\begin{itemize}
			\item Gebietszerlegung: Oft feste Anzahl ähnlich großer tasks sowie strukturierte Kommunikationsmuster \(\rightarrow\) so platzieren, dass Interprozessorkommunikations minimiert wird sowie Aggregation von Tasks, die auf dem selben Prozessor ausgeführt werden
			\item Verwendung eines dynamisch Loadbalancers bei ngliechmäßig großen Tasks oder unstrukturierten Kommunikationsmustern
			\item Verwendung von Tasks-Scheduling-Algorithmen bei Funktionszerlegung (oft viele kurzlebige Tasks) zur Vermeidung untätiger Prozessoren
		\end{itemize}
	\end{itemize}
\end{enumerate}


\subsection{Parallele Programmiertechniken nach Carriero und Gelernter}
\begin{itemize}
	\item \textbf{Vorgehen}
	\begin{enumerate}
		\item Wähle konzeptuelle Klasse
		\item Schreibe Programm unter Beachtung der Programmiermethode
		\item Falls notwendig, transformiere Programm in andere Programmiermethode
	\end{enumerate}
	\item \textbf{Konzeptuelle Klassen}
	\begin{itemize}
		\item Resultat-Parallelität
		\begin{itemize}
			\item Resultat wird in Komponenten zerlegt, diese werden simultan erstellt und dann zusammengebaut
			\item Parallelität entsteht durch parallele Berechnung der Elemente der Datenstruktur
		\end{itemize}
		\item Parallelität durch Spezialisierung
		\begin{itemize}
			\item Spezialisierte Einheiten arbeiten einander zu
			\item Entspricht Funktionszerlegung nach Foster
			\item Pipelining kann eingeschränkt als Parallelität durch Spezialisierung betrachtet werden
		\end{itemize}
		\item Agenda-Parallelität
		\begin{itemize}
			\item Erstellung einer Agenda von Tätigkeiten, die von mehreren Einheiten parallel abgearbeit wird
			\item Typischerweise Master-Worker-Paradigma
			\item Beispielsweise spekulative Ausführung
		\end{itemize}
	\end{itemize}
	\item \textbf{Parallele Programmiermethoden}
	\begin{itemize}
		\item live-Datenstruktur
		\begin{itemize}
			\item Gemeinsamer Adressraum notwendig: Jede Komponente der Datenstruktur erzeugt einen separaten Prozess auf den per Referenz zugegriffen wird. Es gibt keinen Nachrichtenaustausch
			\item Prozesse werden implizit erzeugt \(\rightarrow\) besonders für feinkörnige parallele Programme geeignet
		\end{itemize}
		\item Nachrichtenaustausch
		\begin{itemize}
			\item Geeignet für Nahrichtengekoppelte Multiprozessorsysteme
			\item Explizite Generierung von Prozessen mit individuellen Datenstrukturen
			\item Prozessstruktur/Kommunikationspfade durch Programmstruktur bestimmt
		\end{itemize}
		\item Verteilte Datenstrukturen
		\begin{itemize}
			\item Verteilte Datenstrukturen, die von verschiedenen Prozessen manipuliert werden können
			\item Kommunikation über gemeinsame Datenobjekte
		\end{itemize}
	\end{itemize}
\end{itemize}


\subsection{Programmierung speichergekoppelter Multiprozessoren}
\begin{itemize}
	\item \textbf{Replikationsintelligenz-Modelle}
	\begin{description}
		\item[Objecktspezifisch:] Programmierer für Replikationsmanagement verantwortlich
		\item[Middleware:] Middleware für Replikationsmanagement verantwortlich
	\end{description}
	\item \textbf{Konsistenzmodelle}
	\begin{itemize}
		\item Generell: Bei einem \textbf{Read} wird das Ergebnis des letzten \texttt{Write} erwartet
		\item Konsistenzmodelle
		\begin{description}
			\item[Strikte/Atomare Konsistenz:] Von globaler Zeit abhängig \(\rightarrow\) in Multiprozessorsystem nicht implementierbar
			\item[Sequentielle Konsistenz:] Jede gültige Kombination von RW-Operation zulässig (Permutationen möglich). Schwächer als atomares Modell, aber umsetzbar
			\item[Schwache Konsistenz:] Konsistenz nur zu festgelegten Synchronisatiospunkten gegeben \(\rightarrow\) Einführung kritischer Bereiche, in denen Inkonsistenz gemeinsamer Daten zugelassen ist (konkurrierende Zugriffe müssen verhindert werden)
		\end{description}
	\end{itemize}
	\item \textbf{Variablenanalyse}
	\begin{itemize}
		\item Ziel: Parallele Ausführung von Schleifeniterationen
		\item Vorgehen
		\begin{enumerate}
			\item Unterscheidung: Lokale oder gemeinsame Variable?
			\begin{description}
				\item[Lokale Variable:] Werden in jeder Iteration neu initialisiert
				\item[Globale Variable:] Werden von mehreren Iterationen verwendet
			\end{description}
			\item Falls gemeinsame Variable: Abhängig oder unabhängig?
			\begin{description}
				\item[Unabhängig:] Variable wird während allen Iterationen nur gelesen oder während jeder Iterationen wird auf ein anderes Array-Element zugegriffen
				\item[Unabhängig:] Sonst
			\end{description}
			\item Falls abhängige Variable
			\begin{description}
				\item[Reduktionsvariable:] Erweiterung einer Array-Variable um kommutative oder assotiative Verknüpfung der Variable (\texttt{q = q + b[i][k] * w[i-k]})
				\item[Locked Variable:] Änderungen bleiben ohne Auswirkungen (beispielsweise die Suche nach einem Minimum in einem Array)
				\item[Ordered Variable:] Ergebnis nur bei korrekter sequentieller Ausführung korrekt \(\rightarrow\) Erzwingen der sequentiellen Abarbeitung der Iterationen; parallele Abarbeitung der Iterationsschritte kann jedoch eingeschränkt möglich sein \(\rightarrow\) eventuell Optimierung vor der Parallelisierung notwendig
			\end{description}
		\end{enumerate}
	\end{itemize}
	\item \textbf{Parallelisierung von Iterationen}
	\begin{itemize}
		\item Parallelisierung möglichst über äußere Schleife
		\item Nur die abhängigen Variablen müssen berücksicht werden
	\end{itemize}
\end{itemize}



\section{Paralleles Programmieren mit OpenMP und MPI}

\subsection{Einführung in OpenMP}
\begin{itemize}
	\item Seit 1997 gemeinschaftlich von verschiedenen Hardware- und Compilerherstellern entwickelte Programmierschnittstelle (API) für die Shared-Memory-Programmierung in \texttt{C++}, \texttt{C} und \texttt{Fortran} auf Multiprozessor-Computern\footnote{\url{https://de.wikipedia.org/wiki/OpenMP}}
	\item Shared Memory System: Gesamtsystem verhält sich wie ein einzelnes System. Es existiert eine Kopie des OS 
	\item Daten werden im Shared Memory gespeichert; ein Prozess beim Start erzeugt dynamisch parallele Threads, die auf gemeinsame oder private Daten zugreifen
	\item \textbf{Grundidee}
	\begin{description}
		\item[Parallel Region:] Code wird von allen erzeugten Threads ausgeführt
		\item[Work Sharing Konstrukte:] Abgegrenzte Codesegmente/Schleifenindizes werden von verschiedenen Threads ausgeführt und müssen innerhalb von \textit{Parallel Regions} liegen
	\end{description}
	\item \textbf{Überblick}
	\begin{description}
		\item[Parallel Region:] \texttt{\#pragma omp parallel \{ ... \}}, \texttt{!\$OMP PARALLEL ... !\$OMP END PARALLEL}
		\item[Work Sharing Konstrukte:] \texttt{\#pragma omp for ...}, \texttt{!\$OMP DO ... !\$OMP END DO}
		\item[Synchronisierung:] \texttt{!\$OMP BARRIER} % TODO: Nur in Fortran?
		\item[Threadprivate:] Globale Daten, die innerhalb des Threads als private Daten behandelt werden. Die globalen Werte werden nicht geändert. \texttt{\#pragma omp threadprivate()}, \texttt{!\$OMP THREADPRIVATE()}
	\end{description}
	\item Typische Verwendung: Parallelisieren von Schleifen
	\item \textbf{Wichtige Direktiven}
	\begin{itemize}
		\item \texttt{OMP PARALLEL}: Parallelisiert Schleifen mittels \texttt{\#pragma omp parallel [clauses]}
		\item \texttt{Schedule}
		\begin{description}
			\item[Static:] Iterationen werden in \textit{Chunks} unterteilt und statisch den \textit{Threads} eines \textit{Teams} zugewiesen
			\item[Dynamic:] Interationen werden in \textit{Chunks} unterteilt und dynamisch auf freie \textit{Threads} aufgeteilt
			\item[Guided:] Jeder \textit{Thread} bekommt einen \textit{Chunk} zugewiesen. Nach erfolgreicher Verarbeitung erhält er einen weiteren, kleineren \textit{Chunk}
		\end{description}
		\item \texttt{TASK} (OpenMO 3.0)
		\begin{itemize}
			\item Kapselt ein "`Arbeitspaket"' (Code und Daten) und kann von beliebigen \textit{Threads} verarbeitet werden
			\item Ähnlich zu \texttt{OMP SECTIONS}, vermeidet allerdings viele verschachtelte \textit{Parallel Regions}
		\end{itemize}
		\item \texttt{OMP TASKLOOP} (OpenMP 4.5)
		\begin{itemize}
			\item Nutzt \textit{Tasks} zur Ausführung \(\rightarrow\) ermöglicht Verschränkung von \textit{Tasks} und normalen Schleifen
		\end{itemize}
	\end{itemize}
	\item \textbf{Gültigkeitsbereiche von Variablen}
	\begin{description}
		\item[Shared:] Die meisten variablen sind (gemäß Shared Memory Programmiermodell) standardmäßig gemeinsam
		\item[Globale Variablen:] Gemeinsam untern den \textit{Threads}
		\item[Privat:] Stackvariable in Unterprogrammen; automatische Variable innerhalb von Anweisungsblöcken; Schleifenindizes in \texttt{Fortran}
	\end{description}
	\item \textbf{Umgebungsvariablen}
	\begin{description}
		\item[OMP\_NUM\_THREADS:] Maximalzahl laufender \textit{Threads} (beispielsweise \texttt{export OMP\_NUM\_THREADS=16})
		\item[OMP\_SCHEDULE:] Spezifiziert Scheduling-Verfahren und \textit{Chunk}-Größe (beispielsweise \texttt{export OMP\_SCHEDULE=\dq STATIC,4\dq})
	\end{description}
\end{itemize}


\subsection{Einführung in MPI}
\begin{itemize}
	\item Distributed Memory System: Jeder Knoten agiert als eigenständiges Computersystem mit dediziertem Betriebssystem und lokalem Speicher. Parallelisierung über Message Passing Interface
	\item Daten-/Arbeitsverteilung: Entscheidungen basieren auf \texttt{rank}; alle Programme werden durch spezielles Initialisierungsprogramm gestartet
	\item \textbf{Kategorisierung nach Flynn}
	\begin{itemize}
		\item Pro Prozessor: Selbes Programm mit unterschiedlichen Daten \(\rightarrow\) SIMD
		\item Manche Implementierungen erlauben allerdings auch MIMD: \texttt{rank}-basierte, individuelle Anweisungen pro Prozessor
	\end{itemize}
	\item \textbf{Kommunikation}
	\begin{itemize}
		\item Messages: Datenpakete, die von einem Prozess zu einem anderen übermittelt werden. Informationen sind u.a. der Rang, Lokationen, Datentypen und Datengröße (jeweils für Quelle und Ziel)
		\item Synchrones Senden: Sender erhält Empfangsbestätigung
		\item Asynchrones (gepuffertes) Senden: Keine Epfangsbestätigung
		\item Blockierende Operationen
		\begin{description}
			\item[Synchrones Senden:] Senderoutine wird erst nach Bestätitung verlassen
			\item[Asynchrones Senden:] Senderoutine wird verlassen, sobald die Daten vollständig verschickt worden sind
			\item[Empfangen:] Empfangsroutine wird erst verlassen, wenn die Daten vollständig im Anwendungsspeicher stehen
		\end{description}
		\item Nicht-bockierende Operationen
		\begin{itemize}
			\item Stößt Kommunikation an und kehrt sofort zurück
			\item \texttt{WAIT}- oder \texttt{TEST}-Operationen pro nicht-blockierender Operation (idealerweise)
		\end{itemize}
	\end{itemize}
	\item \textbf{Befehlsreferenz}
	\begin{itemize}
		\item Initialisieren und Beenden: \texttt{MPI\_Init(argc, argv) ... MPI\_Finalize()}
		\item \texttt{MPI\_Comm\_size()} gibt die aktuelle Prozessanzahl zurück
		\item \texttt{MPI\_Comm\_rank()} gibt den Rang des aufrufenden Prozesses zurück
		\item Kommunikation
		\begin{itemize}
			\item Kommunikations findet immer innerhalb eines Kommunikators statt (standardmäßig \texttt{MPI\_COMM\_WORLD}). Prozesse identifizieren sich selbst durch ihren Rang
			\item Adressierungen (\texttt{dest}, \texttt{source}) mittels des entsprechenden Rangs
			\item Wildcards: \texttt{MPI\_ANY\_SOURCE} bzw. \texttt{MPI\_ANY\_TAG}
			\item Standardmäßig blockierende Kommunikation, allerdings auch nicht-blockierende Primitive vorhanden (beispielsweise \texttt{MPI\_ISend})
			\item Strukturierte Daten: Byte-weises Versenden von \texttt{Structs} \(\rightarrow\) MPI-Datentypen müssen erweitert werden
			\item P2P-Kommunikation
			\begin{itemize}
				\item Anforderungen: \texttt{tag} und \texttt{datatype} müssen übereinstimmen; Puffer müssen hinreichend groß sein
				\item Senden: \texttt{MPI\_Send(buf, count, datatypr, dest, tag, comm)}
				\item Empfangen: \texttt{MPI\_Recv(buf, count, datatype, source, tag, comm, status)}
			\end{itemize}
		\end{itemize}
	\end{itemize}
\end{itemize}



\section{Verteiltes Rechnen}
\begin{itemize}
	\item Definition nach Streit: Zusammenbringen von geografisch verteilten System zum gemeinsamen Problemlösen
	\item Beispiele: Grid/Cloud Computing; verteilte Speicherung/Verwaltung/Analyse von BigData
\end{itemize}


\subsubsection{Metacomputing}
\begin{itemize}
	\item Logische Interaktion eigenständiger, heterogener Parallelrechner über ein Hochgeschwindigkeits-WAN \(\rightarrow\) verteilen einer einzelnen Anwendung über verschiedene, auf einander abgestimmte Parallelrechner
	\item Beispiel gekoppelte Simulation: Jede Simulation wird auf der optimalen Plattform berechnet \(\rightarrow\) erhöht Nutzbarkeit/Auslastung von Systemen
	\item Programmierung über nachrichtegekoppelte Methoden, beispielsweise über spezielle \texttt{MPI}-Umgebung
	\item Beispiel aus Karlsruhe (1996): \texttt{IBM-RS/6000-SP}-Rechner (Universität) wird über \(155\) MBit/s-ATM-Leitung mit \(16\) Vektorrechner (Forschungszentrum) zusammengeschlossen \(\rightarrow\) verteilter "`Maschinenraum"'
\end{itemize}


\subsubsection{Grid Computing}
\begin{itemize}
	\item Konzept: Skalierbare und sichere HPC-Systeme über das Internet mit "`beispielloser"' Leistung
	\item Verwendung von quelloffener Standardsoftware/Protokolle/Interfaces
\end{itemize}



\newpage
\section{Appendix A: Formelsammung}

\subsection{Parallelrechner}

\subsubsection{Ende-zu-Ende Übertragungszeit}
Overhead: Zeit, um Nachrichten in/aus dem Netzwerk zu bekommen
\begin{equation}
	latency = t_{overhead} + t_{routing} + t_{transmission} + t_{contention}
\end{equation}


\subsection{Programmiermodelle und Grundlagen}

\subsubsection{Ausführungszeit}
\begin{equation}
	t = t_{computaton} + t_{communication} + t_{idle}
\end{equation}

\subsubsection{Übertragungszeit einer Nachricht}
\begin{equation}
	t_{msg} = t_{startup} + n \cdot \big( t_{transfer} \big)
\end{equation}

\subsubsection{Beschleunigung (Speedup)}
\begin{equation}
	S(p) = \frac{T(1)}{T(p)}
\end{equation}

\subsubsection{Effizienz}
\begin{equation}
	E(p) = \frac{S(p)}{p}
\end{equation}

\subsubsection{Amdahls Gesetz}
\begin{equation}
	T(p) = \underbrace{T(1) \cdot \frac{q}{p}}_{Paralleler~Anteil} + \underbrace{T(1) \cdot \big(1-q\big)}_{Sequentieller~Anteil}
\end{equation}
\begin{equation}
	S(p) = \frac{T(1)}{T(p)} = \frac{T(1)}{T(1) \cdot \frac{q}{p} + T(1) \cdot \big(1-q\big)} = \frac{1}{\frac{q}{p} + \big( 1 - q \big)} \le \frac{1}{1-q}
\end{equation}