Author: Robert Hyatt
Date: 10:44:44 10/05/01
Go up one level in this thread
On October 05, 2001 at 12:28:34, Bruce Moreland wrote: >On October 04, 2001 at 20:14:30, Robert Hyatt wrote: > >>On October 04, 2001 at 18:41:14, Bruce Moreland wrote: > >>>Two units of work is more than twice as fast as six units, so this particular >>>case is super-linear, barely. You can make it more so by making the arrays >>>longer. >> >> >>Nope. I modify my serial algorithm to match your parallel algorithm. Then it >>is not super-linear at all. I find it after two compares, one on the first >>element, one on the last. The parallel algorithm finds it after two compares >>also, but they are done in parallel in one cycle. Speedup = 2.0... > >Bob, I would be an idiot if I said that you couldn't get the same speedup by >modifying the serial algorithm. I'm not saying that. I'm saying that you might >be able to see improbable speedups when modifying a serial algorithm by making >it run in parallel. I haven't disagreed with that at all. What I _have_ said is that if you do get such a speedup, then it clearly points out that your serial algorithm is not the best you can do. in the case of Vincent, I have made that statement repeatedly. (1) Either your speedup is for a few special cases; or (2) your serial search is badly flawed. Perhaps we agree more than you realize? > >I'd be a fool to argue that a parallel algorithm will beat a serial algorithm >plus a guy with a compiler and some time to modify code. > >If you are now saying that a super-linear speedup could be possible, but that a >guy with a compiler could fix the serial algorithm to make it run better, we >aren't arguing about anything. > >bruce That is _all_ I have ever said. If you get a super-linear speedup because of some quirk in the "typical" data that you didn't realize when you wrote the serial algorithm, then when you fix the serial algorithm to handle the quirk case better, the super-linear speedup is gone. If you get a super-linear speedup because of something other than quirky data, then your serial algorithm needs work, because by simple time-slicing it can run faster than the pure serial algorithm did. And that should not happen, unless the serial algorithm has a flaw. But in the case of tree searching, we know much more. IE in my Ph.D. dissertation, I discussed (mathematically) about searching perfectly ordered trees, worst-case ordered trees, and then finally typical-case ordered trees. And chess _must_ fit in the typical-case, for obvious reasons. With perfect ordering, super-linear is impossible, ever. With worst-case ordering, super-linear will happen more frequently, although whether it will average super-linear or not could be debated. For my tests it did not, and I ran some huge test sets. With typical ordering, occasional super-linear can happen, but the average is always not only going to be non-super-linear, but it is going to be below "optimal" as well. IE < 2.0 for 2 processors, < 4.0 for 4 processors, etc...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.