Dr. Dobb's Journal - February 2008 - (Page 74)

d02sutt_p3ma 12/10/07 11:57 AM Page 74 Effective Concurrency by Herb Sutter Break Amdahl’s Law! Here’s a law you should break early and often 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 s+p Speedup = — ———— — — —— — s + p/N I’m sure that resonates with your own experience: When it comes to performance criteria that our software must meet, what constraint tends to be the most immovably fixed? It’s how much time we’re allowed to use to get a useful result. Users have finite patience. For example, they want to wait: • • • • Less than a second for a response to a mouse click Less than a minute to sync a PDA or do an incremental compile Less than an hour to encode and burn a DVD Less than 12 hours to calculate tomorrow’s weather forecast or do a nightly build 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. and they push back hard if we don’t meet those deadlines. But if our users can compile or sync or burn N times as much in the same time given N cores, they will happily accept (nay, greedily gobble) that capability and buy the hardware that matches their problem size. If we keep run time constant and focus instead on increasing the problem size, we get a much better formula. Again assuming no overhead, Gustafson’s Law says that the total work a program can perform in a fixed time on a machine with N cores is given by: Total Work = s + Np Breaking the Speed Limit Even if your current application doesn’t have much embarrassingly parallel functionality, the key observation is that s and p are not fixed. You can change them, including by applying not only O(N), but also O(K) concurrency: 1. You can increase p by doing more of the same: Increase the volume of data processed by the parts that are O(N) parallelizable (and therefore the percentage p of time spent in computing). This is Gustafson’s Law. 2. You can increase p by doing more of something new: Add new features that are O(N) parallelizable. 3. You can reduce s by partially parallelizing it using O(K) techniques, such as pipelining. Let’s consider each of these. where “Total Work” is equivalent to the “best possible speedup” compared to hypothetically doing all that work sequentially, even if nobody would ever wait for such a sequential execution. For example, Figure 2 illustrates applying Gustafson’s Law to the problem in Figure 1. That wonderful amplification of O(N) code just makes our parallel day. Importantly, note that the total program is now O(N), even though there is a sequential portion. As N increases to infinity, the total work we can accomplish also increases to infinity. In practice, this means that it increases until we can’t make the problem any bigger or are bound on some other factor, such as memory or other I/O. Still, the key is that the concurrency is scalable, and is not hardwired to a predetermined preferred fixed number K of cores, or worse still bound by a constant factor maximum speedup over the original code as in Amdahl’s approach. 2. Invent New O(N) Work Besides solving bigger versions of the same problem, we also have the option of adding new O(N) features. This is especially effective, and it’s market changing when the feature is a harder challenge than we could ever solve practically before. Remember Myst? Released in 1993, that first-person immersive adventure was the bestselling computer game of all time for most of the rest of the decade because of its breakthrough graphics. Myst let you walk through high-resolution pre-rendered scenes that were like static postcards, preselected views frozen in space and time. Those scenes took hours and hours to render, of course, so all the rendering work had to be done offline and the game was shipped with only the final images, as many as could fit on a CD-ROM. It was simply impossible to think about actually rendering on the user’s computer at all, never mind at several frames per second in real time so that the player could actually move around the world and look wherever he wanted. Sure, Doom accomplished that later the same year, but not nearly at Myst’s high graphic quality. But real-time 3D was only a matter of time. Myst sequels themselves first let the player turn and look at a 360-degree panoramic rendering from a fixed viewpoint, and then completely freed us to walk and look anywhere in real-time 3D. Just as Myst itself was once unthinkable but was made possible by the widespread availability of PCs that had good graphics and CD drives, and real-time 3D sequels were made possible by advances in both CPUs and parallel graphics 1. Do More of the Same O(N) Work Amdahl analyzed the effect on execution time assuming that we add more processors or cores while keeping the workload fixed. In 1988, John Gustafson came along and said (in effect): But that’s not what really happens! When we get more horsepower, we solve bigger problems. “Hence,” Gustafson suggested, “it may be most realistic to assume that run time, not problem size, is constant.” [3] 74 Dr. Dobb’s Journal l www.ddj.com l February 2008 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - February 2008

Dr. Dobb's Journal - February 2008 Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook South American Software Development Conversations Inside Visual Studio 2008 BibPort: Creating Bibliographic References Continuous LINQ The ZK Framework Static Testing C++ Code The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - February 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.