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.

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

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

definiert werden. Dabei stellen ${\displaystyle T_{1}}$ und ${\displaystyle 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

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

dargestellt werden. Dabei gilt:

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

Im Idealfall gilt

${\displaystyle S_{p}=p}$

sodass die Ausführungszeit auf ${\displaystyle p}$ Prozessoren genau ${\displaystyle 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

${\displaystyle 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.

• Amdahlsches Gesetz
• Parallelrechner
• Speedup beim Pipelining
• Speedup-Theorem in der Komplexitätstheorie
• Speedup messen und visualisieren^[1]

• Rahm, Erhard. Mehrrechner-Datenbanksysteme - Grundlagen der verteilten und parallelen Datenbankverarbeitung (Speedup und Scaleup). Leipzig: 1994.

1. ↑ Speedup messen und visualisieren