Speedup
# Speedup

Speedup (englisch für Beschleunigung) ist ein Begriff aus der Informatik und beschreibt mathematisch den Zusammenhang zwischen der seriellen und der parallelen Ausführungszeit eines Programmteils.

## Definition

Der Speedup $S_{p}$ einer parallelen Ausführung kann anhand der Gleichung

    $S_{p}={\frac {T_{1}}{T_{p}}}$

definiert werden. Dabei stellen $T_{1}$ und $T_{p}$ die serielle sowie parallele Ausführungszeit dar. Die obige Gleichung wird für eine Messung des realen Speedups herangezogen. Wird der theoretische Wert betrachtet, so kann dieser mittels dem Ausdruck

    $S_{p}={\frac {T_{1}}{T_{1}\left(\left(1-f\right)+{\frac {f}{p}}\right)}}$

dargestellt werden. Dabei gilt:

* $p$ ist die Anzahl von Prozessoren
* $S_{p}$ ist der theoretische Speedup, der erreicht werden kann bei Ausführung des Algorithmus auf $p$ Prozessoren
* $T_{1}$ ist die Ausführungszeit auf einem Ein-Prozessor-System
* $T_{p}$ ist die Ausführungszeit auf einem Mehrprozessorsystem
* $f$ (engl. fraction) ist der Anteil von $T_{1}$, welcher parallel ausgeführt werden kann

## Wertebereich

Im Idealfall gilt

    $S_{p}=p$

sodass die Ausführungszeit auf $p$ Prozessoren genau $p$-mal so schnell ist, als auf nur einem Prozessor. Da jedoch ein Algorithmus nie komplett zu 100 % parallel ausgeführt werden kann, weil es immer einen sequenziellen nicht parallelisierbaren Anteil gibt, ist der Idealfall nie erreichbar (siehe Amdahlsches Gesetz).

Der Wertebereich lässt sich daher festlegen mit

    $1\leq S_{p}\leq p$

wobei der Speedup nur dann 1 ist, falls der komplette Algorithmus nicht parallelisierbar ist und daher auf mehreren Prozessoren genauso schnell abgearbeitet wird, wie auf nur einem Prozessor.

