7.1.4   Amdahl’s Law

Amdahl’s Law is a statement regarding the level of parallelization that can be
achieved by a parallel computer [Amdahl67].² Amdahl’s law states that for a
constant problem size, speedup approaches zero as the number of processor elements
grows. It expresses a limit of parallelism in terms of speedup as a software
property, not a hardware one.

Formally, let n be the number of processors available for parallel processing.
Let s be the fraction of the code that is of a serial nature only, that is, it cannot
be parallelized. A simple reason why a portion of code cannot be parallelized
would be a sequence of operations, each depending on the result of the previous
operation. Clearly (1 − s) is the fraction of code that can be parallelized. The
speedup is then given as the ratio of the code before allocation to the parallel
processors to the ratio of that afterwards. That is,

Clearly for s = 0 linear speedup can be obtained as a function of the number
of processors. But for s > 0, perfect speedup is not possible due to the
sequential component.

Amdahl’s Law is frequently cited as an argument against parallel systems and
massively parallel processors. For example, it is frequently suggested that “there
will always be a part of the computation which is inherently sequential, [and that]
no matter how much you speed up the remaining 90 percent, the computation
as a whole will never speed up by more than a factor of 10. The processors
working on the 90 percent that can be done in parallel will end up waiting for
the single processor to finish the sequential 10 percent of the task” [Hillis98].
But the argument is flawed. One underlying assumption of Amdahl’s law is that
the problem size is constant, and then at some point there is a diminishing margin
of return for speeding up the computation. Problem sizes, however, tend to scale
with the size of a parallel system. Parallel systems that are bigger in number of
processors are used to solve very large problems in science and mathematics.

Amdahl’s Law stymied the field of parallel and massively parallel computers,
creating an insoluble problem that limited the efficiency and application of parallelism
to different problems. The skeptics of parallelism took Amdahl’s Law
as the insurmountable bottleneck to any kind of practical parallelism, which ultimately
impacted on real-time systems. However, later research provided new
insights into Amdahl’s Law and its relation to parallelism.