Author: Robert Hyatt
Date: 16:47:49 03/03/06
Go up one level in this thread
On March 03, 2006 at 18:59:33, Uri Blass wrote: >On March 03, 2006 at 16:13:39, Robert Hyatt wrote: > >>On March 03, 2006 at 13:22:53, Uri Blass wrote: >> >>>On March 03, 2006 at 13:05:18, Tord Romstad wrote: >>> >>>>On March 03, 2006 at 12:20:43, Tony Werten wrote: >>>> >>>>>On March 03, 2006 at 09:46:12, Tord Romstad wrote: >>>>> >>>>>>What's the problem with a shared history table? >>>>> >>>>>Problem is a big word, it probably isn't that bad. >>>>> >>>>>Suppose thread 1 want to add 1 to the counter: >>>>>1) load memory into register >>>>>2) add 1 to register >>>>>3) move register to memory >>>>> >>>>>If the thread is interrupted between 1 and 3 and thread 2 adds to the same >>>>>entry, you have lost 1 add. >>>> >>>>Yes, this can happen, of course, but it doesn't bother me at all. >>>>Who cares if the history counters are only approximately correct? >>>>The deviations will be really tiny, and I would be very suprised if >>>>they have any measurable impact on move ordering at all. I really >>>>don't understand why anybody would want to copy the entire history >>>>table to each thread at all split points, instead of just sharing it. >>>> >>>>Tord >>> >>>I see a clear advantage of deterministic search relative to non deterministic >>>search. >>> >>>The advantage is in debugging because there are no mistakes that you cannot >>>reproduce. >>> >>>I wonder if somebody try to have version that is deterministic even with more >>>than one processor. >> >>You can do this, but performance will be horrible. I used to have such an >>option in Cray Blitz, where the same processor always searched the same branch, >>and the hash table was completely disabled to avoid the usual race conditions >>that introduce high levels of non-determinism. But I only used this for >>debugging, it was hopeless for anything real... > >You certainly can do it with 2 processors so it is not slower than one processor >and the simple way is if one processor does nothing. >I believe that there are better ways than that and the only question is what >factor of speed improvement you can get by 2 processors if you are >deterministic. > >Not using hash tables is of course not the way to go if the target is to do >deterministic search that is as good as possible with 2 processors. > >One way that can probably help to get some speed improvement is if one processor >is the leader and it searches normally the best move when the second processor >is searching some interesting positions that processor 1 told it to search and >does notsearch more than the number of nodes that it told it to search. > >processor 1 tell processor 2 during the search the following information: > >position >number of nodes to search >alpha >beta > >processor 2 search the position and tell processor 1 when it finish the job. > >There are 2 cases: >1)processor 2 finished the job before processor 1 finished the job that it >defined for itself that may be for example searching 20% more nodes. > >This should be the case that happen usually. >In that case processor 1 ignore the information until it finish the job that it >defined for itself and when it finish the job it stores the information that it >got from processor 2 in the hash so it can use it later. > >2)processor 1 finished the job before processor 2(usually should not happen) >In that case processor 1 simply wait passively for processor 2 to finish the job >and when processor 2 finish the job 1 store the information in the hash and >continue to search. > >Uri Still would be non-deterministic, since both are searching at the same time, and also both are writing to the hash table at the same time, leaving the classic race condition to introduce non-determinism. Very hard to stop that, so about all that is left is to turn hashing off completely when trying to test in that mode... Then you are just left with race conditions on killer move updates, history counter updates, reduction counter updates, and so forth. :)
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.