Dr. Dobb's Journal - March 2008 - (Page 70)

Effective Concurrency one at a time instead of P at a time. This is a simple and cool technique that often helps us reason clearly about the performance of our parallel algorithms; we definitely need this one in our algorithm design toolchests. But we cannot therefore conclude that superlinear speedups are simply due to inefficiency in the sequential algorithm (“you should have written the sequential one better”). Let’s consider a few pitfalls in the proposed resequentialized algorithm. First, it has worse memory behavior, especially if (a) the algorithm makes multiple passes over the same region of data and/or (b) the collection is an array. The proposed algorithm has worse memory and cache locality because it deliberately keeps jumping around through the search space. Further, its traversal order is hostile to prefetching: Hardware prefetchers try to hide the cost of accessing memory by noticing that if your program is asking for memory location X now, it’s likely to want memory locations like X+1 or X–1 next, so it can choose to speculatively request those at the same time without actually waiting for the program to ask for them. This typically gives a big performance boost to code that traverses memory in order, either forward or backward, instead of jumping around. (This applies less if the collection is a nodebased data structure like a tree or graph, because node-based structures typically make their traversals jump around in memory anyway.) Note that the parallel algorithm avoids this problem because each worker naturally maintains both linear traversal order and locality within its contiguous subrange. You might expect that if the workers all share the same cache anyway, the analysis could come out the same, but the problem doesn’t bite us for reasons we’ll consider in more detail next month when we cover hardware considerations. (Hint: The workers typically do not share the same cache…) Second, it’s more complex. It has to do more bookkeeping than a simple linear traversal. This additional work can be a small additional source of performance overhead, but the more important effect is that algorithms that are more complex require more work to write, test, and maintain. Third, it will sometimes be a pessimization. Even when the values are nonuniform (which is what the complexified algorithm is designed to exploit), sometimes there will be high-probability areas near the front of the collection, and the original sequential search would have searched them thoroughly first whereas the modified version will keep jumping away from them. After all, there’s no way to tell what visitation order is best without knowing in advance where the high-probability regions are. Finally, and perhaps most importantly, when we’re comparing the proposed algorithm with simple parallel search, we’re not really comparing apples with apples. We are comparing: • A complex sequential algorithm that has been designed to optimize for certain expected data distributions, and • A simple parallel algorithm that doesn’t make assumptions about distributions, works well for a wide range of distributions, and naturally takes advantage of the special ones the optimized one is trying to exploit…and still gets linear speedup over its optimized sequential competition on the latter’s home turf. Get data right AddressObject API Prevent errors before they occur to ensure the integrity of your database. Use AddressObject API to verify, cleanse and format customer data at the point of entry or in batch. Address Object easily integrates with Perl, PHP Java and .NET. , - offering a better way to build-in data validation. right from the start On Deck There are two main ways into the superlinear stratosphere: • Do disproportionately less work. • Harness disproportionately more resources. This month, I focused on the first point. Next month, I conclude that with a few more examples, then consider how to set superlinear speedups by harnessing more resources—quite literally, running on a bigger machine without any change in the hardware. Acknowledgments Thanks to Tim Harris, Stephan Lavavej, and Joe Duffy for their input on drafts of this article. Notes [1] V.N. Rao and V. Kumar. “Superlinear speedup in parallel statespace search,” Foundations of Software Technology and Theoretical Computer Science (Springer, 1988). [2] Si. Pi Ravikumar. Parallel Methods for VLSI Layout Design, 4.3.2 (Ablex/Greenwood, 1996). [3] H. Sutter. “Break Amdahl’s Law!” (DDJ, February 2008). DDJ Get a FREE demo at: MelissaData.com/dobbs 70 1.800.MELISSA Dr. Dobb’s Journal l www.ddj.com l March 2008 http://MelissaData.com/dobbs http://MelissaData.com/dobbs http://www.ddj.com

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

Dr. Dobb's Journal - March 2008 Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook Social Networks and Software Development Conversations Detecting Bugs in Safety-Critical Code Change Code Without Fear Continuous Integration and Performance Testing Wt: A Web Toolkit Automating Release Notifications The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - March 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.