Author: Scott Gasch
Date: 11:34:59 11/19/04
Go up one level in this thread
On November 19, 2004 at 11:28:34, Anthony Cozzie wrote: >Well, I also did a pretty complicated algorithm, and I designed my own. If you >borrowed someone else's things might go easier for you, although I think that >takes a lot of the fun out of it. It is also possible you are simply more >talented than I am at this. However, I wouldn't say that it works until you >have run it at a dual for a week or so with no problems. I *thought* I had mine >working after about two weeks of implementation :) I think maybe now I'm down >to only 1 bug that seems to only occur on ICC. > >The next task for you is to measure the speedup you get. BTW, I do have to take >back my comment about ABDADA. After talking with some people, it seems like >ABDADA gives a _really_ poor speedup (<1.3 or so, which is barely worth doing). >Of course, Scott's algorithm probably works better. Scott, what kind of speedup >do you get? > >anthony Well the way I did it was to make the engine able to search in parallel and then pick a likely all-node to split the tree. I do not split at the root and I do not split when there is not enough depth left in the tree to justify it. Other than that anytime I'm on a PV node and have searched the first move and it failed low or anytime I'm on a non-PV node and the first N moves fail low (N for me = 3 but this is obviously adjustable) I split... assuming there is a split node available and an idle thread to help search. This works pretty well, I'd say on average about 5-10% of my split nodes end up failing high. I've only tested on my dual proc 1.5ghz Athlon but I see a very good speedup most of the time... When I was measuring and coding this I was seeing 1.8x to 1.9x on a dual proc. My initial speedups were more on the order of about 1.4x or 1.5x but this was due to hash table contention and pawn hash contention (see below). One of these days I will borrow a bigger machine at work and benchmark there. If I do that I'll post results here. I have heard of some people not running into contention in the hash table when going multi-threaded. For example one friend of mine did a MT search and ended up just locking the whole table when one thread was accessing it... and not seeign any slow down. This was not my experience at all and so I end up locking the hash table in 1/64th of the hash table at a time. As I scaled up the number of CPUs searching I suspect this would have to become 1/128th or 1/256th. Also I have a multi-probe algorithm in the pawn hash table that I suspect would not scale out very well with N CPUs. One solution to this I think would be to have a separate pawn hash table in each thread. Scott Scott
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.