Scalability (from CUDA Best Practices)

Question 1

What is Amdahl’s Law?

Answer 1

Amdahl’s Law gives the maximum speedup S of a program for a fixed problem size as a function of P, the proportion of serial runtime taken up by code that can be parallelized, and N, the number of processors.

S = 1 / [(1 - P) + P/N]

Question 2

What’s the easy way to think about Amdahl’s Law?

Answer 2

Let the number of processors N -> inf, so the equation goes from…

S = 1 / [(1 - P) + P/N]

to…

S = 1 / (1 - P)

For P = 0 we get S = 1 (same as without the limit) and for P = 1 we get an infinite speedup (this is where it’s different than the original). This is what happens when we assume we can do as much as we want in parallel.

Question 3

What is Strong Scaling?

Answer 3

Strong Scaling is a measure, for a fixed problem size, of how the runtime of a program decreases as the number of processors increases.

Another way to think of it:
- The total problem size stays fixed as more processors are added
- Goal is to run the same problem size faster
- Perfect strong scaling means that the runtime decreases linearly with slope 1/N as the number of processors N increases

Question 4

What does it mean for a program to exhibit linear strong scaling?

Answer 4

Speedup equals the number of processors, i.e., increases linearly with the number of processors

Question 5

What law is associated with Strong Scaling?

Answer 5

Amdahl’s Law

Question 6

What scaling measure is associated with Amdahl’s Law?

Answer 6

Strong Scaling

Question 7

What is Gustafson’s Law?

Answer 7

The problem size scales with the number of processors. i.e., the maximum speedup S of a program is:

S = N + (1 - P)(1 - N)

Where P is the proportion of serial runtime that can be parallelized (like Amdahl’s!) and N is the number of processors.

Basically S = N but with a penalty weighted by the non-parallel proportion of serial runtime.

Assumes that the runtime remains constant instead of the problem size! (We still get speedup because as the problem size increases, so does the serial runtime we’re comparing our parallel runtime to). Another way to think about this is that Gustafson’s Law assumes a constant fraction of serial to parallel runtime.

Question 8

What is Weak Scaling?

Answer 8

A measure of how runtime changes for a problem of fixed size PER PROCESSOR as you increase the number of processors.

Another way to think of it:
- The problem size per processor stays fixed as more processors are added. The total problem size is proportional to the number of processors used.
- Goal is to run larger problem in same amount of time
- With perfect weak scaling, the runtime remains the same as the problem size (and corresponding number of processors) grows

Question 9

What law is associated with Weak Scaling?

Answer 9

Gustafson’s Law

Question 10

What scaling measure is associated with Gustafson’s Law?

Answer 10

Weak Scaling