Solution
1. Check out the formula for speedup according to Gustafson’s law and briefly describe its parameters.
Gustafson’s law:
where the speedup depends on
- , the not parallelisable part of the computational work
- , the parallelisable part
- , the number of processors
- , the non-parallelisable fraction of the work
The whole work is the the work that can be executed by one processor in time.
2. Assume that 20 percent of the code of an algorithm cannot be parallelized. What is the maximally achievable speedup according to Amdahl’s law?
Amdahl’s law (with ):
The maximal achievable speedup is .
3. Imagine you have a processor providing 47 cores. Assume 94 percent of a program can be parallelized and there is no additional overhead when running this program on all cores. By using Amdahl’s law, what is the parallel speedup maximally achievable?
with :
The maximal achievable speedup is .