Question

In computer architecture, Gustafson's law gives the speedup in the execution time of a task that theoretically gains from parallel computing, using a hypothetical run of the task on a single-core machine as the baseline. Gustafson estimated the speedup S of a program gained by using parallel computing as follows:

S=s+p×N=N+(1−N)×s
Where:
S is the theoretical speedup
N is the number of processors
s and p are the fractions of serial and parallel part of the program, and s+p=1.
This law basically states that, hypothetically, when running the program on a serial system (only one processor), the serial part still takes s, while the parallel part now takes Np. The execution time on the serial system is:
T=s+Np
Hence the speedup is:
S=TrT=s+Np
a) Explain how Gustafson's law is making different assumptions compared to the Amdahl's law.
b) Given a program of the serial part 50% and the parallel part of 50%, with 128 processors, what is the theoretical maximum speedup using Gustafson's law?

Answer 1

Gustafson's law assumes increasing problem size with more processors, unlike Amdahl's law, which assumes a fixed problem size. For a program that is 50% serial and 50% parallel on 128 processors, Gustafson's law predicts a theoretical maximum speedup of 64.5.

Step-by-step explanation:

Gustafson's law differs from Amdahl's law in its assumptions about parallel computing. Amdahl's law focuses on a fixed problem size and shows diminishing returns for parallelization due to the serial portion of the task, which cannot be accelerated through more processors. In contrast, Gustafson's law assumes that the problem size increases with the number of processors, making the parallel portion more significant, which leads to a more optimistic view on scalable parallelization.

Applying Gustafson's law to a program with a 50% serial and 50% parallel composition using 128 processors, we calculate the theoretical maximum speedup (S) as follows:

S = N + (1 - N) × s
S = 128 + (1 - 128) × 0.5
S = 128 + (-127) × 0.5
S = 128 - 63.5
S = 64.5

So, the theoretical maximum speedup using Gustafson's law would be 64.5 times faster as compared to the serial execution.