Dr. Dobb's Journal - April 2008 - (Page 52)

d04sutt_p5ds 2/13/08 9:53 AM Page 52 Effective Concurrency by Herb Sutter Super Linearity and the Bigger Machine Sometimes you can have your scalability and boost it, too THERE ARE TWO main ways to achieve superlinear scalability, or to use P processors to compute an answer more than P times faster (see Figure 1): • Do disproportionately less work. • Harness disproportionately more resources. Last month [1], we focused on the first point by illustrating parallel search and how it naturally achieves superlinear speedups when matches are not distributed evenly because some workers get “rich” subranges and will find a match faster, which benefits the whole search because we can stop as soon as any worker finds a match. This month, we’ll conclude examining the first point with a few more examples, and then consider how to achieve superlinear speedups by harnessing more resources—quite literally, running on a bigger machine without any change in the hardware. simple search algorithm will do, such as a linear search for arrays or a depth-first search for trees. Parallel search naturally exploits nonuniform distributions of matches: • Without knowing where the nonuniformity is. It doesn’t need any prior locality information, such as location hints for high-probability areas to try first. • Without knowing whether there is any nonuniformity at all. Most interestingly, parallel search naturally benefits from nonuniformity without any extra knowledge at all, not even whether there is any! In this respect, we might say that parallel search is deliciously opportunistic. Sequential search, on the other hand, cannot exploit nonuniformity at all without advance information about where the high-probability regions are. Having the sequential algorithm visit nodes in a different or randomized order doesn’t help by itself without additional information about where to start [2]. Even armed with a map of the high-probability match areas, the sequential algorithm would need to be made more complex to exploit the nonuniformity. Finally, getting superlinear parallel algorithm performance typically relies on the ability to interrupt or cancel work. There are two aspects to this, one musthave and one good-to-have: • Immediate return (necessary). When a worker finds a match, we must be able to return the result to the caller, and let the caller complete immediately without waiting for other workers to complete normally. Otherwise, parallel performance will still scale, but the scaling will usually be sublinear; the time to complete is the maximum, not the minimum, of all workers, and in our search example, we’d typically have to wait for some unsuccessful workers that take N/P time, which puts the overall search’s performance in the same category. • Stop abandoned work (highly desirable). When one worker finds a match, we want to be able to efficiently stop the other workers in order to reclaim their resources, including access to any data they may have locked and the OS and hardware threads they are running on, so that we can use those resources for other work. This is sometimes called “interruption” or “cancellation” and will be the subject of next month’s column. What Have We Learned? As we saw last month, a parallel search often doesn’t need to do anything special to exploit a nonuniform distribution of matches to find a match that much faster; a Other Sources of Superlinearity Another way to achieve superlinear scalability is to exploit partial information. In some parallel algorithms, one worker can discover partial information that it can communicate to other workers to let those others do their work faster than they could do otherwise. For example, in a tree search, one worker might discover that “there are never matches under a node whose weight is over 100.” Or, in computing solutions to a set of equations, one worker might discover that in any solution the value of variable x has to be between y–1 and y+4. Other workers can then use Figure 1: Parallel scalability. 52 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://www.ddj.com

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

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

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