Author: Robert Hyatt
Date: 21:15:28 11/08/02
Go up one level in this thread
On November 08, 2002 at 19:25:54, Murray wrote: > >(snip) > >>>Just start 2 processes instead of 1, let one process do as if it is >>>single cpu and play the game with that. the other process just fills the >>>hashtable at the same time. >>> > >Hmm so do you mean that the first process doesn't actually fill the hash table >but tells the 2nd process what put add and which key to insert it? >I can see that saving a bit of time, but I found with my program that the >biggest hit was the probe from the hash table (not the update) as the probe was >the one doing all the damage with most probes reading from main memory rather >than a local CPU cache. the update however follows the probe and so there is >more chance of hitting the CPU cache. > >(snip) >> >>Don't know where you have been, but the parallel search in Crafty took two weeks >>to write. It may well _still_ have a bug or two that I haven't seen show up, of >>course. >>But the idea is to start off with something that has a chance of producing good >>performance. Just sharing hash tables isn't going to offer much. > >What parallel algorithm would you recommend for targetting 2 CPU systems only? >Which is the simplest to implement and works reasonably well for 2 CPU? PV split >or some other? First, forget the crapola algorithms and do something that is known to work. The simplest is the PVS algorithm, _not_ to be confused with the PVS negamax search. The way this works is that you do (say) a 10 ply search. You search the first move at ply 1, 2, ..., 9 with one cpu. At ply=10 you start both processors to searching and they search until they finish. Then you back that score up to ply=9 and search the rest of those in parallel. You continue this until you back up to the ply-1 list and search everything there in parallel. That is not hard to implement, and it will produce a good speedup for 2-4 processors. Beyond that it becomes less efficient, but then it is not that hard to modify it to become something even better than bare PVS... Second, think "dual" but plan on "more". IE you don't want to limit yourself to duals when quads might be the norm in 3-4 years. And finally, follow good software engineering practices. Design the code so that it is easy to understand. Efficiency (cute programming tricks) in the parallel code itself is counter-productive because it isn't executed very much, and making it more complicated than necessary is going to lead to trouble down the road...
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.