\documentclass{beamer}

\mode<presentation>{
    \usetheme{Singapore}
    \setbeamercovered{transparent}
}

\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{tikz}

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

\AtBeginSection[]
{
    \begin{frame}
        \frametitle{Übersicht}
        \tableofcontents[currentsection]
    \end{frame}
}

%\AtBeginSubsection[]
%{
%    \begin{frame}
%        \frametitle{Übersicht}
%        \tableofcontents[currentsection,currentsubsection]
%    \end{frame}
%}

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

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

\begin{frame}
    \frametitle{Übersicht}
    \tableofcontents
\end{frame}

\section{Amdahlsches Gesetz}

\begin{frame}
    \frametitle{Amdahlsches Gesetz}

    \begin{tabular}{rl}
    $N$ & Anzahl der Prozessoren \\
    $P$ & Anteil des parallelisierbaren Programmcodes (an Laufzeit) \\
    \pause
    $(1-P)$ & Anteil des sequenziellen Programmcodes
    \end{tabular}
    \pause
    \begin{align*}
    \text{Zeitgewinn} &= \frac{1}{(1-P) + \frac{P}{N}}
    \end{align*}
    \pause
    \begin{itemize}
    \item auch: speedup, Geschwindigkeitsgewinn
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Höchstgeschwindigkeit}

    \begin{tikzpicture}[domain=0:12,xscale=0.4,yscale=0.2,>=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}
    \begin{itemize}
    \pause
    \item $\text{Zeitgewinn} < \frac{1}{(1-P)}$
    \pause
    \item folgt direkt aus Definition von "`sequenzieller Programmcode"'
    \pause
    \item alternativ durch $N \rightarrow \infty$ herleitbar
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Grenzen des Amdahlschen Gesetzes}

    Das Amdahlsche Gesetz ignoriert:

    \bigskip

    \begin{itemize}
    \item wachsende Resourcen
        \begin{itemize}
        \item Prozessor-Cache
        \item RAM
        \end{itemize}
    \pause
    \item Verwaltungsaufwand für Parallelisierung
    \pause
    \item wachsende Problemgröße ($\rightarrow$ Gustafsonsches Gesetz)
    \end{itemize}
\end{frame}

\section{Ausweitungen des Amdahlschen Gesetzes}

\begin{frame}
    \frametitle{Übertragung auf sequenzielle Programme}

    \begin{tabular}{rl}
    $N$ & Geschwindigkeits-Anstieg des optimierten Programmteils \\
    $P$ & ursprünglicher Anteil des optimierten Programmteils \\
    \end{tabular}
    \begin{align*}
    \text{Zeitgewinn} &= \frac{1}{(1-P) + \frac{P}{N}}
    \end{align*}

    \pause
    \bigskip

    \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{frame}

\begin{frame}
    \frametitle{Gesetz des abnehmenden Gewinns}

    \begin{itemize}
    \item Leistungssteigerung bei Verdoppelung von $N$:

    \bigskip

    \begin{tikzpicture}[domain=0:12,xscale=0.4,yscale=3,>=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}

    \pause
    \item Verdoppelung bringt immer weniger
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Höchster vertretbarer Aufwand}

    \begin{itemize}
    \item Erforderlicher $P$-Anteil,
          damit sich Verdoppelung noch lohnt:

    \bigskip

    \begin{tikzpicture}[domain=0:12,xscale=0.4,yscale=3,>=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}

    \item "`Verdoppelung lohnt sich"' = Leistungssteigerung um $\geq 5\%$
    \pause
    \item Verdoppelung lohnt sich schnell nicht mehr
    \end{itemize}
\end{frame}

\section{Gustafsonsches Gesetz}

\begin{frame}
    \frametitle{Einbeziehung der Problemgröße (nach Gustafson)}

    \begin{tabular}{rl}
    $N$  & Anzahl der Prozessoren \\
    $K$  & Problemgröße \\
    $P'$ & Anteil des parallelisierbaren Programmcodes bei $K=1$
    \end{tabular}
    \pause
    \begin{align*}
    \text{Zeitgewinn} &= \frac{(1-P') + K \cdot P'}
                              {\pause (1-P') + \frac{K \cdot P'}{N}}
    \end{align*}

    \pause
    \bigskip

    Herleitbar aus dem Amdahlschen Gesetz:
    \begin{align*}
    P &= \frac{K \cdot P'}{(1-P') + K \cdot P'}
    \end{align*}
\end{frame}

\begin{frame}
    \frametitle{Gustafsonsches Gesetz -- Gute Idee \ldots}

    \begin{itemize}
    \item "`Hence, it may be most realistic to assume that
            run time, not problem size, is constant."'
        \pause
        \begin{align*}
        1 &= (1-P') + \frac{K \cdot P'}{N} \\
        \Rightarrow\quad K &= N
        \end{align*}
    \pause
    \item kein Zeitgewinn, aber Kapazitätsgewinn!
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{\ldots\ aber schlechte Umsetzung}

    \begin{itemize}
    \item Eigentliches Gesetz:
        \begin{align*}
        K &= N
        \end{align*}
    \pause
    \item Kompliziertere Umschreibung:
        \begin{align*}
        \text{Zeitgewinn} &= \frac{(1-P') + K \cdot P'}
                                  {(1-P') + \frac{K \cdot P'}{N}} \\
        \pause
                          &= (1-P') + N \cdot P'
        \end{align*}
    \pause
    \item Kapazitätsgewinn als Zeitgewinn dargestellt
    \pause
    \item "`Sparen Sie Geld! Kaufen Sie 2~Stück zum Preis von einem!"'
    \end{itemize}
\end{frame}

\section{Widerlegungen}

\begin{frame}
    \frametitle{Quellen von Verwirrungen}

    \begin{itemize}
    \item Massive Parallelisierung lohnt sich nicht?
        \begin{itemize}
        \pause
        \item Amdahlsches Gesetz ignoriert Problemgröße
        \item $N \rightarrow \infty$: kein Zeitgewinn, aber Kapazitätsgewinn
        \end{itemize}
    \pause
    \bigskip
    \item Gustafsonsches Gesetz widerspricht Amdahlschem Gesetz?
        \begin{itemize}
        \pause
        \item Gustafsonsches Gesetz spricht auch von Zeitgewinn
        \item lediglich anderer Aspekt betrachtet
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Algorithmen ändern sich durch Parallelisierung}

    \begin{itemize}
    \item Amdahlsches Gesetz empirisch widerlegt?
        \begin{itemize}
        \pause
        \item Einige Algorithmen ändern sich durch Parallelisierung
        \pause
        \item Paralleles und sequenzielles Programm nur vergleichbar, wenn
            \begin{align*}
            \sum_{\text{Prozessoren}} \#\text{Befehle}_{par}
            \quad &\geq \quad
            \#\text{Befehle}_{seq}
            \end{align*}
        \end{itemize}
    \pause
    \item Beispiel
        \begin{itemize}
        \item sortierte Liste
        \item lineare Suche mit Randprüfung
        \pause
        \item Parallelisierung $\rightarrow$ Binärsuche
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Wirkliche Widerlegung}

    \begin{itemize}
    \item Amdahlsches Gesetz dennoch empirisch widerlegt?
        \begin{itemize}
        \pause
        \item Ja, denn es ignoriert die wachsenden Resourcen
        \pause
        \item mehr Prozessoren $\rightarrow$ mehr Cache
        \item Geschwindigkeitszuwachs, wenn Teilprobleme in Cache passen
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Ende}

    \begin{center}
    \textbf{Vielen Dank für die Aufmerksamkeit!}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{URL und Lizenz}

    \begin{itemize}
    \item Veröffentlicht unter \\
        \url{http://www.profv.de/uni/}

    \vfill

    \item 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}
    \end{itemize}
\end{frame}

\end{document}