Speedup

In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is defined by the following formula:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

S_p = rac{T_1}{T_p}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• p is the number of processors
• $T\_1$ is the execution time of the sequential algorithm
• $T\_p$ is the execution time of the parallel algorithm with p processors

Linear speedup or ideal speedup is obtained when ,S_p = p. When running an algorithm with linear speedup, doubling the number of processors doubles the speed, which is usually considered very good scalability.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Efficiency is a performance metric defined as Sp/p. It is a value, typically between zero and one, estimating how well-utilized the processors are in solving the problem, compared to how much effort is wasted in communication and synchronization. Algorithms with linear speedup and algorithms running on a single processor have an efficiency of 1, while many difficult-to-parallelize algorithms have efficiency such as 1/log p that approaches zero as the number of processors increases.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Speedup: See also ►



 

Parallel computing: Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain faster results....

Parallel algorithm: In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result....

Algorithm: In mathematics and computer science an algorithm (the word is derived from the name of the Persian mathematician Al-Khwarizmi) is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state (contrast wi...