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

d02sutt_p3ma 12/10/07 11:56 AM Page 77 potential concurrency at all. For the past 30 years, processors have been successfully speeding up purely sequential programs by injecting O(K) concurrency in the form of caching, prefetching, instruction reordering, and pipelining. Granted, the maximum potential speedup of sequential code is bounded by some fixed constant K. For example, adding a fast Level 1 (L1) cache can improve memory access from slower L2 or L3 cache times (or, worse still, glacial DRAM or geological disk) up to the speed of L1, but no further. Adding a five-stage instruction pipeline can improve performance by a factor of five, assuming all the pipeline stages have equal weight and minimal overhead, but no further. But O(K) improvements are nothing to sneeze at. Today, nobody would buy a desktop PC that didn’t have plenty of cache and a pipelined processor. We can use the same tricks. We can compute separable pieces of work concurrently by running some of the work on a thread pool. For example, given the following sequential function that computes total sales in two independent regions of similar size Quantity ComputeSales() { return region1.Sales() + region2.Sales(); } // these calculations // are independent To paraphrase Churchill: We shall cheat him in the data sizes, we shall cheat him in the loops, we shall cheat him in the pipelines and in the caches, we shall cheat him in the unimagined new features. We shall never surrender. Notes [1] For more on O(1), O(K), and O(N) concurrency, see my column “How Much Scalability Do You Have or Need?” (DDJ, September 2007), available online at http://www.ddj.com/hpc-high-performancecomputing/201202924. Briefly, O(x) means that the code has about x things it could be running concurrently at a given time, where O(1) is sequential, O(K) is code that hardwires a predetermined fixed amount of concurrency that prefers K cores and can’t use >K cores, and O(N) is scalable across variable numbers of cores. [2] Gene Amdahl. “Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities” (AFIPS Conference Proceedings, Vol. 30, AFIPS Press, April 1967). [3] John Gustafson. “Reevaluating Amdahl’s Law” (Communications of the ACM, 31(5), 1988). DDJ Herb is a software architect at Microsoft and chair of the ISO C++ Standards committee. He can be contacted at www.gotw.ca. you can improve this from O(1) to O(2) by moving the computation of region1.Sales() to a background thread or thread pool, so that region1.Sales() and region2.Sales() can execute concurrently. Just be sure that the calculation you’re shipping to another thread is big enough to justify today’s overhead of executing it somewhere else, and that the data the two operations use really are independent. Generalizing that technique, we can pipeline to overlap separable subparts of work being done to each piece of data in a collection [1]. Figure 3 illustrates the effect of additionally applying O(K) techniques to the “sequential” portions of the program. Accelerate up to x20: Visual Studio builds Make-Based Builds Data Builds R&D Scripts Custom Applications IncrediBuild is an easy-to-use platform for accelerating Windowsbased processes using advanced Grid Computing technology technology. Conclusion Over the next few articles, I’ll discuss ways to apply O(N) and O(K) techniques, and ways to not only cheat Amdahl, but beat him. Shameless teaser: How can you use N cores to get an answer more than N times faster? Normally, getting just N-fold speedups is considered the Holy Grail. Hint: Think about ways you might leverage data locality and/or perform speculative and cancellable execution to set yourself up for such superlinear speedups of p. Then read next month’s column. Cheat Amdahl by doing more of the same: Solve bigger cases of the same problem. As Gustafson concluded: “Speedup should be measured by scaling the problem to the number of processors, not fixing problem size. We expect to extend our success to a broader range of applications and even larger values for N.” (To put “even larger” in context, when Gustafson wrote that he was already reporting repeatable successes with N = 1024 processors.) Cheat Amdahl by finding new O(N) work to do that was once unthinkable. Cheat him by O(K)-parallelizing the apparently “sequential” parts of your code. Download FREE, fully-functional 30-day trial: http://www.xoreax.com February 2008 l www.ddj.com l Dr. Dobb’s Journal 77 http://www.ddj.com/hpc-high-performance-computing/201202924 http://www.ddj.com/hpc-high-performance-computing/201202924 http://www.gotw.ca http://www.xoreax.com http://www.xoreax.com 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.