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.

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

S p = T 1 T p {\displaystyle S_{p}={\frac {T_{1}}{T_{p}}}}

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

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

dargestellt werden. Dabei gilt:

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

Im Idealfall gilt

S p = p {\displaystyle S_{p}=p}

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

1 ≤ S p ≤ p {\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