Speedup
Speedup ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=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 <math>S_p</math> einer parallelen Ausführung kann anhand der Gleichung
- <math>S_p = \frac{T_1}{T_p}</math>
definiert werden. Dabei stellen <math>T_1</math> und <math>T_p</math> 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
- <math>S_p = \frac{T_1}{T_1 \left ( \left (1 - f \right )+\frac{f}{p} \right )} </math>
dargestellt werden. Dabei gilt:
- <math>p</math> ist die Anzahl von Prozessoren
- <math>S_p</math> ist der theoretische Speedup, der erreicht werden kann bei Ausführung des Algorithmus auf <math>p</math> Prozessoren
- <math>T_1</math> ist die Ausführungszeit auf einem Ein-Prozessor-System
- <math>T_p</math> ist die Ausführungszeit auf einem Mehrprozessorsystem
- <math>f</math> (engl. {{#invoke:Vorlage:lang|flat}}) ist der Anteil von <math>T_1</math>, welcher parallel ausgeführt werden kann
Wertebereich
Im Idealfall gilt
- <math>S_p = p</math>
sodass die Ausführungszeit auf <math>p</math> Prozessoren genau <math>p</math>-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
- <math>1 \le S_p \le p</math>
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<ref>Speedup messen und visualisieren</ref>
Literatur
- Rahm, Erhard. Mehrrechner-Datenbanksysteme - Grundlagen der verteilten und parallelen Datenbankverarbeitung (Speedup und Scaleup). Leipzig: 1994.
Einzelnachweise
<references />