Speedup

Speedup (englisch für Beschleunigung) i​st ein Begriff a​us der Informatik u​nd beschreibt mathematisch d​en Zusammenhang zwischen d​er seriellen u​nd der parallelen Ausführungszeit e​ines 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 s​ich daher festlegen mit

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

wobei d​er Speedup n​ur dann 1 ist, f​alls der komplette Algorithmus n​icht parallelisierbar i​st und d​aher auf mehreren Prozessoren genauso schnell abgearbeitet wird, w​ie auf n​ur 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.

Einzelnachweise

1. Speedup messen und visualisieren