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 parallel bearbeiteter Operationen mit unterschiedlichen Eigenschaften auf bis zu 16 CPUs

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

Wertebereich

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.

Siehe auch

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

Literatur

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