Author: Sune Fischer
Date: 01:56:53 09/05/02
Go up one level in this thread
On September 04, 2002 at 18:38:17, Dann Corbit wrote: >My take on the matter (in one paragraph): >Robert wrote a paper on parallel speedup, showing a 1.7 increase for 2 CPU's (as >derived from his more general formula). Vincent was unable to reproduce this >sort of speedup, and thought the research was faulty. Robert agreed that the >test set was limited and you won't always get that sort of speedup, but as an >average (over a broad set of positions) that's about what he got. There has >been some acrimony over whether superlinear speedups are possible. I think that >the jury is still out on that one. The jury is wasting their time then ;) You can't get a superlinear speedup, in general. At best you can get a linear, which fortunately can happen with a lot of problems (eg. distributed data analysis like SETI). But I certainly do remember this discussion running a while back;) In chess try and reverse the move ordering to seek the worst move first, that would probably give you a superlinear speedup. This way the slave thread actually does some good in cutting branches faster. But in general it won't happen. Some nodes probably split quite well (fail low nodes?), but you can't improve anything by splitting a fail high node, there is just _one_ good move, how do you propose to speed that up a factor of >=2? So there must be at least some places where running serial is just as fast, thus the speedup is bound to be less than 2. However if you searched the cutoff move second instead of first, then you would get the cut off faster, but naturally only because the serial version sucks. If there was no overhead in splitting at all, one could probably come really close to the factor of two in speedup, for instance splitting only near the leafs or perhaps even making parallel versions of makemove() and eval(). I think it would be interesting to derive the maximum theoretical speedup for N processors with optimal move ordering analyticly, perhaps it could be done with a few simplifying assumptions, like a constant branch factor, no extensions/pruning, no overhead for splitting etc. Then again such a number would become unrealistic because of the many assumptions needed. -S.
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.