11.2. Amdahl’s Law

Some problems can be solved faster with more resources—the more workers available for harvesting crops, the faster the harvest can be completed. Other tasks are fundamentally serial—no number of additional workers will make the crops grow any faster. If one of our primary reasons for using threads is to harness the power of multiple processors, we must also ensure that the problem is amenable to parallel decomposition and that our program effectively exploits this potential for parallelization.

Most concurrent programs have a lot in common with farming, consisting of a mix of parallelizable and serial portions. Amdahl’s law describes how much a program can theoretically be sped up by additional computing resources, based on the proportion of parallelizable and serial components. If F is the fraction of the calculation that must be executed serially, then Amdahl’s law says that on a machine with N processors, we can achieve a speedup of at most: