We need to define terms so we don't end up arguing about something we probably agree on.
Here is my assertion (which I admit needs to be checked): Given perfect move ordering, but not a-priori knowledge of this, a parallel program will search more nodes on average than a serial program. And more processors will "waste" more work in this sense. That's my definition of "wasted work." I'm sure there are also synchronization issues and other overheads, but let's just deal with the tree size. I think you agree with this, but I'm not sure. I have to run but I will try to dig up a paper on this later today. - Don On Tue, 2008-08-12 at 16:26 +0200, Gian-Carlo Pascutto wrote: > > On Tue, 2008-08-12 at 15:40 +0200, Gian-Carlo Pascutto wrote: > >> Even in the theorethical case of a perfectly ordered game tree? > > > > I'll have to check my facts, but I remember seeing actual numbers on > > this. It has something to do with the minimial tree and it was a proof > > think that alpha-beta could not be fully parallel. I will see what I > > can dig up. > > This is very different from being forced to do wasted work. > > To put it extremely, I can run the entire problem on just 1 CPU. > No work wasted. No speedup either, but hey, no work wasted :) > > If you split off work only when you are positive it will not get > aborted, you will still get a speedup, but it will be limited by > the critical tree (or minimal tree or mandatory work...I forgot the name). > > I think you have this last case in mind. > > In practise things are very different from theory. You would rather > do very questionable work (which is likely to get aborted) rather > than have a CPU sit idle. > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
