The question of quantifying the popularity of parallelism has been the focus of considerable debate; the answer is, "it depends."

Everyone agrees that it depends on the size of the problem to be solved and the developer's ability to find a suitable algorithm to take advantage of parallelism. Fortunately, much of this debate has been centered on making sure we write efficient programs for expensive and rare parallel computers. So the definitions of size, efficiency, and expense are all changed with the emergence of multi-core processors. We need to step back, and be sure we review the ground we are standing on. The world has changed.

Amdahl's Law
Gene Amdahl, renowned computer architect, proposed a general formula regarding the maximum improvement to a computer system that can be expected when part of the system is improved. His formula tells us that if we speed up everything in a program 2X, we can expect the resulting program could run 2X faster. However, if we improve the performance of only half the program by 2X, the overall system improves only 1.3X.

Parallel programmers have long used Amdahl's law to predict the maximum speedup one can expect using multiple processors. This interpretation ultimately tells us that a computer program will never go faster than the sum of the parts that do not run in parallel (the serial portions), no matter how many processors we have.

Imagine a program with five equal modules (100 seconds each) which runs in 500 seconds. If we can speed up two of the parts by 2X or 4X. we will see the 500 seconds reduced to only 400 or 350 seconds, respectively. No matter how many processor cores we use, the serial portions create a barrier at 300 seconds that will not be broken because the three parts we do not speed up are always there.

Many have used Amdahl's Law to predict doom and gloom for parallel computers, but there is another way to look at things which shows much more promise.

Gustafson's Observations Regarding Amdahl's Law
Many people have observed that Amdahl's Law views programs as being fixed while we change the computer. Experience seems to indicate that as computers get new capabilities, applications change to take advantage of these features. Most of today's applications would not seem reasonable to run on computers of ten years ago; many would run poorly on machines which are just five years old.

Gustafson took a different approach and suggested a re-evaluation of Amdahl's Law by assuming that the work load scales to take advantage of the new capabilities. We can start with the same 500-second application, but if the problem scales with the available parallelism we are likely to see advancements such that the work scales in parallel. We can double the work of the two parallel regions and have more work scale linearly as we add processors. Two processors can get 1.4X, and 4 processors yield 2.2X. Even in our example, the efficiency of the program is still greatly limited by the serial portion. In fact, the efficiency of using processors in our example is about 40% for large numbers of processors. On a supercomputer, this might be a terrible waste. On a multi-core processor based system, one can hope there is other work running on the computer at the same time. This new world has many complexities. In any case, serial code is still good to eliminate whether you are a "glass-half-empty" type who favors Amdahl's Law or a "glass-half-full" who favors Gustafson's observations.

Both Amdahl's and Gustafson's observations are correct. The only difference is whether you worry about making a program run faster with the same workload, or you envision working on a larger workload. History clearly shows that programs become more complex and aim to solve larger problems, supporting Gustafson's observations. Amdahl's Law is still going to haunt us, however, as we work today to make a single application work faster on the same benchmark. You have to look forward to see a brighter picture.

Making today's application run faster by switching to a parallel algorithm without expanding the problem is harder than making it run faster on a larger problem. So the value of parallelism is easier to prove by looking forward than it is by assuming the world is not changing.

Scalability of an application comes down to increasing the work done in parallel and minimizing the work done in serial. Amdahl motivates use to reduce the serial portion while Gustafson encourages us to increase the work done in parallel. Once you do a reasonable job working your program into using parallelism, using the Gustafson approach is much more likely to yield results.

Here is what Amdahl and Gustafson actually said in their landmark papers which have been interpreted in many different words and equations ever since:

"…the effort expended on achieving high parallel processing rates is wasted unless it is accompanied by achievements in sequential processing rates of very nearly the same magnitude." —Amdahl, 1967

"…speedup should be measured by scaling the problem to the number of processors,
not by fixing the problem size." —Gustafson, 1988

Combining these thoughts, I conclude that the value of parallelism is easier to prove if you are looking forward than if you assume the world is not changing. There is hope.