Author: Robert Hyatt
Date: 12:21:50 09/19/01
Go up one level in this thread
On September 19, 2001 at 10:21:44, Uri Blass wrote: >On September 19, 2001 at 09:57:21, Robert Hyatt wrote: > >>On September 19, 2001 at 07:18:28, Tony Werten wrote: >> >>>On September 18, 2001 at 18:27:01, Robert Hyatt wrote: >>> >>>>On September 18, 2001 at 17:19:54, Vincent Diepeveen wrote: >>>> >>>>>On September 18, 2001 at 16:53:30, Robert Hyatt wrote: >>>>> >>>>>>On September 18, 2001 at 14:45:45, Vincent Diepeveen wrote: >>>>> >>>>>[snip] >>>>> >>>> >>>>That is correct. If you can produce a speedup of > 2x, using 2 cpus, you >>>>have a bug, or an anomaly position. It is simply not possible. If you >>>>are _really_ doing that, you should modify your single-cpu version as >>>>follows: >>>> >>>>search normally until you would choose to use a second process if you had one. >>>>From this point forward, time-slice between two search threads. Search one >>>>node on one, one on the other. That should run twice as fast, since it is >>>>_exactly_ how the program really does on the SMP platform. >>>> >>>>And that will _not_ work unless you have either the world's worse sequential >>>>search algorithm, or the world's buggiest parallel search algorithm. >>>> >>>>Before you label a statement as ridiculous, find me _one_ person that will >>>>side with you and say that "yes, it is possible to get a > 2 speedup using >>>>only two cpus on anything but anomaly positions. Find _one_ person that will >>>>agree... >>>> >>> >>>Just for fun, I'll give it a try. I'm probably wrong but maybe you can point out >>>where I go wrong. >>> >>>To make it more obvious I'll make the numbers a bit more extreme. >>> >>>Vincent says that in 85% of the cases the first move is the cutoff move, that >>>means in 15% it's not. Now suppose the cutoff move is always the second move and >>>that it's an easy cutoff. >>> >>>Normally you would search the first move (say 15 seconds) then the second (say 5 >>>sec) total is 20. >>> >>>Now 1st and second are searched parallel, second causes cutoff after 5 secs, >>>first get's stopped. Total time 5 secs. 4 times faster. >> >> >>Here is the problem. That works in 15% of the time. What about the _other_ >>85% of the time? You search two moves. You only need to search the first to >>get a cutoff. 85% of the time you search double the stuff you _need_ to search. >>Net result: way slower. >> >> >> >>> >>>Funny thing: The worse your first cutoff rate is, the bigger the speedup. >>> >> >>True of course. And well-known. But today's programs (mine at least) >>gets a cutoff on the first move 92% of the time. That leaves only 8% >>for improvement. > >Not exactly. > >It is possible to get a speed improvement even in part of the 92% of the cases. >The fact that you only need the first move to get a cutoff does not prove that >the order of moves is optimal because it is possible that another move helps you >to get the cutoff faster. > >Uri That is certainly possible. And it could be measured if someone wants to test it. But irregardless, you _never_ want to search two moves at the same time if either will cause a cutoff, because _one_ is doing unnecessary work that is not contributing a thing to the speedup of the sequential algorithm.
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.