Algorithms and Parallel Computing

1.10 GUSTAFSON–BARSIS’S LAW

The predictions of speedup according to Amdahl’s law are pessimistic. Gustafson [15] made the observation that parallelism increases in an application when the problem size increases. Remember that Amdahl’s law assumed that the fraction of parallelizable code is fixed and does not depend on problem size.

To derive Gustafson–Barsis formula for speedup, we start with the N parallel processors first. The time taken to process the task on N processors is given by

(1.28)

When this task is executed on a single processor, the serial part is unchanged, but the parallel part will increase as given by

(1.29)

The speedup is given now by

(1.30)

Figure 1.9 shows the speedup versus f for different values of N. The solid line is for f = 0.99; the dashed line is for f = 0.9; and the dotted line is for f = 0.5. Notice that there is speedup even for very small values of f and the situation improves as N gets larger.

Figure 1.9 Speedup according to Gustafson–Barsis’s law. The solid line is for f = 0.99; the dashed line is for f = 0.9; and the dotted line is for f = 0.5.

To get any speedup, we must have

(1.31)

Notice that we can get very decent speedup even ...