The Era of Amdahl’s Law

Today, the transition is being made from the individual knowledge worker in the Era of Moore’s Law to the collective Web workers in the Era of Amdahl’s Law where Web workers create, sort, search, and manage information between knowledge products, devices, and people.

While corporations were seeking to increase each individual’s productivity in the Era of Moore’s Law, now distributed groups working in parallel are reaping the benefits of plummeting transaction costs over the Web.

In 2005, IBM's announcement that it had doubled the performance of the world's fastest computer, named Blue Gene/L from 136.8 trillion calculations per second (teraflops) to 280.6 teraflops. The Blue Gene system is the new generation of a massively parallel supercomputer in the IBM System Blue Gene Solution series: the epitome of centralized computer power.

At the other end of the scale, Google has developed the largest parallelized computer complex in the world, by inventing their own Googleware technology for parallel processing across distributed servers, microchips, and databases.

As a result, parallel processing is effecting all aspects of the Information Revolution: the mainframe computers have become supercomputers with massively parallel microchip configurations; the individual personal computers of the Era of Moore’s Law have become multicore processors for application processing, and the Web is utilizing applications such as Googleware based upon a vast parallelized computer complex with its specialized concurrent programming.

Parallel processing has infiltrated all aspects of computer usage because the limitations of Moore’s Law require compensation through Amdahl’s Law given by:

Speedup ≤ 1 / (F + (1-F) / N)

Amdahl's law describes how much a program can theoretically be sped up by additional computing resources, based the proportion of parallelizable and serial components. Where F is the fraction of calculation that must be executed serially given as:

F = s / (s + p)

where s = serial execution and p=parallel execution.

Then Amdahl's law says that on a machine with N processors, the maximum speedup is given by:


As N approaches infinity, the maximum speedup converges to 1/F, or (s + p)/s.

This means that a program with fifty percent of the processing executed serially, the sped up is only a factor of two, regardless of how many processors are available. For a program where ten percent must be executed serially a factor of ten is the maximum sped up.

All computer applications must now being translated from sequential programming into parallel processing methods. As a result, the third wave of computing has become the Era of Amdahl’s Law where the information environment of each person is connected through the Web to a variety of multicore devices.

Manycore systems hold the promise of 10 to 100 times the processing power in the next few years. However, as software developer’s transition from writing serial programs to writing parallel programs there will be pitfalls to creating robust and efficient parallel code.

Even if current applications don't have much parallel functionality, s and p can be changed:

1. Increase p by doing more of the same: Increase the volume of data processed by the parts that are parallelizable. This is Gustafson's Law.

2. Increase p by doing adding new features that are parallelizable.

3. Reduce s by pipelining.

If we keep run time constant and focus instead on increasing the problem size, the total work in a fixed time:

Total Work = s + N * p


Besides solving bigger versions of the same problem, we also have the option of adding new features.

Normally, getting just N-fold speedups is considered the Holy Grail, but there are ways to leverage data locality and/or perform speculative and cancelable execution to set up super linear speedups.

References:

[1] Alesso, H. P. and Smith, C. F., Connections: Patterns of Discovery, John Wiley & Sons Inc., New York, NY, 2007.

[2] Sutter, H., Break Amdahl’s Law!, Dr. Dobb’s Portal, Jan. 17, 2008.

[3] Goetz, B., et. al., Java: Concurrency in Practice, Addison-Wesley, Stoughton, Massachusetts, USA, 2008.