\documentclass[a4paper,12pt]{article}

\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage[left=3cm,right=3cm,top=2cm,bottom=3cm]{geometry}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{hyperref}

\newcommand{\ignore}[1]{}
\newcommand{\seqlabel}[2]{%
    \textcolor{black}{%
    (\textcolor{red}{#1},
     \textcolor{blue}{#2})}}
\newcommand{\seqbar}[2]{%
    \begin{tikzpicture}
    \fill[color=red!70]  (0,0)  rectangle +(#1,0.3);
    \fill[color=blue!70] (#1,0) rectangle +(#2,0.3);
\end{tikzpicture}}

\title{Seminarvortrag \\
       Amdahlsches und Gustafsonsches Gesetz}
\author{Volker Grabsch \and Yves Radunz}
\date{26. Mai 2008}

\begin{document}

\maketitle

\subsection*{Veröffentlicht unter}

    \url{http://www.profv.de/uni/}

\subsection*{Lizenziert unter}

    \href{http://creativecommons.org/licenses/by-sa/3.0/deed.de}{%
    % CC-Icons heruntergeladen von:
    % http://creativecommons.org/presskit
    \includegraphics{by-sa}
    Creative Commons BY-SA 3.0}

\tableofcontents

\newpage
\section{Einleitung}

Es gibt viele theoretische Untersuchungen
zur parallelen Programmierung.
Doch zwei von ihnen
haben besonderes Aufsehen erregt:
das Gesetz von Amdahl \cite{Amdahl}
und das Gesetz von Gustafson \cite{Gustafson}.

Während das Amdahlsche Gesetz gern als
Totschlagargument gegen massive Parallelisierung
angeführt wurde,
sorgte das Gustafsonsche Gesetz wieder
für mehr Optimismus.
Obwohl es sehr einfache Theorien sind,
die eng miteinander zusammenhängen,
ranken sich um sie
viele Missverständnisse und hitzige Diskussionen.
Es gab sogar Versuche zur "`Schlichtung"'. \cite{Shi}

Wir werden uns in diesem Vortrag
beide Modelle und ihre Folgerungen
genauer ansehen.
Dabei versuchen wir,
ein wenig Klarheit
in dieses verwirrende und heiß diskutierte Thema
hinein zu bringen.



\section{Das Amdahlsche Gesetz}

Das Amdahlsche Gesetz \cite{Amdahl}
beschäftigt sich mit der Frage,
wie stark man ein bestimmtes Programm
durch Parallelisierung beschleunigen kann.
In diesem Abschnitt
werden wir uns
das Gesetz an sich ansehen,
einfache Folgerungen ziehen
und zum Schluss die Grenzen des Modells beleuchten.


\subsection{Amdahlsches Gesetz}

Das Amdahlsche Gesetz geht von einem
sehr einfachen Modell
des zu parallelsierenden Programmcodes
aus.
Es nimmt an,
dass jedes Programm zu einem gewissen Teil beliebig stark parallelisierbar ist,
und zu einem gewissen Teil sequenziell ablaufen muss,
d.h.\ überhaupt nicht parallelisiert werden kann.

Wir starten unser Programm hypothetisch
auf einem System
mit nur einem Prozessor,
und normieren seine Laufzeit auf $1$.
Dann schauen wir,
wieviel Zeit das Programm
im parallelisierbaren Teil verbringt,
und bezeichnen diesen Anteil mit $P$.
Der sequenzielle Teil hat dann die Laufzeit $(1-P)$.

Wie schnell läuft das Programm
auf einem System mit $N$ Prozessoren?
Die Laufzeit des sequenziellen Teils
ändert sich nicht.
Der parallelisierbare Teil jedoch
wird optimal auf alle Prozessoren verteilt
und läuft daher $N$-mal so schnell.
Als neue Laufzeit ergibt sich:
    \begin{align*}
    \underbrace{(1-P)}_{\text{sequenziell}}
    \quad + \quad
    \underbrace{\frac{P}{N}}_{\text{parallel}}
    \end{align*}
Wieviel schneller ist das Programm nun geworden?
Ganz einfach:
    \begin{align*}
    \text{Zeitgewinn}
        &= \frac{\text{ursprüngliche Laufzeit}}{\text{neue Laufzeit}}
         = \frac{1}{(1-P) + \frac{P}{N}}
    \end{align*}
Dies ist das \emph{Amdahlsche Gesetz}.
Dabei ist 
$N$ die Anzahl der Prozessoren und
$P$ der Laufzeit-Anteil des parallelisierbaren Programmcodes.

Ein Zeitgewinn von $2$ bedeutet,
dass das Programm nun doppelt so schnell ist wie vorher.
In der Literatur findet man
an Stelle des Begriffs "`Zeitgewinn"'
auch "`speedup"' oder "`Geschwindigkeitsgewinn"'.


\subsection{Höchstgeschwindigkeit}

Kommen wir nun zur
ersten und wichtigsten Konsequenz
des Amdahlschen Gesetzes:
Ein Programm kann durch Parallelisierung
nur bis zu einer bestimmtem Grenze hin
beschleunigt werden.
Das ist ein harter Schlag!
Es ist die Hauptursache für den
Pessimismus gegenüber massiver Parallelisierung.
Genauer gesagt gilt folgende Ungleichung:
    \begin{align*}
    \text{Zeitgewinn} &< \frac{1}{1-P}
    \end{align*}
Diese Ungleichung folgt direkt aus dem Modell,
denn $(1-P)$ ist per Definition genau der
Laufzeit-Anteil des Programms,
der bei Parallelisierung nicht verschwindet.

Wir können die Grenze auch dadurch herleiten,
dass wir im Amdahlschen Gesetz
die Anzahl $N$ der Prozessoren
gegen $\infty$ laufen lassen:
    \begin{align*}
       \lim_{N\rightarrow\infty} \text{Zeitgewinn}
    &= \lim_{N\rightarrow\infty} \frac{1}{(1-P) + \frac{P}{N}}
     =                           \frac{1}{1-P}
    \end{align*}
Das heißt,
selbst mit tausenden Prozessoren
können wir
ein zu 95\% parallelisierbares Programm
höchstens um den Faktor~20
beschleunigen.
($\frac{1}{1-P} = \frac{1}{1-0,95} = 20$)

Das folgende Diagramm veranschaulicht dies
für verschieden gut parallelisierbare Programme.
Dabei ist die $N$-Achse logarithmisch eingeteilt,
d.h.\ die Anzahl der Prozessoren wird immer verdoppelt:
    \begin{center}
    \begin{tikzpicture}[domain=0:12,xscale=0.8,yscale=0.4,>=latex]
    \draw[very thin,color=gray] (0,0) grid (12.1,20.1);
    \foreach \P in {50,80,90,95}
        \draw[color=blue]
            plot[id=amdahl-\P]
            function{1/((1-\P*.01)+\P*0.01/(2**x))}
            node[right] {$P = \P\%$};
    \draw[->] (0,0) -- (13,0) node[right] {$N$};
    \draw[->] (0,0) -- (0,22) node[above] {Zeitgewinn};
    \foreach \x/\N in {1/2,3/8,5/32,8/256,12/4096}
        \draw (\x,0.2) -- (\x,-0.2) node[below] {\N};
    \foreach \Z in {1,5,10,...,20}
        \draw (0.1,\Z) -- (-0.1,\Z) node[left] {\Z};
    \end{tikzpicture}
    \end{center}
Weitere Anwendungen
des Amdahlschen Gesetzes
besprechen wir
in Kapitel~\ref{amdahl-ausweitungen}.


\newpage
\subsection{Grenzen des Amdahlschen Gesetzes}

So schön und einfach das Amdahlsche Gesetz auch ist,
es hat natürlich seine Grenzen.
Folgende Aspekte der Parallelisierung werden
vom ihm nicht berücksichtigt:
    \begin{enumerate}
    \item
        Je mehr Prozessoren an einem Problem arbeiten,
        umso aufwändiger wird die \textbf{Kommunikation} zwischen ihnen.
        Dieser zusätzliche Verwaltungsaufwand
        senkt
        die zu erwartenden Zeitgewinne
        durch Parallelisierung
        nochmals.

        Wir werden auf diesen Aspekt
        nicht weiter eingehen,
        da er den ohnehin schon vorhandenen Pessimismus
        nur noch schlimmer machen würde.
    \item
        Neben der Anzahl der Prozessoren
        wachsen auch \textbf{weitere Resourcen} mit der Parallelisierung.
        So bringt jeder zusätzliche Prozessor
        normalerweise auch Cache mit,
        sodass insgesamt für die Berechnungen
        viel mehr Prozessor-Cache zu Verfügung steht.

        In einem Rechencluster kommt mit jedem neuen Prozessor
        sogar ein kompletter Computer hinzu,
        sodass mehr RAM, mehr Festplattenspeicher, u.s.w.
        zu Verfügung steht.

        Wir werden in Kapitel~\ref{wirkliche-widerlegung}
        hierauf zurück kommen.
    \item
        Oft wollen wir unsere Ergebnisse
        gar nicht schneller haben,
        sondern lieber
        \textbf{größere Probleme}
        in der bisherigen Zeit
        berechnen.

        Diese Idee führt uns direkt zum Gustafsonschen Gesetz,
        welches wir in Kapitel~\ref{gustafson} besprechen werden.
    \end{enumerate}



\section{Ausweitungen des Amdahlschen Gesetzes}
\label{amdahl-ausweitungen}

Bisher hatten wir uns nur mit dem Effekt der Parallelisierung eines Programmabschnitts auf die Gesamtlaufzeit befasst.
An dieser Stelle sollen daher einige Bemerkungen zu der Anwendung des Amdalschen Gesetzes in anderen Zusammenh"angen folgen.
\cite{AmdahlWikipedia}


\subsection{"Ubertragung auf sequenzielle Programme}
Betrachten wir einmal ein sequenzielles Programm, welches sich aus mehreren Abschnitten zusammensetzt.
Jetzt stellt sich die Frage, wie stark die Gesamtlaufzeit des Programms verk"urzt w"urde, wenn wir die Ausf"uhrung eines der Abschnitte durch Optimierung um einen bestimmten Faktor beschleunigten.

Hierzu w"ahlen wir $P$ als den urspr"unglichen (d.h. vor der Optimierung) Anteil des optimierten Programmteils an der Gesamtlaufzeit.
F"ur $N$ k"onnen wir nun an Stelle der Anzahl der verwendeten Prozessoren den Faktor einsetzen, um welchen die Ausf"uhrung dieses Programmfragments beschleunigt wird.

Damit ergibt sich eine neue Laufzeit von $(1-P)+\frac PN$, da der nicht optimierte Abschnitt weiterhin mit der einfachen Geschwindigkeit ausgef"uhrt wird und damit einen Zeitaufwand von $1-P$ hat.
Der optimierte Abschnitt wird nun $N$-mal schneller ausgef"uhrt und ben"otigt somit nur noch eine Zeit von $\frac PN$.

Der Geschwindigkeitsgewinn in der Ausf"uhrung des gesamten Programm ergibt sich also wieder durch den bereits bekannten Quotienten aus altem Zeitaufwand und neuem Zeitaufwand:

\[\frac{1}{(1-P) + \frac{P}{N}}\]

\bigskip

Oftmals stellt sich das Problem, welcher Teil des Programms eher zu optimieren ist, da mit der Optimierung schlie"slich auch ein Mehraufwand bei der Implementierung und/oder "Ubersetzung verbunden ist.
Mit Hilfe des Amdahlschen Gesetzes l"asst sich der erwartete Zeitgewinn f"ur das gesamte Programm nun recht leicht absch"atzen.
Man ben"otigt daf"ur wie bereits erw"ahnt nur den Anteil des ggf. zu optimierenden Programmteils an der gesamten Laufzeit des Programms und den erwarteten Geschwindigkeitsgewinn innerhalb dieses Programmteils nach der Optimierung.

\bigskip

Beispielsweise w"ahlen wir ein Programm, welches aus zwei Teilen besteht.
Nennen wir diese einmal \textcolor{red}A und \textcolor{blue}B.
Programmteil \textcolor{red}A habe im unoptimierten Zustand einen Anteil von $75\%$ an der Gesamtlaufzeit des Programms, wohingegen \textcolor{blue}B nur f"ur die "ubrigen $25\%$ verantwortlich ist.
Nun mag es mit einem vertretbaren Aufwand m"oglich sein, h"ochstens einen der beiden Abschnitte zu verbessern.
Insbesondere sei f"ur den ersten Abschnitt nur ein Verfahren bekannt, welches die Ausf"uhrungszeit lediglich halbiert.
F"ur den zweiten Abschnitt existiere hingegen eine M"oglichkeit, die Ausf"uhrung auf das Zehnfache zu beschleunigen.

Obwohl der Abschnitt \textcolor{blue}B viel besser optimiert werden kann, sieht man schnell, dass eine Optimierung von \textcolor{red}A einen viel gr"o"seren Geschwindigkeitsvorteil bringt:
    \begin{center}
    \begin{tabular}{lll}
    \seqlabel{$A$}{$B$}            & \seqbar{6.0}{2.0} \\
    \seqlabel{$A$}{$\frac{B}{10}$} & \seqbar{6.0}{0.2} \\
    \seqlabel{$\frac{A}{2}$}{$B$}  & \seqbar{3.0}{2.0}
    \end{tabular}
    \end{center}
Dies l"asst sich auch rechnerisch nachvollziehen:
\begin{enumerate}
\item Optimierung von Teil \textcolor{red}A:

In diesem Fall gilt $P=\frac34$ und $N=2$, womit sich eine Beschleunigung des gesamten Programmablaufs ergibt von:

\[\frac{1}{(1-\frac34) + \frac{\frac34}{2}}=\frac{1}{\frac14 + \frac{3}{8}}=\frac{1}{\frac{5}{8}}=\frac85=1.6\]

\item Optimierung von Teil \textcolor{blue}B:

Hier haben wir $P=\frac14$ und $N=10$.
Der erwartete Zeitgewinn liegt in diesem Fall jedoch nur bei

\[\frac{1}{(1-\frac14) + \frac{\frac14}{10}}=\frac{1}{\frac34 + \frac{1}{40}}=\frac{1}{\frac{31}{40}}=\frac{40}{31}<1.3\]

was viel kleiner ist als der Zeitgewinn im ersten Fall.
\end{enumerate}





\subsection{Gesetz des abnehmenden Gewinns}
Eine weitere Folgerung aus dem Amdahlschen Gesetz ist die Tatsache, dass die Hinzunahme eines weiteren Prozessors nur noch einen sehr geringen Geschwindigkeitsvorteil bringt, wenn bereits eine gro"se Anzahl an Prozessoren verwendet wird.
Selbst eine \emph{Verdoppelung} der Prozessorenanzahl $N$ hilft f"ur gro"se Werte von $N$ nur noch sehr wenig.

In der folgenden Graphik ist der erwartete Geschwindigkeitsgewinn bei einem parallelisierbaren Anteil von $95\%$ und einer Verdoppelung der Prozessorenanzahl von $N$ auf $2N$ dargestellt.
    \begin{center}
    \begin{tikzpicture}[domain=0:12,xscale=0.8,yscale=6,>=latex]
    \draw[very thin,color=gray,ystep=.1] (0,1) grid (12.1,2.01);
    \foreach \P in {95}
        \draw[color=blue]
            plot[id=abgew-\P]
            function{((1-\P*.01)+\P*.01/(2**x))/((1-\P*.01)+\P*0.01/(2**(x+1)))}
            +(0,0.2) node[right] {$P = \P\%$};
    \draw[->] (0,1) -- (13,1) node[right] {$N$};
    \draw[->] (0,1) -- (0,2.2) node[above] {Zeitgewinn};
    \foreach \x/\N in {0/1,1/2,3/8,5/32,8/256,12/4096}
        \draw (\x,1.02) -- (\x,0.98) node[below] {\N};
    \foreach \y/\Z in {1.0/{1,0},1.2/{1,2},1.4/{1,4},1.6/{1,6},1.8/{1,8},2.0/{2,0}}
        \draw (0.1,\y) -- (-0.1,\y) node[left] {\Z};
    \end{tikzpicture}
    \end{center}





\subsection{H"ochster vertretbarer Aufwand}
Wenn bei einer ausreichend gro"sen Prozessorenanzahl eine weitere Verdoppelung der Prozessorenanzahl keinen gro"sen Zeitgewinn mehr erhoffen l"asst, so stellt sich die Frage, ab welcher Prozessorenanzahl dieser Effekt eintritt.
Selbstverst"andlich h"angt diese Grenze von der Gr"o"se des parallelisierbaren Anteils des Programms ab.

Wenn man eine Leistungssteigerung um mindestens $5\%$ als lohnend ansieht, so erkennt man, dass ab etwa $1000$ Prozessoren nahezu das gesamte Programm parallelisierbar sein m"usste, damit eine Verdoppelung von $N$ noch einen lohnenenden Geschwindigkeitszuwachs verursacht:
    \begin{center}
    \begin{tikzpicture}[domain=0:12,xscale=0.8,yscale=6,>=latex]
    \draw[very thin,color=gray,ystep=.1] (0,0) grid (12.1,1.01);
    \foreach \f in {5}
        \draw[color=blue]
            plot[id=vertretbar-\f]
            function{1/(1+(1+1/(\f*.01))/(2**(x+1)))}
            +(0,0.2) node[right] {};
    \draw[->] (0,0) -- (13,0) node[right] {$N$};
    \draw[->] (0,0) -- (0,1.2) node[above] {$P_{min}$};
    \foreach \x/\N in {1/2,3/8,5/32,8/256,12/4096}
        \draw (\x,0.02) -- (\x,-0.02) node[below] {\N};
    \foreach \y/\P in {0.0/{0},0.2/{20},0.4/{40},0.6/{60},0.8/{80},1.0/{100}}
        \draw (0.1,\y) -- (-0.1,\y) node[left] {\P\%};
    \end{tikzpicture}
    \end{center}







\section{Das Gustafsonsche Gesetz}
\label{gustafson}

Das Gustafsonsche Gesetz \cite{Gustafson}
entstand als
Gegenstück zum Amdahlschen Gesetz.
Es zeigt,
dass sich massive Parallelisierung
eben doch lohnt!
Zwar können wir nicht beliebig schneller werden,
aber in gleicher Zeit beliebig große Probleme lösen.
Gustafson widerspricht damit Amdahl in keiner Weise,
sondern zeigt lediglich einen Aspekt auf,
den Amdahl übersehen hat.

Leider formulierte Gustafson sein Gesetz
unzulässigerweise als "`Zeitgewinn"'.
So provozierte er Missverständnisse,
die bis hin zu einem vermeintlichen Widerspruch
zum Amdahlschen Gesetz reichten.

Um möglichst viel Klarheit zu schaffen,
werden wir Schritt für Schritt
die einzelnen Gedanken von Gustafson nachvollziehen.
Dabei werden wir all seine guten Ideen zusammentragen
und in nützliche Formeln gießen.
Erst zum Schluss unternehmen wir den fatalen Schritt,
daraus einen fiktiven Zeitgewinn abzuleiten,
und landen beim Gustafsonschen Gesetz.


\subsection{Einbeziehung der Problemgröße (nach Gustafson)}

Die wichtigste Idee von Gustafson ist die
Einbeziehung der \emph{Problemgröße} in das Modell.
Genauer gesagt
geht es um die Eingangsdaten,
deren Größe wir mit $K$ bezeichnen wollen.
Das ursprüngliche Problem habe die Größe $K=1$.

Die Laufzeit des Programms
bei Problemgröße $K=1$
auf einer 1-Prozessor-Maschine
normieren wir wieder auf $1$.
Der parallelisiere Programmteil
habe bei Problemgröße $K=1$
einen Anteil von $P'$ an der Laufzeit.

Wie ändert sich die Laufzeit,
wenn wir die Problemgröße erhöhen?
Gustafson argumentiert,
dass normalerweise nur
der parallelisierbare Programmteil
mehr zu tun bekommt.
Denn dieser besteht
typischerweise aus vielen Vektor-Operationen,
deren Dimension sich direkt aus der
Größe der Eingabedaten ergibt.
Der sequenzielle Programmteil hingegen
besteht überwiegend aus Initialisierungs-Schritten,
die unabhängig von der Problemgröße sind.
Dies führt zu folgender Laufzeit:
    \begin{align*}
    \underbrace{(1-P')}_{\text{sequenziell}}
    \quad + \quad
    \underbrace{K \cdot P'}_{\text{parallel}}
    \end{align*}
Wie beim Amdahlschen Gesetz
stellen wir uns nun die Frage,
wieviel schneller das Programm
auf einem $N$-Prozessor-System läuft.
Dort arbeitet
der sequenzielle Programmteil unverändert,
während
der parallelisierbare Programmteil
$N$-mal so schnell wird.
Als neue Laufzeit ergibt sich:
    \begin{align*}
    \underbrace{(1-P')}_{\text{sequenziell}}
    \quad + \quad
    \underbrace{\frac{K \cdot P'}{N}}_{\text{parallel}}
    \end{align*}
Der Zeitgewinn lautet entsprechend:
    \begin{align*}
    \text{Zeitgewinn} &= \frac{(1-P') + K \cdot P'}
                              {(1-P') + \frac{K \cdot P'}{N}}
    \end{align*}
Wir haben somit den Zeitgewinn
in Abhängigkeit von der Problemgröße
ermittelt.
Diese Formel wurde von Gustafson
leider nicht herausgearbeitet,
entspricht aber genau seinem Modell.

Das Amdahlsche Gesetz finden wir
in dieser Formel
als Spezialfall $K=1$
wieder.
Umgekehrt können wir
auch die neue Formel
aus dem Amdahlschen Gesetz herleiten.
Dazu müssen wir für lediglich für $P$
den parallelisierbaren Anteil
bei Problemgröße $K$ einsetzen:
    \begin{align*}
    P &= \frac{\text{parallelisierbarer Teil der Laufzeit}}{\text{gesamte Laufzeit}}
       = \frac{K \cdot P'}{(1-P') + K \cdot P'}
    \end{align*}
Es ergibt sich:
    \begin{align*}
    \text{Zeitgewinn}
        &= \frac{1}{(1-P) + \frac{P}{N}}
         = \frac{1}
                {\left(1 - \frac{K \cdot P'}{(1-P') + K \cdot P'}\right)
                 + \frac{\frac{K \cdot P'}{(1-P') + K \cdot P'}}{N}}
    \\
        &= \frac{(1-P') + K \cdot P'}
                {\Big((1-P') + K \cdot P' - K \cdot P'\Big)
                 + \frac{K \cdot P'}{N}}
         = \frac{(1-P') + K \cdot P'}
                {(1-P')
                 + \frac{K \cdot P'}{N}}
    \end{align*}
Wir erhalten die selbe Formel.


\subsection{Gustafsonsches Gesetz -- Gute Idee \ldots}

Die zweite gute Idee,
die Gustafson einbringt,
ist folgende:
Wenn wir bessere Rechentechnik erhalten,
freuen wir uns,
dass unsere alten Programme schneller laufen.
Doch ihre Laufzeit war
gar nicht so schlecht.
Sie war vielleicht hart an der Grenze,
aber immer noch in Ordnung.
Also lassen wir auf dem neuen System
immer größere Probleme rechnen,
bis wir wieder die Grenze stoßen,
an die ursprüngliche Laufzeit.
Gustafson hat es so formuliert:
    \begin{quote}
    "`Hence, it may be most realistic to assume that
      run time, not problem size, is constant."'
    \end{quote}
Die Frage ist also,
welche Problemgröße wir
in der ursprünglichen Laufzeit $1$
auf einem $N$-Prozessor-System handhaben können:
    \begin{align*}
    \text{Laufzeit}               &= 1  \\
    (1-P') + \frac{K \cdot P'}{N} &= 1  \\
    \frac{K \cdot P'}{N}          &= P' \\
    K                             &= N
    \end{align*}
Ein erstaunliches Ergebnis!
Unserem Modell zufolge
können wir stets
die $N$-fache Problemgröße
berechnen,
unabhängig vom parallelisierbaren Anteil $P'$.


\subsection{\ldots\ aber schlechte Umsetzung}

Schauen wir uns die bisherigen Erkenntnisse noch einmal an:
    \begin{align*}
    \text{Zeitgewinn} &= \frac{1}{(1-P) + \frac{P}{N}}  && \text{bei Problemgröße $1$} \\
    K                 &= N                              && \text{bei Laufzeit $1$}
    \end{align*}
Mit diesen Formeln ist eigentlich alles gesagt:
Durch Parallelisierung
erhalten wir zwar nur einen begrenzten Zeitgewinn,
aber einen beliebig hohen Kapazitätsgewinn.
Also lohnt sich massive Parallelisierung doch!

Leider hat es Gustafson nicht
bei der einfachen Formel
$K=N$
belassen.
Stattdessen
stellt er Überlegungen an,
welche Zeit das neue, größere Problem
auf einer 1-Prozessor-Maschine benötigt hätte.
Der daraus resultierende, fiktive Zeitgewinn lautet dann:
    \begin{align*}
    \text{Zeitgewinn} &= \frac{(1-P') + K \cdot P'}
                              {(1-P') + \frac{K \cdot P'}{N}}   & \text{$K=N$ einsetzen} \\
                      &= \frac{(1-P') + N \cdot P'}
                              {(1-P') + \frac{N \cdot P'}{N}}                            \\
                      &= \frac{(1-P') + N \cdot P'}
                              {(1-P') + P'}                                              \\
                      &= \frac{(1-P') + N \cdot P'}
                              {1}
    \end{align*}
Im Nenner steht die ursprüngliche Laufzeit, die sich wie erwartet auf $1$ zusammenkürzt.
Damit ergibt sich das Gustafsonsche Gesetz:
    \begin{align*}
    \text{Zeitgewinn} &= (1-P') + N \cdot P'
    \end{align*}
Die Absurdität tritt deutlich zutage,
wenn man bedenkt,
dass dieser "`Zeitgewinn"'
letztlich auf der Annahme basiert,
dass die Laufzeit konstant gehalten wird.

Stellen wir uns folgendes Sonderangebot im Supermarkt vor:
"`Zwei~Stück zum Preis von einem!"'
Kaufen wir nun zwei~Stück statt einem,
hätten wir nach Gustafsons Argumentation 50\% Geld gespart.
Aber wir haben genauviel Geld ausgegeben wie sonst auch!
Wir haben überhaupt kein Geld gespart,
sondern 1~Stück extra erhalten.
Wir haben einen materiellen Gewinn,
aber keinen finanziellen!

Genauso ist der von Gustafson formulierte
"`Zeitgewinn"' unzulässig.
Dieser völlig unnötige Schritt
in Gustafsons Arbeit~\cite{Gustafson}
sorgte für viel Verwirrung.





\section{Widerlegungen}

Seit der Formulierung
des Amdahlschen Gesetzes
gab es viele Hinweise darauf,
dass es widerlegt worden sei.
In diesem Kapitel untersuchen wir,
was an diesen Hinweisen dran ist.

\subsection{Widerspruch zwischen den Gesetzen?}
Scheinbar gibt es einen grundlegenden Widerspruch zwischen dem Amdahlschen und dem Gustafsonschen Gesetz:

Das Amdahlsche Gesetz besagt, dass sich schon ab einer recht geringen Prozessorenanzahl kein weiter Geschwindigkeitsgewinn mehr erwarten l"asst, wohingegen das Gustafsonsche Gesetz von einem nahezu linearen Geschwindigkeitsgewinn spricht.
Die Ursache dieses scheinbaren Widerspruchs ist jedoch lediglich, dass bei dem Amdahlschen Gesetz die Problemgr"o"se und vor allem auch die Gr"o"se des parallelisierbaren Anteils konstant sind.

Gustafson geht jedoch von einem mit wachsender Problemgr"o"se verschwindend geringem sequentiellen Anteil aus.
Damit kann dann in der gleichen Zeit ein linear mit der Anzahl der Prozessoren wachsendes Problem l"osen.
Bei dem Gustafsonschen Gesetz wird dann das Verh"altnis aus der theoretischen Laufzeit dieses (gr"o"seren) Problems auf einem Prozessor und der Laufzeit auf $N\gg1$ Prozessoren gebildet.
Es wird hier also nur ein vollkommen anderer Aspekt betrachtet.

Amdahl sagt letztendlich,
dass sich massive Parallelisierung nicht lohnt,  % TODO: sagt er das wirklich?
weil sich unsere bisherigen Programme
nur bis zu einer bestimmten Grenze beschleunigen lassen.
Gustafson erwidert,
dass sich Parallelisierung dennoch lohnt,
weil wir dadurch größere Probleme berechnen können.

Parallelisierung bringt zwar
\emph{wenig Zeitgewinn},
aber einen
\emph{großen Kapazitätsgewinn}.



\subsection{Algorithmen "andern sich durch Parallelisierung}
In den vergangenen Jahren hat sich gezeigt, dass bei der Parallelisierung einiger Programme Geschwindigkeitsgewinne erreicht wurden, welche dem Amdahlschen Gesetz zu widersprechen scheinen.

Ein Grund f"ur diesen unerwarteten Zeitgewinn liegt darin, dass ein sequentieller Algorithmus nicht ohne weiteres auf mehrere Prozessoren aufgeteilt werden kann.
Meist ist hierf"ur eine Anpassung n"otig, die unter Umst"anden zu einer grundlegenden "Anderung des Algorithmus' f"uhren kann.
Dabei ist es dann auch m"oglich, dass sich sogar die Komplexit"atsklasse des Algorithmus "andert, was dann den beobachteten Effekt erkl"art.

\bigskip

Betrachten wir hierzu beispielsweise den folgenden Algorithmus:

Der Algorithmus erh"alt eine sortierte Liste $x_1, ..., x_n$ paarweise verschiedener Elemente als Eingabe und soll in ihr ein bestimmtes Element $x$ finden bzw. ``nicht gefunden'' ausgeben, wenn das Element nicht enthalten ist.

Im Groben f"uhrt der Algorithmus einfach eine lineare Suche auf der gesamten Liste aus, um das gesuchte Element zu finden.
Das die Liste sortiert ist, wird dabei nicht beachtet.

Lediglich vor dem Start der linearen Suche f"uhrt der Algorithmus einen Randtest aus, d.h. er "uberpr"uft, ob das gesuchte Element mindestens so gro"s wie das erste und h"ochstens so gro"s wie das letzte Element der Liste ist.
Damit l"asst sich unter Umst"anden sehr schnell feststellen, dass das gesuchte Element nicht in der Liste enthalten sein kann.
(Dies ist der Fall, wenn $x<x_1$ oder $x>x_n$ gilt.)

Wenn das gesuchte Element wirklich in der Liste enthalten ist, bringt dieser Randtest keinen Vorteil.
Damit ist bei einem Prozessor die Laufzeit $O(n)$.

\bigskip

Nun parallelisieren wir den Algorithmus wie folgt:

Wenn noch $N>1$ freie Prozessoren zur Verf"ugung stehen, so wird die Liste in $N$ gleichgro"se St"ucke zerlegt und jedem dieser $N$ Prozessoren wird eines dieser St"ucke zur Bearbeitung "ubergeben.
Nehmen wir einmal an, dass wir nur $2$ Prozessoren haben.
Dann wird die Liste zu Beginn in zwei Teillisten zerlegt.

Durch den anf"anglichen Randtest wird einer der Prozessoren sofort feststellen, dass seine Teilliste das gesuchte Element nicht enthalten kann.
Also kann er die Bearbeitung seines Teilproblems sofort beenden.
Damit stehen f"ur den zweiten Teil der Liste wieder zwei Prozessoren zur Verf"ugung, womit sie erneut geteilt werden kann.

Durch Iteration dieses Verfahrens entartet die anf"angliche lineare Suche bei einem Prozessor zu einer Bin"arsuche, sobald man $2$ Prozessoren zur Verf"ugung hat.
Damit reduziert sich auch die Komplexit"at auf $O(\log n)$.

\subsection{Wirkliche Widerlegung}
\label{wirkliche-widerlegung}
Ein weiterer Grund f"ur den Geschwindigkeitszuwachs liegt in der Hardware.

Die vereinfachenden Grundannahmen des Amdahlschen Gesetzes ignorieren zum Beispiel, dass mit einer Erh"ohung der Prozessorenanzahl meistens auch eine Vergr"o"serung des zur Verf"ugung stehendes Hauptspeichers und Caches einher geht.
Insbesondere kann es zu dem Effekt kommen, dass ein gro"ses Problem, welches unter Verwendung eines einzigen Prozessors vielleicht nicht einmal in den Speicher passte, nach der Parallelisierung in so viele Teilprobleme zerlegt wurde, dass diese zumindest zu einem gro"sen Teil (wenn nicht sogar ganz) im Cache gehalten werden k"onnen.
Damit ist dann nat"urlich eine viel h"ohere Verarbeitungsgeschwindigkeit der Teilprobleme und somit auch des gesamten Problems m"oglich.

\newpage
\bibliography{Literatur}
\bibliographystyle{geralpha}

\end{document}
