Author: Dann Corbit
Date: 19:07:17 09/05/02
Go up one level in this thread
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? 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. [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.