speedup

Speedup is a way to quantify the advantage of using a parallel algorithm over a sequential algorithm. The speedup $S$ is defined as

$$S=\frac{R}{P}$$

Where $R$ is the running time of the best available sequential algorithm and $P$ is the running time of the parallel algorithm.

Ideally, on a system with $N$ processors, the speedup for any algorithm would be $N$. Amdahl’s law deals with the speedup in more realistic situations.

Title	speedup
Canonical name	Speedup
Date of creation	2013-03-22 12:04:12
Last modified on	2013-03-22 12:04:12
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	6
Author	akrowne (2)
Entry type	Definition
Classification	msc 68W40
Classification	msc 68W10