\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 $xx_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}