Author: Robert Hyatt
Date: 20:44:54 09/05/02
Go up one level in this thread
On September 05, 2002 at 22:07:17, Dann Corbit wrote: >On September 05, 2002 at 21:58:08, Robert Hyatt wrote: >[snip] >>So I simply asked a few to run one and two cpu tests and provide the raw NPS >>number. It had nothing to do with the speedup in the context most of us use >>here... But clearly if a program can't search 1.5X the nps, then it can't >>search 1.5x faster either... so it is an interesting number as nps is >>certainly an upper bound on the expected actual speedup, which will probably >>be less in reality. > >I am not sure about this. Consider a single CPU example... >We have a tiny hash table and get a terrific NPS rate, maybe 1 million NPS on a >fast CPU. We make a huge hash table and the NPS goes way down. But the time to >solution is sped up dramatically. That's because the hash table shunts node >searches if the transposition has already been computed. > >Now, consider a two-cpu machine. We have two chips sharing the same hash table. > Couldn't we get a big drop in NPS because chip #1 has already calculated some >transposition wanted by chip #2 and stored it in the hash table? sure... but I call that a win by serendipity. It won't be repeatable. Also I am not sure that the hash hits will significantly shorten the search and drive the NPS down, in middlegame positions at least. But it is a _very_ complex interaction. My only point was that if you only search 1.9X the nodes per second, it seems impossible to sustain more than a 1.9X search speed improvement, and since there are "overhead nodes" being searched, the speed improvement will likely be even less. > >I think to get an sort of decent measure you will have to add the hash hits >together with the nodes searched or the amount of analysis could be very >different from just that reported by the node counts. > >I also think it is not absurd that a superlinear speedup can be achieved. >However, I do not think it can be obtained by any of the standard parallel >search algorithms (which could do at best a linear speedup). Perhaps (though) >if the second chip was pondering ahead it might be able to shunt some of the >earlier searches through quick cutoffs. Or some other different idea that is >not related to splitting the work that needs to be done on the root into slices >might possibly yield a better than linear speedup. Of course, to achieve this >it is perfectly clear that the tree must be shrunk compared to the linear single >CPU search. If the total nodes searched to attain the next ply remains the >same, then it is simple mathematics that you cannot achieve a better than linear >speedup. > That is the point. Super-linear speedup is a direct proof of bad move ordering, as that is the only way to get one. I get a few (I am going to post a set of positions for Martin in just a few minutes) but those are offset (more than offset actually) by less than linear speedups in other positions... >[snip]
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.