37 lines
2.1 KiB
TeX
37 lines
2.1 KiB
TeX
% !TeX spellcheck = de_DE
|
|
\subsection{Leistungsanalyse}
|
|
\begin{itemize}
|
|
\item allgemeiner \begriff{Speed-up}:
|
|
\begin{equation*}
|
|
\text{Speedup} = \frac{\text{sequentielle Ausführungszeit}}{\text{parallele Ausführungszeit}}
|
|
\end{equation*}
|
|
\item Zeit für inhärent sequentielle Berechnungen $\sigma(n)$
|
|
\item Zeit für potentiell parallele Berechnungen $\varphi(n)$
|
|
\item Zeit für Kommunikation $\kappa(n,p)$
|
|
\item Speed-up $\psi$ bei Problemgröße $n$ auf $p$ Prozessoren
|
|
\begin{equation*}
|
|
\psi(n, p) \leq \frac{\sigma(n) + \varphi(n)}{\sigma(n) + \frac{\varphi(n)}{p} + \kappa(n,p)}
|
|
\end{equation*}
|
|
\item ab bestimmten Punkt ist Kommunikationsaufwand größer als Ersparnis durch weitere Parallelisierung $\rightarrow$ \enquote{Ellbogeneffekt} bei Plot Speed-up gegen $p$
|
|
\item Effizienz $0 \leq \varepsilon \leq 1$:
|
|
\begin{align*}
|
|
\text{Effizienz} &= \frac{\text{Speed-up}}{\text{Prozessoren}}\\
|
|
\varepsilon(n,p) &\leq \frac{\sigma(n) + \varphi(n)}{p \cdot \sigma(n) + \varphi(n) + p \cdot \kappa(n,p)}
|
|
\end{align*}
|
|
\item \begriff{Amdahl'sches Gesetz} mit $f = \frac{\sigma(n)}{\sigma(n) + \varphi(n)}$ als sequentieller Anteil der Programmausführung (unter Vernachlässigung der Kommunikationskosten):
|
|
\begin{equation*}
|
|
\psi(n,p) \leq \frac{1}{f + \frac{1 - f}{p}}
|
|
\end{equation*}
|
|
\item Amdahl-Effekt: für große $n$ nimmt Speed-up erst spät ab
|
|
\item Gesetz von Gustafson-Barsis nimmt Zeit als Konstante an und skaliert Problemgröße mit Zahl der Prozessoren:\begin{itemize}
|
|
\item serieller Anteil eines parallelen Programms $s = \frac{\sigma(n)}{\sigma(n)+ \frac{\varphi(n)}{p}}$
|
|
\item skalierter Speedup (unter der Annahme, dass paralleles Programm insgesamt 1 Zeiteinheit braucht):
|
|
\begin{equation*}
|
|
\varphi = p + \left(1 - p\right)\cdot s
|
|
\end{equation*}
|
|
\end{itemize}
|
|
\item \begriff{Karp-Flatt-Maß} berücksichtigt Kommunikation durch experimentelle Bestimmung des seriellen Anteils $e$ eines parallelen Programms
|
|
\begin{equation*}
|
|
e =\frac{\sigma(n) + \kappa(n,p)}{\sigma(n) + \varphi(n)} = \frac{\frac{1}{\varphi} - \frac{1}{p}}{1 - \frac{1}{p}}
|
|
\end{equation*}
|
|
\end{itemize} |