You are here:   ArielOrtiz.com > Programming Languages > Parallelism and Performance

Parallelism and Performance

Speedup

The speed of a program is the time it takes the program to execute. This could be measured in any increment of time. Speedup is defined as the time it takes a program to execute sequentially (with one processor) divided by the time it takes to execute in parallel (with many processors). The formula for speedup is:

Sp = T1 / Tp

Where:

Sp
The speedup obtained from using p processors.
T1
The time it takes the program to be executed sequentially.
Tp
The time it takes the program to be executed in parallel using p processors.

Linear Speedup

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

Amdahl's Law

Amdahl's law states that the speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program.

As a formula:

Sp = 1 / (F + (1 - F) / p)

Where:

p
The number of processors.
Sp
The speedup obtained from using p processors.
F
The fraction of the program that must be executed sequentially. 0 ≤ F ≤ 1.

If p tends to ∞, the maximum speedup tends to 1 / F.

Reference:

Shameem Akhert and Jason Roberts.
Multi-Core Programming: Increasing Performance Through Software Multi-Threading.
Intel Press, 2006.
ISBN: 0976483246.
pp. 13-15.

© 1996-2010 by Ariel Ortiz (ariel.ortiz@itesm.mx)
Made with Django | Licensed under Creative Commons | Valid XHTML | Valid CSS