Parallelitaet.tex 10.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. %!TEX root = Programmierparadigmen.tex
  2. \chapter{Parallelität}
  3. \index{Parallelität|(}
  4. Systeme mit mehreren Prozessoren sind heutzutage weit verbreitet. Inzwischen
  5. sind sowohl in Desktop-PCs als auch Laptops, Tablets und Smartphones
  6. \enquote{Multicore-CPUs} verbaut. Daher sollten auch Programmierer in der Lage
  7. sein, Programme für mehrere Kerne zu entwickeln.
  8. Parallelverarbeitung kann auf mehreren Ebenen statt finden:
  9. \begin{itemize}
  10. \item \textbf{Bit-Ebene}: Werden auf 32-Bit Computern \texttt{long long}, also
  11. 64-Bit Zahlen, addiert, so werden parallel zwei 32-Bit Additionen durchgeführt und
  12. das carry-flag benutzt.
  13. \item \textbf{Anweisungs-Ebene}: Die Ausführung von Anweisungen in der CPU
  14. besteht aus mehreren Phasen (Instruction Fetch, Decode, Execution, Write-Back).
  15. Besteht zwischen aufeinanderfolgenden Anweisungen keine Abhängigkeit,
  16. so kann der Instruction Fetch-Teil einer zweiten Anweisung parallel zum
  17. Decode-Teil einer ersten Anweisung geschehen. Das nennt man Pipelining\xindex{Pipelining}.
  18. Man spricht hier auch von \textit{Instruction Level Parallelism} (ILP)\xindex{ILP}
  19. \item \textbf{Datenebene}: Es kommt immer wieder vor, dass man in Schleifen
  20. eine Operation für jedes Objekt eines Contaitainers (z.~B. einer Liste)
  21. durchführen muss. Zwischen den Anweisungen verschiedener Schleifendurchläufe
  22. besteht dann eventuell keine Abhängigkeit. Dann können alle Schleifenaufrufe
  23. parallel durchgeführt werden.
  24. \item \textbf{Verarbeitungsebene}: Verschiedene Programme sind unabhängig
  25. von einander.
  26. \end{itemize}
  27. 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
  28. Anwendungen, sodass es sich so anfühlt, als würden die Programme echt parallel
  29. ausgeführt werden.
  30. Weitere Informationen zu Pipelining gibt es in der Vorlesung \enquote{Rechnerorganisation}
  31. bzw. \enquote{Digitaltechnik und Entwurfsverfahren} (zu der auch ein exzellentes Skript angeboten wird). Informationen über Schedulung werden in der Vorlesung \enquote{Betriebssysteme}
  32. vermittelt.
  33. \section{Architekturen}
  34. Es gibt zwei Ansätze, wie man Parallelrechner entwickeln kann:
  35. \begin{itemize}
  36. \item \textbf{Gemeinsamer Speicher}: In diesem Fall kann jeder Prozessor
  37. jede Speicherzelle ansprechen. Dies ist bei Multicore-CPUs der Fall.
  38. \item \textbf{Verteilter Speicher}: Es ist auch möglich, dass jeder Prozessor
  39. seinen eigenen Speicher hat, der nur ihm zugänglich ist. In diesem Fall
  40. schicken die Prozessoren Nachrichten (engl. \textit{message passing}\xindex{message passing}). Diese Technik wird in Clustern eingesetzt.
  41. \end{itemize}
  42. Eine weitere Art, wie man Parallelverarbeitung klassifizieren kann, ist anhand
  43. der verwendeten Architektur. Der der üblichen, sequentiellen Art der Programmierung,
  44. bei der jeder Befehl nach einander ausgeführt wird, liegt die sog.
  45. \textbf{Von-Neumann-Architektur}\xindex{Von-Neumann-Architektur} zugrunde.
  46. 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.
  47. In diesem Modell geht man von einer beliebigen Anahl an Prozessoren aus, die
  48. über lokalen Speicher verfügen und synchronen Zugriff auf einen gemeinsamen
  49. Speicher haben.
  50. Anhand der \textbf{Flynn'schen Klassifikation}\xindex{Flynn'sche Klassifikation}
  51. können Rechnerarchitekturen in vier Kategorien unterteilt werden:
  52. \begin{table}[h]\xindex{SISD}\xindex{MISD}\xindex{SIMI}\xindex{MIMD}
  53. \centering
  54. \begin{tabular}{l|ll}
  55. ~ & Single Instruction & Multiple Instruction \\ \hline
  56. Single Data & SISD & MISD \\
  57. Multiple Data & SIMD & MIMD \\
  58. \end{tabular}
  59. \end{table}
  60. Dabei wird die Von-Neumann-Architektur als \textit{SISD-Architektur} und die
  61. PRAM-Architektur als \textit{SIMD-Architektur} klassifiziert. Es ist so zu
  62. verstehen, dass ein einzelner Befehl auf verschiedene Daten angewendet wird.
  63. Bei heutigen Multicore-Rechnern liegt MIMD vor, da verschiedene Befehle in den
  64. Programmspeichern möglich sind.
  65. Ein Beispiel für die SIMD sind GPUs. Sie haben einen Befehl im Programmspeicher
  66. der auf verschiedenen Daten (Pixel) angewendet wird.
  67. MISD ist nicht so richtig sinnvoll.
  68. \begin{definition}[Nick's Class]\index{NC|see{Nick's Class}}\xindex{Nick's Class}%
  69. Nick's Class (in Zeichen: $\mathcal{NC}$) ist die Klasse aller Probleme,
  70. die im PRAM-Modell in logarithmischer Laufzeit lösbar sind, wobei die
  71. Anzahl der Prozessoren polynomiell in der Eingabegröße beschränkt ist.
  72. \end{definition}
  73. \begin{beispiel}[Nick's Class]%
  74. Folgende Probleme sind in $\mathcal{NC}$:
  75. \begin{bspenum}
  76. \item Die Addition, Multiplikation und Division von Ganzzahlen,
  77. \item Matrixmultiplikation, die Berechnung von Determinanten und Inversen,
  78. \item ausschließlich Probleme aus $\mathcal{P}$, also: $\mathcal{NC} \subseteq \mathcal{P}$
  79. \end{bspenum}
  80. Es ist nicht klar, ob $\mathcal{P} \subseteq \mathcal{NC}$ gilt. Bisher
  81. wurde also noch kein Problem $P \in \mathcal{P}$ gefunden mit $P \notin \mathcal{NC}$.
  82. \end{beispiel}
  83. \section{Prozesskommunikation}
  84. Die Prozesskommunikation wird durch einige Probleme erschwert:
  85. \begin{definition}[Wettlaufsituation]\xindex{Wettlaufsituation}\index{Race-Condition|see{Wettlaufsituation}}%
  86. Ist das Ergebnis einer Operation vom zeitlichen Ablauf der Einzeloperationen
  87. abhängig, so liegt eine Wettlaufsituation vor.
  88. \end{definition}
  89. \begin{beispiel}[Wettlaufsituation]
  90. Angenommen, man hat ein Bankkonto mit einem Stand von $\num{2000}$ Euro.
  91. Auf dieses Konto wird am Monatsende ein Gehalt von $\num{800}$ Euro eingezahlt
  92. und die Miete von $\num{600}$ Euro abgehoben. Nun stelle man sich folgende
  93. beiden Szenarien vor:
  94. \begin{table}[h]
  95. \centering
  96. \begin{tabular}{c|l|l|l}
  97. $t$ & Prozess 1: Lohn & Prozess 2: Miete & Kontostand \\ \hline
  98. 1 &Lade Kontostand & Lade Kontostand & 2000 \\
  99. 2 & Addiere Lohn & ~ & 2000 \\
  100. 3 & Speichere Kontostand & ~ & 2800 \\
  101. 4 & ~ & Subtrahiere Miete & 2800 \\
  102. 5 & ~ & Speichere Kontostand & 1400 \\
  103. \end{tabular}
  104. \end{table}
  105. Dieses Problem existiert nicht nur bei echt parallelen Anwendungen, sondern
  106. auch bei zeitlich verzahnten Anwendungen.
  107. \end{beispiel}
  108. \begin{definition}[Semaphore]\xindex{Semaphore}%
  109. Eine Semaphore $S=(c, r, f, L)$ ist eine Datenstruktur, die aus einer Ganzzahl, den beiden
  110. atomaren Operationen $r$ = \enquote{reservieren probieren} und $f$ = \enquote{freigeben}
  111. sowie einer Liste $L$ besteht.
  112. $r$ gibt entweder Wahr oder Falsch zurück um zu zeigen, ob das reservieren
  113. erfolgreich war. Im Erfolgsfall wird $c$ um $1$ verringert. Es wird genau
  114. dann Wahr zurück gegeben, wenn $c$ positiv ist. Wenn Wahr zurückgegeben wird,
  115. dann wird das aufrufende Objekt der Liste hinzugefügt.
  116. $f$ kann nur von Objekten aufgerufen werden, die in $L$ sind. Wird $f$ von
  117. $o \in L$ aufgerufen, wird $o$ aus $L$ entfernt und $c$ um eins erhöht.
  118. \end{definition}
  119. Semaphoren können eingesetzt werden um Wettlaufsituationen zu verhindern.
  120. \begin{definition}[Monitor]\xindex{Monitor}%
  121. Ein Monitor $M = (m, c)$ ist ein Tupel, wobei $m$ ein Mutex und $c$ eine
  122. Bedingung ist.
  123. \end{definition}
  124. Monitore können mit einer Semaphore, bei der $c=1$ ist, implementiert werden.
  125. Monitore sorgen dafür, dass auf die Methoden der Objekte, die sie repräsentieren,
  126. zu jedem Zeitpunkt nur ein mal ausgeführt werden können. Sie sorgen also für
  127. \textit{gegenseitigen Ausschluss}.
  128. \begin{beispiel}[Monitor]
  129. Folgendes Beispiel von \url{https://en.wikipedia.org/w/index.php?title=Monitor_(synchronization)&oldid=596007585} verdeutlicht den Nutzen eines Monitors:
  130. \begin{verbatim}
  131. monitor class Account {
  132. private int balance := 0
  133. invariant balance >= 0
  134. public method boolean withdraw(int amount)
  135. precondition amount >= 0
  136. {
  137. if balance < amount:
  138. return false
  139. else:
  140. balance := balance - amount
  141. return true
  142. }
  143. public method deposit(int amount)
  144. precondition amount >= 0
  145. {
  146. balance := balance + amount
  147. }
  148. }
  149. \end{verbatim}
  150. \end{beispiel}
  151. \section{Parallelität in Java}
  152. Java unterstützt mit der Klasse \texttt{Thread} und dem Interface \texttt{Runnable}
  153. Parallelität.
  154. Interessante Stichwörder sind noch:
  155. \begin{itemize}
  156. \item ThreadPool
  157. \item Interface Executor
  158. \item Interface Future<V>
  159. \item Interface Callable<V>
  160. \end{itemize}
  161. \section{Message Passing Modell}
  162. Das Message Passing Modell ist eine Art, wie man parallel laufende Programme
  163. schreiben kann. Dabei tauschen die Prozesse Nachrichten aus um die Arbeit zu
  164. verteilen.
  165. Ein wichtiges Konzept ist hierbei der \textit{Kommunikator}\xindex{Kommunikator}.
  166. Ein Kommunikator definiert eine Gruppe von Prozessen, die mit einander kommunizieren
  167. können. In dieser Gruppe von Prozessen hat jeder Prozesse einen eindeutigen
  168. \textit{Rang}\xindex{Rang}, den sie zur Kommunikation nutzen.
  169. Die Grundlage der Kommunikation bilden \textit{send} und \textit{receive} Operationen.
  170. Prozesse schicken Nachrichten an andere Prozesse, indem sie den eindeutigen Rang
  171. und einen \textit{tag} angeben, der die Nachricht identifiziert.
  172. Wenn ein Prozess mit einem einzigen weiteren Prozess kommuniziert, wird dies
  173. \textit{Punkt-zu-Punkt-Kommunikation}\xindex{Punkt-zu-Punkt-Kommunikation} genannt.
  174. Wenn ein Prozess allen anderen eine Nachricht schickt, nennt man das \textit{Broadcast}\xindex{Broadcast}.
  175. \index{Parallelität|)}