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

Effective Concurrency by Herb Sutter Going Superlinear When it comes to scalability, lots (for lack of a better word) is good WE SPEND MOST of our scalability lives inside a triangular box, shown in Figure 1. It reminds me of the early days of flight: We try to lift ourselves away from the rough ground of zero scalability and fly as close as possible to the cloud ceiling of linear speedup. Normally, the Holy Grail of parallel scalability is to linearly use P processors or cores to complete some work almost P times faster, up to some hopefully high number of cores before our code becomes bound on memory or I/O or something else that means diminishing returns for adding more cores. As Figure 1 illustrates, the traditional shape of our “success” curve lies inside the triangle. Sometimes, however, we can equip our performance plane with extra tools and safely break through the linear ceiling into the superlinear stratosphere. So the question is: “Under what circumstances can we use P cores to do work more than P times faster?” There are two main ways to enter that rarefied realm: • Do disproportionately less work. • Harness disproportionately more resources. This month and next, we’ll consider situations and techniques that fall into one or both of these categories. Parallel Search: Exploiting Nonuniformity Let’s say we want to search an unsorted collection of size N for a value that matches some criteria. First, consider a simple sequential search: • If no match exists, the sequential search has no choice but to look at all N elements. • If there’s one match, on average, the sequential search has to look at half of the elements to find the match, which is still O(N). • If there are M matches, it typically has to look at proportionately fewer elements, or O(N/M). These results are summarized in the first column of Table 1. A simple P-way parallel search, where each worker explores 1/P-th of the collection, will normally be P times faster than the sequential search even in the worst case. After all, we’re just searching P elements at each step instead of only one. (See the second column of Table 1.) Figures 2 and 3 show sample sequential and parallel searches side by side. But something interesting happens when the distribution of solutions is not uniform, because then averages no longer apply the same way. To illustrate what happens when matches are clustered, consider Figure 4: We still have M matches in the collection, as before, but let’s assume that they are distributed, not evenly throughout, but with higher probability in some regions. For simple sequential search, this is no big news: It fares neither better nor worse, and on average still takes as long to find a match as it would if the matches were distributed uniformly throughout the collection. Even if the sequential algorithm writer knows in advance that matches tend to be clustered, it’s hard to see how to take advantage of that without also knowing in advance where the clusters are. For the simple parallel search, on the other hand, clustering is great news, because a parallel search directly takes advantage of any locality there may be in the matches. Consider: Any clustering effect means that some subrange workers will end up discovering that they are impoverished, having relatively fewer matches, or none at all, in their assigned search areas. But other workers will enjoy a correspondingly higher number of matches in their areas, which means—and this is the important part—they will have a higher probability of finding a match each time they test an element, which in turn means that on average they will need to visit fewer elements to find a match. Like Forty-Niners panning and digging for nonuniformly distributed gold in California (near Sutter’s Mill; no relation), many workers will find little or nothing, while a lucky few, or just one, will hit the Motherlode. And “just one” is all it takes; any clustering at all is immediately helpful because the time to perform the total search is the minimum of the workers’ runtimes—we’re done as soon as any worker finds a match. Figure 1: Parallel scalability. 68 Dr. Dobb’s Journal l www.ddj.com l March 2008 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.