Effective Concurrency: Break Amdahl’s Law!

The latest Effective Concurrency column, "Break Amdahl’s Law!", just went live on DDJ’s site, and will also appear in the print magazine. From the article:

Back in 1967, Gene Amdahl famously pointed out what seemed like a fundamental limit to how fast you can make your concurrent code: Some amount of a program’s processing is fully "O(N)" parallelizable (call this portion p), and only that portion can scale directly on machines having more and more processor cores. The rest of the program’s work is "O(1)" sequential (s). [1,2] Assuming perfect use of all available cores and no parallelization overhead, Amdahl’s Law says that the best possible speedup of that program workload on a machine with N cores is given by

Note that, as N increases to infinity, the best speedup we can ever get is (s+p)/s. Figure 1 illustrates why a program that is half scalably parallelizable and half not won’t scale beyond a factor of two even given infinite cores. Some people find this depressing. They conclude that Amdahl’s Law means there’s no point in trying to write multicore- and manycore-exploiting applications except for a few "embarrassingly parallel" patterns and problem domains with essentially no sequential work at all.

Fortunately, they’re wrong. If Amdahl’s Game is rigged, well then, to paraphrase a line from the movie WarGames: The only way to win is not to play. …

I hope you enjoy it.
Finally, here are links to previous Effective Concurrency columns (based on the dates they hit the web, not the magazine print issue dates):
July 2007 The Pillars of Concurrency
August 2007 How Much Scalability Do You Have or Need?
September 2007 Use Critical Sections (Preferably Locks) to Eliminate Races
October 2007 Apply Critical Sections Consistently
November 2007 Avoid Calling Unknown Code While Inside a Critical Section
December 2007 Use Lock Hierarchies to Avoid Deadlock

One thought on “Effective Concurrency: Break Amdahl’s Law!

  1. “Herb fought the law—Amdahl’s Law, that is—and Herb won-DDJ” -Was it been a good caption? Is it real that Herb won? Even how would someone tell you fought the amdahl’s law? You just pointed out the gustafson’s law right? It have read most of your recent articles in DDJ. The intention of the article was excellent that not to stop by the parallelization since Amdahl’s law tells there cant be speedup. But the title of the article looked very weird for me. I just made a blog on this at http://amalp.blogspot.com/2008/02/did-herb-sutter-fight-with-amdahls-law.html.

Comments are closed.