Algorithms and Parallel Computing

1.9 AMDAHL’S LAW FOR MULTIPROCESSOR SYSTEMS

Assume an algorithm or a task is composed of parallizable fraction f and a serial fraction 1 − f. Assume the time needed to process this task on one single processor is given by

(1.21)

where the first term on the right-hand side (RHS) is the time the processor needs to process the serial part. The second term on RHS is the time the processor needs to process the parallel part. When this task is executed on N parallel processors, the time taken will be given by

(1.22)

where the only speedup is because the parallel part now is distributed over N processors. Amdahl’s law for speedup S(N), achieved by using N processors, is given by

(1.23)

To get any speedup, we must have

(1.24)

This inequality dictates that the parallel portion f must be very close to unity especially when N is large.

Figure 1.8 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. We note from the figure that speedup is affected by the value of f. As expected, larger ...