Speedup

Speedup ( English for acceleration is) a term from the computer science and mathematically describes the relationship between the serial and the parallel execution time of a program part.

definition

The speedup of parallel processed operations with different properties on up to 16 CPUs

The speedup is defined by the following two formulas:

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

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

where:

• ${\displaystyle p}$ is the number of processors
• ${\displaystyle S_{p}}$is the theoretical speedup that can be achieved when executing the algorithm on processors ${\displaystyle p}$
• ${\displaystyle T_{1}}$ is the execution time on a single processor system
• ${\displaystyle T_{p}}$ is the execution time on a multiprocessor system
• ${\displaystyle f}$(engl. fraction ) is the part of which can be executed in parallel ${\displaystyle T_{1}}$

Range of values

Ideally

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

so that the execution time on processors is exactly times as fast as on just one processor. However, since an algorithm can never be executed completely 100% in parallel , because there is always a sequential, non-parallelizable part, the ideal case can never be achieved (see Amdahl's law ) . ${\displaystyle p}$ ${\displaystyle p}$

The range of values ​​can therefore be set with

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

The speedup is only 1 if the complete algorithm cannot be parallelized and is therefore processed just as quickly on several processors as on just one processor.

See also

• Amdahl's law
• Parallel computer
• Pipelining speed up
• Speedup theorem in complexity theory
• Measure and visualize speedup

literature

• Rahm, Erhard. Multi-computer database systems - basics of distributed and parallel database processing ( speedup and scaleup ). Leipzig: 1994.

Individual evidence

1. ↑ Measure and visualize Speedup