123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212 |
- %!TEX root = Programmierparadigmen.tex
- \chapter{Parallelität}
- \index{Parallelität|(}
- Systeme mit mehreren Prozessoren sind heutzutage weit verbreitet. Inzwischen
- sind sowohl in Desktop-PCs als auch Laptops, Tablets und Smartphones
- \enquote{Multicore-CPUs} verbaut. Daher sollten auch Programmierer in der Lage
- sein, Programme für mehrere Kerne zu entwickeln.
- Parallelverarbeitung kann auf mehreren Ebenen statt finden:
- \begin{itemize}
- \item \textbf{Bit-Ebene}: Werden auf 32-Bit Computern \texttt{long long}, also
- 64-Bit Zahlen, addiert, so werden parallel zwei 32-Bit Additionen durchgeführt und
- das carry-flag benutzt.
- \item \textbf{Anweisungs-Ebene}: Die Ausführung von Anweisungen in der CPU
- besteht aus mehreren Phasen (Instruction Fetch, Decode, Execution, Write-Back).
- Besteht zwischen aufeinanderfolgenden Anweisungen keine Abhängigkeit,
- so kann der Instruction Fetch-Teil einer zweiten Anweisung parallel zum
- Decode-Teil einer ersten Anweisung geschehen. Das nennt man Pipelining\xindex{Pipelining}.
- Man spricht hier auch von \textit{Instruction Level Parallelism} (ILP)\xindex{ILP}
- \item \textbf{Datenebene}: Es kommt immer wieder vor, dass man in Schleifen
- eine Operation für jedes Objekt eines Contaitainers (z.~B. einer Liste)
- durchführen muss. Zwischen den Anweisungen verschiedener Schleifendurchläufe
- besteht dann eventuell keine Abhängigkeit. Dann können alle Schleifenaufrufe
- parallel durchgeführt werden.
- \item \textbf{Verarbeitungsebene}: Verschiedene Programme sind unabhängig
- von einander.
- \end{itemize}
- Gerade bei dem letzten Punkt ist zu beachten, dass echt parallele Ausführung nicht mit \textit{verzahnter Ausführung}\xindex{verzahnt} zu verwechseln ist. Auch bei Systemen mit nur einer CPU und einem Kern kann man gleichzeitig den Browser nutzen und einen Film über eine Multimedia-Anwendung laufen lassen. Dabei wechselt der Scheduler sehr schnell zwischen den verschiedenen
- Anwendungen, sodass es sich so anfühlt, als würden die Programme echt parallel
- ausgeführt werden.
- Weitere Informationen zu Pipelining gibt es in der Vorlesung \enquote{Rechnerorganisation}
- bzw. \enquote{Digitaltechnik und Entwurfsverfahren} (zu der auch ein exzellentes Skript angeboten wird). Informationen über Schedulung werden in der Vorlesung \enquote{Betriebssysteme}
- vermittelt.
- \section{Architekturen}
- Es gibt zwei Ansätze, wie man Parallelrechner entwickeln kann:
- \begin{itemize}
- \item \textbf{Gemeinsamer Speicher}: In diesem Fall kann jeder Prozessor
- jede Speicherzelle ansprechen. Dies ist bei Multicore-CPUs der Fall.
- \item \textbf{Verteilter Speicher}: Es ist auch möglich, dass jeder Prozessor
- seinen eigenen Speicher hat, der nur ihm zugänglich ist. In diesem Fall
- schicken die Prozessoren Nachrichten (engl. \textit{message passing}\xindex{message passing}). Diese Technik wird in Clustern eingesetzt.
- \end{itemize}
- Eine weitere Art, wie man Parallelverarbeitung klassifizieren kann, ist anhand
- der verwendeten Architektur. Der der üblichen, sequentiellen Art der Programmierung,
- bei der jeder Befehl nach einander ausgeführt wird, liegt die sog.
- \textbf{Von-Neumann-Architektur}\xindex{Von-Neumann-Architektur} zugrunde.
- Bei der Programmierung von parallel laufenden Anwendungen kann man das \textbf{PRAM-Modell}\xindex{PRAM-Modell} (kurz für \textit{Parallel Random Access Machine}) zugrunde legen.
- In diesem Modell geht man von einer beliebigen Anahl an Prozessoren aus, die
- über lokalen Speicher verfügen und synchronen Zugriff auf einen gemeinsamen
- Speicher haben.
- Anhand der \textbf{Flynn'schen Klassifikation}\xindex{Flynn'sche Klassifikation}
- können Rechnerarchitekturen in vier Kategorien unterteilt werden:
- \begin{table}[h]\xindex{SISD}\xindex{MISD}\xindex{SIMI}\xindex{MIMD}
- \centering
- \begin{tabular}{l|ll}
- ~ & Single Instruction & Multiple Instruction \\ \hline
- Single Data & SISD & MISD \\
- Multiple Data & SIMD & MIMD \\
- \end{tabular}
- \end{table}
- Dabei wird die Von-Neumann-Architektur als \textit{SISD-Architektur} und die
- PRAM-Architektur als \textit{SIMD-Architektur} klassifiziert. Es ist so zu
- verstehen, dass ein einzelner Befehl auf verschiedene Daten angewendet wird.
- Bei heutigen Multicore-Rechnern liegt MIMD vor, da verschiedene Befehle in den
- Programmspeichern möglich sind.
- Ein Beispiel für die SIMD sind GPUs. Sie haben einen Befehl im Programmspeicher
- der auf verschiedenen Daten (Pixel) angewendet wird.
- MISD ist nicht so richtig sinnvoll.
- \begin{definition}[Nick's Class]\index{NC|see{Nick's Class}}\xindex{Nick's Class}%
- Nick's Class (in Zeichen: $\mathcal{NC}$) ist die Klasse aller Probleme,
- die im PRAM-Modell in logarithmischer Laufzeit lösbar sind, wobei die
- Anzahl der Prozessoren polynomiell in der Eingabegröße beschränkt ist.
- \end{definition}
- \begin{beispiel}[Nick's Class]%
- Folgende Probleme sind in $\mathcal{NC}$:
- \begin{bspenum}
- \item Die Addition, Multiplikation und Division von Ganzzahlen,
- \item Matrixmultiplikation, die Berechnung von Determinanten und Inversen,
- \item ausschließlich Probleme aus $\mathcal{P}$, also: $\mathcal{NC} \subseteq \mathcal{P}$
- \end{bspenum}
- Es ist nicht klar, ob $\mathcal{P} \subseteq \mathcal{NC}$ gilt. Bisher
- wurde also noch kein Problem $P \in \mathcal{P}$ gefunden mit $P \notin \mathcal{NC}$.
- \end{beispiel}
- \section{Prozesskommunikation}
- Die Prozesskommunikation wird durch einige Probleme erschwert:
- \begin{definition}[Wettlaufsituation]\xindex{Wettlaufsituation}\index{Race-Condition|see{Wettlaufsituation}}%
- Ist das Ergebnis einer Operation vom zeitlichen Ablauf der Einzeloperationen
- abhängig, so liegt eine Wettlaufsituation vor.
- \end{definition}
- \begin{beispiel}[Wettlaufsituation]
- Angenommen, man hat ein Bankkonto mit einem Stand von $\num{2000}$ Euro.
- Auf dieses Konto wird am Monatsende ein Gehalt von $\num{800}$ Euro eingezahlt
- und die Miete von $\num{600}$ Euro abgehoben. Nun stelle man sich folgende
- beiden Szenarien vor:
- \begin{table}[h]
- \centering
- \begin{tabular}{c|l|l|l}
- $t$ & Prozess 1: Lohn & Prozess 2: Miete & Kontostand \\ \hline
- 1 &Lade Kontostand & Lade Kontostand & 2000 \\
- 2 & Addiere Lohn & ~ & 2000 \\
- 3 & Speichere Kontostand & ~ & 2800 \\
- 4 & ~ & Subtrahiere Miete & 2800 \\
- 5 & ~ & Speichere Kontostand & 1400 \\
- \end{tabular}
- \end{table}
- Dieses Problem existiert nicht nur bei echt parallelen Anwendungen, sondern
- auch bei zeitlich verzahnten Anwendungen.
- \end{beispiel}
- \begin{definition}[Semaphore]\xindex{Semaphore}%
- Eine Semaphore $S=(c, r, f, L)$ ist eine Datenstruktur, die aus einer Ganzzahl, den beiden
- atomaren Operationen $r$ = \enquote{reservieren probieren} und $f$ = \enquote{freigeben}
- sowie einer Liste $L$ besteht.
- $r$ gibt entweder Wahr oder Falsch zurück um zu zeigen, ob das reservieren
- erfolgreich war. Im Erfolgsfall wird $c$ um $1$ verringert. Es wird genau
- dann Wahr zurück gegeben, wenn $c$ positiv ist. Wenn Wahr zurückgegeben wird,
- dann wird das aufrufende Objekt der Liste hinzugefügt.
- $f$ kann nur von Objekten aufgerufen werden, die in $L$ sind. Wird $f$ von
- $o \in L$ aufgerufen, wird $o$ aus $L$ entfernt und $c$ um eins erhöht.
- \end{definition}
- Semaphoren können eingesetzt werden um Wettlaufsituationen zu verhindern.
- \begin{definition}[Monitor]\xindex{Monitor}%
- Ein Monitor $M = (m, c)$ ist ein Tupel, wobei $m$ ein Mutex und $c$ eine
- Bedingung ist.
- \end{definition}
- Monitore können mit einer Semaphore, bei der $c=1$ ist, implementiert werden.
- Monitore sorgen dafür, dass auf die Methoden der Objekte, die sie repräsentieren,
- zu jedem Zeitpunkt nur ein mal ausgeführt werden können. Sie sorgen also für
- \textit{gegenseitigen Ausschluss}.
- \begin{beispiel}[Monitor]
- Folgendes Beispiel von \url{https://en.wikipedia.org/w/index.php?title=Monitor_(synchronization)&oldid=596007585} verdeutlicht den Nutzen eines Monitors:
- \begin{verbatim}
- monitor class Account {
- private int balance := 0
- invariant balance >= 0
- public method boolean withdraw(int amount)
- precondition amount >= 0
- {
- if balance < amount:
- return false
- else:
- balance := balance - amount
- return true
- }
- public method deposit(int amount)
- precondition amount >= 0
- {
- balance := balance + amount
- }
- }
- \end{verbatim}
- \end{beispiel}
- \section{Parallelität in Java}
- Java unterstützt mit der Klasse \texttt{Thread} und dem Interface \texttt{Runnable}
- Parallelität.
- Interessante Stichwörder sind noch:
- \begin{itemize}
- \item ThreadPool
- \item Interface Executor
- \item Interface Future<V>
- \item Interface Callable<V>
- \end{itemize}
- \section{Message Passing Modell}
- Das Message Passing Modell ist eine Art, wie man parallel laufende Programme
- schreiben kann. Dabei tauschen die Prozesse Nachrichten aus um die Arbeit zu
- verteilen.
- Ein wichtiges Konzept ist hierbei der \textit{Kommunikator}\xindex{Kommunikator}.
- Ein Kommunikator definiert eine Gruppe von Prozessen, die mit einander kommunizieren
- können. In dieser Gruppe von Prozessen hat jeder Prozesse einen eindeutigen
- \textit{Rang}\xindex{Rang}, den sie zur Kommunikation nutzen.
- Die Grundlage der Kommunikation bilden \textit{send} und \textit{receive} Operationen.
- Prozesse schicken Nachrichten an andere Prozesse, indem sie den eindeutigen Rang
- und einen \textit{tag} angeben, der die Nachricht identifiziert.
- Wenn ein Prozess mit einem einzigen weiteren Prozess kommuniziert, wird dies
- \textit{Punkt-zu-Punkt-Kommunikation}\xindex{Punkt-zu-Punkt-Kommunikation} genannt.
- Wenn ein Prozess allen anderen eine Nachricht schickt, nennt man das \textit{Broadcast}\xindex{Broadcast}.
- \index{Parallelität|)}
|