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

The final row of Table 1 illustrates this effect with a simplified example case that defines a clustering factor, C: We still have M matches, but the matches are concentrated in 1/C-th of the subranges (not necessarily contiguous) to be explored by the parallel workers. When C=1, we’re just in the uniform distribution case. But when C>1, the lucky workers’ probability of success on each test is higher by a factor of C, and because in this example we are guaranteed that one of them will find the answer, this has the same effect on the performance of the entire search as if all workers enjoyed the same boost; that is, it’s as if the whole collection contained not just M matches, but CM matches. Hence the parallel search enjoys not just the expected linear speedup of P, but a superlinear speedup of CP—the greater the clustering factor, the greater the improvement above and beyond the linear speedup from using a larger number of processors [1]. This isn’t limited to simple array-like collections. Many kinds of collections naturally enjoy clustered matches. For example, when we traverse a tree or graph using depth-first search, the parallel version of the algorithm typically has each parallel worker searching a localized subtree, and in many problem domains the solutions tend to be clustered in subtrees. When that happens, one worker will have a disproportionately better chance of being assigned an area with more matches, and we can expect superlinear improvement. Example applications range from searching game trees (for example, a bad move at one node in the tree can cause the entire subtree below it containing subsequent moves to have no good solutions), to CAD and VLSI circuit layout algorithms (see [2]). Obviously, that will be slower than the parallel version by only a factor of P.” Give yourself bonus points if you noticed that, and more bonus points if you noticed that even Amdahl’s Law (covered last month [3]) implies that the maximum speedup though the use of P processors cannot be more than P. It is indeed important and useful to know we can turn any parallel algorithm into a sequential one by just doing the steps of the work Figure 2: Sequential versus parallel search, single match. Figure 3: Sequential versus parallel search matches evenly distributed. Figure 4: Sequential versus parallel search, when matches are clustered. A Word About Sequential Efficiency versus Complexity At this point, it’s important to consider and understand a potential objection. “But wait,” someone could complain, “your example so far is unfair because you’ve stacked the deck. The truth is that, when you find a superlinear speedup, what you’ve really found is an inefficiency in the sequential algorithm.” Taking a deep breath, the dissenter might correctly point out: “For any P-way parallel algorithm, we can find a sequential algorithm that is only P times slower (that is, the parallel advantage is linear, not superlinear) as follows: Just visit the nodes in the same order as the parallel algorithm, only one at a time instead of P at a time. Visit the set of nodes visited first by each worker, then the set of nodes visited second by each worker, and so on. Table 1: Sequential versus parallel search, matches distributed uniformly versus nonuniformly. March 2008 l www.ddj.com l Dr. Dobb’s Journal 69 http://www.codereviewbook.com http://www.codereviewbook.com 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.