% -*- coding: utf-8; -*-

\lecture[1]{Parallele Modelle}{parallele-modelle}

\subtitle{Wie rechnet man parallel?}

\date{11. April 2008}


\begin{body}

\begin{frame}
  \maketitle
\end{frame}


\begin{learning targets}
\item Grundidee des parallelen Algorithmus verstehen
\item DAGs als paralleles Modell kennen und anwenden können
\item \textsc{pram}s als paralleles Modell kennen und anwenden können
\item Das Netzwerkmodell und Netztopologien kennen
\end{learning targets}


\begin{lecture notes intro}
  Bevor man parallele Programme schreiben kann benötigt man zunächst
  eine Programmiersprache, die Parallelität unterstützt. Ganz ähnlich
  benötigt man zum Entwurf paralleler Algorithmen zunächst ein
  \emph{paralleles Maschinenmodell}. Ohne ein solches Modell machen
  Aussagen der Art »dieser Algorithmus löst das Problem in Zeit
  $O(\log n)$« keinen Sinn (was genau bedeutet denn »in Zeit
  XY«?). Noch trostloser wird es ohne ein genaues Maschinenmodell,
  wenn man Aussagen der  Form »dieses Problem lässt sich parallele
  nicht schneller als in Zeit $O(\log \log n)$ lösen« zeigen möchte. 

  Wie sollte nun ein geeignetes Maschinenmodell aussehen? Im Prinzip
  geht man beim Entwurf eines solchen Modells genauso vor wie im
  sequenziellen Fall: Man beginnt mit einem realen parallelen Computer
  und modelliert mathematisch alles, was dort so passiert. Dann
  beginnt man, von Besonderheiten der Architektur zu
  abstrahieren. Beispielsweise ist es wohl eher unerheblich, ob nun
  2~Gigabyte oder 4~Gigabyte Speicher zur Verfügung stehen. Ebenso ist
  es reichlich unerheblich, ob es ein A20-Gate gibt. Resultat dieser
  Vereinfachungen ist idealerweise ein einfaches, elegantes
  mathematisches Modell mit der Eigenschaft, dass alle anderen
  sinnvollen Modelle ohne großen Zeit- oder Platzverlust simuliert
  werden können. Im Sequenziellen hat dieser Ansatz gut funktioniert:
  Es sind dabei das \textsc{ram}-Modell und die Turing-Maschine herausgekommen;
  zwei sehr einfache Modelle, die beide einander simulieren können.

  Im Parallelen ist die Sache leider komplexer. Es gibt kein Modell
  von dem man behaupten könnte, es sein gleichzeitig einfach, elegant
  und universell einsetzbar. Ist das Modell schön einfach (wie das
  \textsc{pram}-Modell), so lässt es leider zu viele reale Details weg, in
  denen bekanntlich der Teufel steckt. Ist es geradezu übermächtig (wie 
  das Netzwerkmodell, in dem die Kommunikation der Prozessoren
  komplett modelliert wird), so kann man kaum etwas Sinnvolles
  beweisen.

  In der heutigen Vorlesung wollen wir die Problematik
  eines geeigneten Maschinenmodells für parallele Algorithmen
  erörtern. Das Resultat kann man auch gleich vorwegnehmen: Wir werden
  später auf das \textsc{pram}-Modell setzen. Wie schon gesagt ist dieses Modell
  eigentlich »zu optimistisch«. Dies hat aber auch einen wichtigen
  Vorteil: Können wir zeigen, dass sich ein Problem \emph{noch nicht
    mal auf einer \textsc{pram} schnell lösen lässt}, so gilt dies sicher auch
  für alle »weniger optimistischen« Modelle. 
\end{lecture notes intro}
 

\section{Einführung}

\subsection{Mehr Prozessoren = Schneller?}

\begin{frame}{Das Versprechen der Parallelverarbeitung.}
  \begin{itemize}
  \item Die Kosten, Prozessoren schneller zu machen, steigen
    exponentiell.
  \item Die Kosten, die Anzahl der Prozessoren zu erhöhen, steigen
    linear.
  \end{itemize}

  \begin{alertblock}{Versprechen}
    Durch Parallelverarbeitung kann man Probleme billiger
    schnell lösen als durch schnellere Prozessoren. 
  \end{alertblock}

  \begin{discussion}[lines=5]
    Welche Einwände lassen sich gegen dieses Argument erheben?
  \end{discussion}
\end{frame}


\subsection{Arten der Parallelverarbeitung}

\begin{frame}{Grundsätzliche Arten von Parallelverarbeitung.}
  \begin{enumerate}
  \item SISD: single instruction, single data

    »Eine Instruktion auf einen Datensatz anwenden«

    \ExampleInline{Normale CPU}
  \item SIMD: single instruction, multiple data

    »Eine Instruktion auf mehrere Datensätze anwenden«

    \ExampleInline{Graphikprozessor}
  \item MIMD: multiple instructions, multiple data

    »Unterschiedliche Instruktionen auf unterschiedliche
    Datensätze anwenden«

    \ExampleInline{Dual-Core-Prozessoren, große Parallelrechner}
  \end{enumerate}
\end{frame}


\subsection{Fallbeispiel}

\begin{frame}{Die Matrix-Vektor-Multiplikation.}
  \begin{block}{Problem}
    \begin{description}
    \item[Eingabe] Eine $n \times n$ Matrix $A$ und ein Vektor $v$.
    \item[Ausgabe] $b = A \cdot v$.
    \end{description}
  \end{block}
  \begin{discussion}[lines=7]
    Wie löst man das Problem, wenn man \dots
    \begin{itemize}
    \item \dots einen Prozessor hat?
    \item \dots zwei Prozessoren hat?
    \item \dots drei Prozessoren hat?
    \item \dots $n/2$ Prozessoren hat?
    \item \dots $n/2 + 1$ Prozessoren hat?
    \item \dots $n$ Prozessoren hat?
    \item \dots $2n$ Prozessoren hat?
    \item \dots $n^2$ Prozessoren hat?
    \item \dots $2n^2$ Prozessoren hat?
    \end{itemize}
  \end{discussion}
\end{frame}


\begin{frame}{Was bringen mehr Prozessoren?}
  Für das Problem Matrix-Vektor-Multiplikation hat die Verdoppelung
  der Prozessoranzahl folgenden Effekt:
  \begin{itemize}
  \item Für kleine Prozessorzahlen halbiert sich jedesmal die
    Rechenzeit. 
  \item Für Prozessorzahlen über $n$ gilt dies nicht mehr exakt, aber fast.
  \item Für Prozessorzahlen in der Nähe von $n^2$ verringert sich die
    Rechenzeit kaum.
  \item Für Prozessorzahlen über $n^2$ ändert sich die Rechenzeit
    nicht mehr.
  \end{itemize}
\end{frame}



\section{Das DAG-Modell}

\begin{frame}{Die Idee hinter dem DAG-Modell.}

  \begin{itemize}
  \item Das DAG-Modell macht \alert{Abhängigkeiten} sichtbar.
  \item Das DAG-Modell blendet die Implementierung aus.
  \end{itemize}

  \begin{block}{Beschreibung des DAG-Modells}
    \begin{itemize}
    \item Im DAG-Modell wird ein Algorithmus durch einen DAG (directed
      acyclic graph) beschrieben.
    \item Die Eingabe liegt an den Knoten mit Eingrad~0 an.
    \item Die anderen Knoten führen Berechnungen durch.
    \item Sie können ihre Berechnung erst durchführen, wenn die
      Ergebnisse der Vorgänger vorliegen.
    \item Berechnungen können recht beliebig sein.
    \end{itemize}
  \end{block}

  \begin{example}
    \begin{tikzpicture}[graph,x=2cm]

      \foreach \x in {0,1,2,3,4}
      {
        \node[node] (a\x) at (\x,0) {};
        \node[node] (b\x) at (\x,1) {};
      }

      \draw[->] (a0) -- (a1); 
      \draw[->] (a1) -- (a2); 
      \draw[->] (a2) -- (a3); 
      \draw[->] (a3) -- (a4); 
      \draw[->] (b0) -- (b1); 
      \draw[->] (b1) -- (b2); 
      \draw[->] (b2) -- (b3); 
      \draw[->] (b3) -- (b4); 
      \draw[->] (a1) -- (b2); 
      \draw[->] (b3) -- (a4); 
    \end{tikzpicture}
  \end{example}
\end{frame}


\begin{frame}{Das Konzept des Schedules.}

  \begin{definition}[Schedule]
    Sei $G= (V,E)$ ein DAG und $P$ eine Menge von Prozessoren. Ein
    \alert{Schedule} $S$ ist eine Abbildung, die jedem Knoten von $G$
    einen Prozessor $p \in P$ zuordnet und einen Zeitpunkt $t \in
    \mathbb N$. Dabei muss gelten:
    \begin{enumerate}
    \item Keinen zwei Knoten darf derselbe Zeitpunkt und gleichzeitig
      derselbe Prozessor zugeordnet werden.
    \item Der Zeitpunkt jedes Prozessors muss größer sein als der
      seiner Vorgänger.
    \end{enumerate}
  \end{definition}

  Der maximale in $S$ vorkommende Zeitpunkt heißt
  \alert{Zeitbedarf}, abgekürzt $T(S)$.
  
  \begin{example}
    \begin{tikzpicture}[graph,node/.append style={font=\tiny},x=2cm]

      \foreach \x in {0,1,2,3,4}
      {
        \node[node,text badly centered,text width=7mm] (a\x) at (\x,0) {$p=P_1$\\<all>$t=\x$};
        \node[node,text badly centered,text width=7mm] (b\x) at (\x,1) {$p=P_2$\\<all>$t=\x$};
      }

      \draw[->] (a0) -- (a1); 
      \draw[->] (a1) -- (a2); 
      \draw[->] (a2) -- (a3); 
      \draw[->] (a3) -- (a4); 
      \draw[->] (b0) -- (b1); 
      \draw[->] (b1) -- (b2); 
      \draw[->] (b2) -- (b3); 
      \draw[->] (b3) -- (b4); 
      \draw[->] (a1) -- (b2); 
      \draw[->] (b3) -- (a4); 
    \end{tikzpicture}
  \end{example}
\end{frame}


\begin{exercise frame}[lines=8]

  \begin{tikzpicture}[graph,x=2cm]

    \foreach \x in {0,1,2,3,4}
    {
      \node [node] (a\x) at (\x,0) {};
      \node [node] (b\x) at (\x,1) {};
    }
    
    \node [node] (c2) at (2,2) {};
    \node [node] (c3) at (3,2) {};
    
    \draw[->] (a0) -- (a1); 
    \draw[->] (a1) -- (a2); 
    \draw[->] (a2) -- (a3); 
    \draw[->] (a3) -- (a4); 
    \draw[->] (b0) -- (b1); 
    \draw[->] (b1) -- (b2); 
    \draw[->] (b2) -- (b3); 
    \draw[->] (b3) -- (b4); 
    \draw[->] (a1) -- (b2); 
    \draw[->] (b3) -- (a4); 
    \draw[->] (b1) -- (c2); 
    \draw[->] (c2) -- (c3); 
    \draw[->] (c3) -- (b4); 
  \end{tikzpicture}

  \begin{block}{Gruppe 1}
    Geben Sie einen optimalen Schedule für den DAG mit $P
    = \{P_1,P_2\}$ an.    
  \end{block}
  \begin{block}{Gruppe 2}
    Geben Sie optimale Schedules für den DAG mit $P = \{P_1\}$ an und dann für
    $P = \{P_1,P_2,P_3\}$.    
  \end{block}
\end{exercise frame}


\section{Das PRAM-Modell}

\subsection{Die Idee}

\begin{frame}{\textsc{pram}s im Überblick}{Aufbau und Initialisierung}
  \begin{itemize}
  \item Die Abkürzung \textsc{pram} steht für Parallel Random Access Machine.
  \item Jeder Prozessor ist eine eigene \textsc{ram}. Das bedeutet:
    \begin{itemize}
    \item
      Eine \textsc{ram} hat Zugriff auf einen Satz Register, in denen Zahlen stehen.
    \item
      Eine \textsc{ram} arbeitet ein festes Programm ab.
    \end{itemize}
    \alert{Neu im Vergleich zur einfachen \textsc{ram} ist:}
    \begin{itemize}
    \item
      Es gibt noch \alert{globale Register}.
    \item
      Es gibt noch ein \alert{nur lesbares Prozessor-ID-Register}.
    \item
      Es gibt neue Befehle, um die globalen Register zu lesen und zu
      beschreiben. 
    \end{itemize}
  \item Die Prozessoren arbeiten synchron (exakt gleichgetaktet).
  \item Alle Prozessoren führen das gleiche Programm aus, aber bei jedem
    Prozessor ist PID anders initialisiert.
  \item Ein- und Ausgabe liegen in bestimmten Bereichen des globalen
    Speichers. 
  \end{itemize}
\end{frame}

\begin{frame}{\textsc{pram}s im Überblick}{Kommunikation}
  \begin{itemize}
  \item Die Kommunikation erfolgt mittels des globalen Speichers
    (shared memory).
  \item Man unterscheidet, ob der Lesezugriff ausschließend (exclusive read)
    oder parallel (concurrent read) sein darf.
  \item Schreibzugriff kann man ebenfalls unterschiedlich regeln:
    \begin{itemize}
    \item Nur ein bestimmter Prozessor darf eine bestimmte globale Zelle
      beschreiben (owner write).
    \item Immer nur ein Prozessor darf schreiben (exclusive write).
    \item Paralleles Schreiben (concurrent write) ist erlaubt. Hier gibt es
      die Untervarianten Common, Arbitrary und Priority. 
    \end{itemize}
  \item Insgesamt gibt es folgende sinnvolle Zugriffsarten:
    EROW, EREW, CROW, CREW, Common-CRCW, Aribtrary-CRCW,
    Priority-CRCW.
  \end{itemize}
\end{frame}


\subsection{Ein Beispiel}

\begin{frame}[fragile]{Beispiel eines \textsc{pram}-Programms.}

  Folgendes Programm berechnet die Summe der Zahlen im Array $A$ im
  globalen Speicher.

\begin{lstlisting}[style=pseudocode]
for $h$ <- $1$ to $\log n$ seq do
    if $\mathit{pid}\le n/2^h$ then
        global read $a$ <- $A[2\cdot\mathit{pid}]$
        global read $b$ <- $A[2\cdot\mathit{pid}-1]$
        $c$ <- $a+b$
        global write $A[\mathit{pid}]$ <- $c$
if $\mathit{pid}=1$ then
    global write $S$ <- $c$
\end{lstlisting}

  \begin{lecture exercise}[lines=3]
    Welche Schreib-/Lese-Zugriffsart wird im Programm verwendet?
  \end{lecture exercise}
\end{frame}


\mode
<article>
\begin{lecture notes only}[Skript]
  Das \textsc{pram}-Modell wird das »zentrale« Modell sein, welches
  wir im Rest der Veranstaltung benutzen werden. Aus diesem Grund ist
  im Folgenden (nur im Skript) für an Formalisierungen Interessierte
  eine genaue Beschreibung des Modells angegeben. \emph{Es ist aber
    nicht nötig, diese genau zu kennen, Algorithmen und Beweise werden
    wir eher auf der Pseudo-Code-Ebene führen.} (Man beweist auch nicht die
  Eigenschaften eines Quicksorts anhand einer Implementation in
  Maschinensprache\dots) Es gibt verschiedene Arten, \textsc{ram}s und
  \textsc{pram}s zu formalisieren, die folgende Formalisierung
  ist eher für Komplexitätsbetrachtungen geeignet, da es nur wenige
  Befehle gibt und »aufwendige« Berechnungen wie die Multiplikation
  explizit \emph{nicht} als ein Befehl zur Verfügung stehen.

  \def\Global#1{\langle \GR#1\rangle}
  \def\Local#1{\langle \R#1\rangle}
  \def\PC{\langle \text{\textsc{pc}}\rangle}
  \def\R{\text{\textsc{r}}}
  \def\GR{\text{\textsc{gr}}}
  \def\RR{\text{\textsc{rr}}}
  \def\GRR{\text{\textsc{grr}}}

  \begin{definition}[Syntax eines \textsc{pram}-Programms]
    Ein \emph{\textsc{pram}-Programm} besteht aus einer endlichen, durchnummerierten
    Folge von Befehlen, wobei die Zählung mit 1 beginnt. In Befehlen kommen
    \emph{Registeradressierungen} vor, wovon es genau folgende vier Arten
    gibt (im Folgenden sei immer $i,j,k \in \mathbb N$): 
    \begin{enumerate}
    \item $\R i$ bezeichnet eine \emph{direkte lokale Adressierung}
    \item $\RR i$ bezeichnet eine \emph{indirekte lokale Adressierung}
    \item $\GR i$ bezeichnet eine \emph{direkte globale
        Adressierung}
    \item $\GRR i$ bezeichnet eine \emph{indirekte globale Adressierung}
    \end{enumerate}
    Folgende Befehle sind möglich:
    \begin{itemize}
    \item \textsf{\small Die Transportbefehle}
      \begin{enumerate}
      \item[1.] $\R i \gets \R j$
      \item[2.] $\R i \gets \RR j$
      \item[3.] $\R i \gets \GR j$
      \item[4.] $\R i \gets \GRR j$
      \item[5.] $\RR i \gets \R j$
      \item[6.] $\GR i \gets \R j$
      \item[7.] $\GRR i \gets \R j$
      \end{enumerate}
    \item \textsf{\small  Die arithmetischen Befehle}
      \begin{enumerate}
      \item[8.] $\R i \gets k$
      \item[9.] $\R i \gets \mathit{pid}$
      \item[10.] $\R i \gets \R j + \R k$
      \item[11.] $\R i \gets \R j - \R k$
      \item[12.] $\R i \gets \lfloor \frac{1}{2} \R j \rfloor$
      \end{enumerate}
    \item  \textsf{\small Die Sprungbefehle}
      \begin{enumerate}
      \item[13.] \pseudocode{if $\R i = 0$ goto $k$}
      \item[14.] \pseudocode{if $\R i > 0$ goto $k$}
      \item[15.] \pseudocode{goto $k$}
      \end{enumerate}
      Bei allen Sprungbefehlen muss $k$ die Nummer einer Programmzeile
      sein. 
    \item  \textsf{\small Die Stopp- und Idlebefehle}
      \begin{enumerate}
      \item[16.] \pseudocode{idle while $\GRR i = 0$}
      \item[17.] \pseudocode{stop}
      \end{enumerate}      
      Der letzte Befehl eines Programms muss der Stoppbefehl sein.
    \end{itemize}
  \end{definition}
  Ein Beispiel eines \textsc{pram}-Programms wäre folgendes:
\begin{lstlisting}[style=pseudocode]
$\R0 \gets \mathit{pid}$
$\R3 \gets \GR0$
$\R2 \gets 1$
$\R1 \gets \R0 + \R2$
$\R4 \gets \R1 - \R3$
if $\R4 > 0$ goto 13
$\R5 \gets \GRR0$
$\R6 \gets \GRR1$
$\R7 \gets \R6 + \R7$
$\GRR0 \gets \R7$
$\R2 \gets \R2 + \R2$
goto 4
stop
\end{lstlisting}
  \begin{definition}[Semantik eines \textsc{pram}-Programms]
    Sei $P$ ein \textsc{pram}-Programm. Eine \textsc{pram} hat einen
    \emph{globalen Speicher} sowie eine  
    unbeschränkte Anzahl an Prozessoren, die alle einen \emph{lokalen
      Speicher} besitzen. Eine \textsc{pram} arbeitet getaktet, wobei
    mit Takt $t=0$ begonnen wird. Der Inhalt des $i$-ten globalen
    Registers zum Zeitpunkt $t$ ist eine natürliche Zahl, welche wir
    mit $\Global i_t$ bezeichnen. Der Inhalt des $i$-ten lokalen
    Registers des $p$-ten Prozessors zum Zeitpunkt~$t$ bezeichnen wir
    mit $\Local i^p_t$. Weiterhin verfügt jeder Prozessor über einen
    Programmschrittzähler, dessen Wert zum Zeitpunkt $t$ mit $\PC^p_t$
    bezeichnet wird.

    Die Gesamtheit der Inhalte aller lokalen und globalen Register
    (dies sind abzählbar unendlich viele) bezeichnen wir als
    \emph{Konfiguration}. Eine \emph{Berechnung} ist eine Folge von
    Konfigurationen, die den weiter unten angegebenen Bedingungen
    genügt. Eine \emph{Eingabe} für eine \textsc{pram} ist ein
    Vektor~$v$ von natürlichen Zahlen. Zu einer Eingabe gehört die
    \emph{Anfangskonfiguration} bei der alle lokalen Register $0$
    sind, alle Programmschrittzähler $1$ sind, das erste globale
    Register ($\GR0$) die Dimension $n$ von $v$ enthält und die globalen
    Register $\GR1$ bis $\GR n$ die Komponenten von $v$ enthalten. Eine
    \emph{Endkonfiguration} ist eine Konfigurationen, in der der
    Programmschrittzähler aller Prozessoren eine Nummer enthält, für
    die der Programmbefehl »Stopp« lautet.

    Die \emph{Berechnungsrelation} gibt an, welche neue Konfiguration
    zum Zeitpunkt $t+1$ aus der Konfiguration zum Zeitpunkt $t$
    hervorgeht. Dazu führen alle Prozessoren gleichzeitig den
    jeweiligen Befehl aus, der im \textsc{pram}-Programm $P$ in der
    Zeile $\PC^p_t$ steht. Die Effekte dieser Befehle sind in der
    folgenden Tabelle angegeben:
    
    \medskip
    \begin{colortabular}{lp{9.1cm}}
      \emph{Befehl} & \emph{Wirkung, wenn von Prozessor $p$ ausgeführt} \\
      $\R i \gets \R j$ & $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \Local j_t^p$ \\
      $\R i \gets \RR j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \Local{\Local j_t^p}_t^p$ \\
      $\R i \gets \GR j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \Global j_t$\\
      $\R i \gets \GRR j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \Global{\Local j_t^p}_t$\\
      $\RR i \gets \R j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local {\Local i_t^p}_{t+1}^p = \Local j_t^p$ \\
      $\GR i \gets \R j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$,  $\Global i_{t+1} = \Local j_t^p$, aber siehe unten\\
      $\GRR i \gets \R j$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Global {\Local i_t^p}_{t+1} = \Local j_t^p$, aber siehe unten \\
      $\R i \gets k$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = k$ \\
      $\R i \gets \mathit{pid}$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = p$ \\
      $\R i \gets \R j + \R k$ & $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \Local j_t^p+\Local k_t^p$ \\ 
      $\R i \gets \R j - \R k$ & $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \max\{\Local j_t^p-\Local k_t^p,0\}$  \\
      $\R i \gets \lfloor \frac{1}{2} \R j \rfloor$ &  $\PC_{t+1}^p = \PC_{t}^p+1$, $\Local i_{t+1}^p = \lfloor\Local j_t^p/2\rfloor$ \\
      {\pseudocode!goto $k$!} & $\PC_{t+1}^p = k$, \\
      {\pseudocode!if $\R i = 0$ goto $k$!} & $\PC_{t+1}^p = k$, falls
      $\Local i_t^p = 0$, sonst $\PC_{t+1}^p = \PC_{t}^p+1$\\
      {\pseudocode!if $\R i > 0$ goto $k$!} &  $\PC_{t+1}^p = k$, falls
      $\Local i_t^p > 0$, sonst $\PC_{t+1}^p = \PC_{t}^p+1$  \\
      {\pseudocode!idle while $\GRR i = 0$!} & $\PC_{t+1}^p = \PC_{t}^p+1$, falls
      $\Global {\Local i_t^p}_{t} > 0$, sonst keine Änderung\\
      {\pseudocode!stop!} & keine Änderungen \\
    \end{colortabular}

    Es kann vorkommen, dass mehrere Prozessoren gleichzeitig auf ein
    globales Register schreibend zugreifen. Dann können Konflikte
    entstehen und der Wert von $\Global i_{t+1}$ ist nicht
    wohldefiniert, da unterschiedliche Angaben vorliegen
    können. Dieses Problem wird wie folgt aufgelöst:
    \begin{enumerate}
    \item Beim \emph{Owner-Write-Modell} darf auf das Register $\GR i$ nur
      Prozessor $i$ schreiben. Die Nachfolgekonfiguration
      ist nicht definiert, falls ein Prozessor sich nicht daran hält.
    \item Beim \emph{Exclusive-Write-Modell} darf in jedem Takt für jedes
      globale Register $i$ nur genau ein Prozessor $\Global i_{t+1}$
      einen Wert zuweisen. Versuchen dies mehrere, so gibt es wiederum
      keine Nachfolgekonfiguration.
    \item Beim \emph{Arbitrary-Write-Modell} gibt es im Falle von
      unterschiedlichen Werten, die von verschiedenen Prozessor in
      dasselbe globale Register $\GR i$ geschrieben werde, für jeden
      Wert eine eigene Nachfolgekonfiguration, in der dieser Wert
      eingenommen wird (das Verhalten ist also nichtdeterministisch).
    \item Beim \emph{Common-Write-Modell} müssen alle Prozessoren denselben
      Wert schreiben. Geschieht dies nicht, ist die
      Nachfolgekonfiguration wieder nicht definiert.
    \item Beim \emph{Priority-Write-Modell} sei $P_i$ die Menge aller
      Prozessornummern von Prozessoren, die versuchen, im Zeittakt $t$
      den Wert von $\Global i_{t+1}$ zu verändern. Sei $p_i = \min
      P_i$ und sei $x_i$ der Wert, den $p_i$ schreiben möchte. Dann ist
      $\Global i_{t+1} = x_i$.
    \end{enumerate}
    Während ein Prozessor den Idle-Befehl ausführt (und somit schläft)
    zählt er nicht zu den aktiven  Prozessoren und liefert keinen
    Beitrag zur so genannten \emph{Arbeit} des Systems (siehe dazu die
    nächste Vorlesung). 
  \end{definition}
\end{lecture notes only}

\mode
<all>

\section{Das Netzwerkmodell}

\subsection{Das Modell}

\begin{frame}{Die Idee hinter dem Netzwerk-Modell.}
  \begin{itemize}
  \item Man modelliert ein festes Kommunikationsnetzwerk durch einen Graphen.
  \item Die \alert{Knoten} des Graphen sind die Prozessoren.
  \item Die \alert{Kanten} des Graphen sind Kommunikationskanäle.
  \item Die Prozessoren arbeiten in der Regel \alert{asynchron} und
    schicken sich gegenseitig Nachrichten.
  \end{itemize}
\end{frame}

\begin{frame}{Das Netzwerk-Modell -- parallel oder verteilt?}
  \begin{block}{Gemeinsamkeiten mit verteilten Systemen}
    \begin{itemize}
    \item Modellierung des Kommunikationsnetzwerks.
    \item Nachrichtenbasiertes Modell.
    \end{itemize}
  \end{block}
  \begin{block}{Unterschiede zu verteilten Systemen}
    \begin{itemize}
    \item Feste Topologie (fest verdrahtet)
    \item Sichere Kommunikation
    \end{itemize}    
  \end{block}
\end{frame}

\begin{frame}{Wichtige Parameter eines Netzwerks}
  \begin{block}{Parameter Durchmesser}
    Maximale Entfernung zwischen Knoten.\\

    Dies ist die Zeit, die eine Nachricht höchstens braucht.\\

    \alert{Kleiner ist besser.}
  \end{block}
  \begin{block}{Parameter Grad}
    Maximale Anzahl von Nachbarn eines Knoten.\\

    Je höher der Grad, desto mehr Kabel muss man ziehen.\\

    \alert{Kleiner ist besser.}
  \end{block}
  \begin{block}{Parameter Zusammenhänge}
    Minimale Anzahl von Knoten/Kanten, die man
    löschen muss, um das Netz in zwei Teile zu spalten.\\

    Je höher der Zusammenhang, desto ausfallsicherer.\\

    \alert{Größer ist besser.}
  \end{block}
\end{frame}


\subsection{Wichtige Topologien}

\begin{frame}{Liste wichtiger Netztopologien.}
  \begin{enumerate}
  \item Lineares Array (Pfad)
  \item Ring
  \item 2D-Gitter
  \item 3D-Gitter
  \item Hyperwürfel
  \item Binärbaum
  \end{enumerate}
  \begin{lecture exercise}[lines=6]
    Bestimmen Sie für eine der obigen Topologien für $p$
    Prozessoren den Durchmesser, Grad und Kantenzusammenhang.
  \end{lecture exercise}
\end{frame}



\begin{summary}
  \begin{enumerate}
  \item \alert{Parallele Algorithmen} führen mehrere Berechnungen
    koordiniert aus.
  \item Probleme haben häufig \alert{parallele Anteile} und
    \alert{sequentielle Anteile}.
  \item Das \alert{DAG-Modell} beschreibt abstrakt, welche Anteile parallel
    und welche sequentiell sind.
  \item Das \alert{\textsc{pram}-Modell} beschreibt Algorithmen konkreter.
  \item Das \alert{Netzwerkmodell} modelliert die \alert{Kommunikation} bei
    parallelen Programmen realistischer als das \textsc{pram}-Modell.
  \end{enumerate}
\end{summary}

\end{body}

