Author: Scott Gasch
Date: 23:54:34 08/29/01
Hi, I've been reading about parallel search algorithms. So far the only practical ones I have run across are ABDADA and Youngest Brother Wait. Others like APHID and tree-splitting seem designed for distributed operation or operation with more processors than I'm likely to use. My first question is this: am I missing any important algorithm? I'd like to make sure I at least read an overview of the important ones before trying to implement something. What I have read leads me to conclude that ABDADA offers a good speedup with fairly minor codebase changes. Below is my understanding of the algorithm. I think I have an ok feel for what is happening but I would really appreciate clarification.. I do not have a firm grip on this yet: 1. A count of "number of processors under this node" is maintained in the hash table entry for each node. 2. Every node is searched with an extra flag: exclusive. The recursive call to search the subtree under the first move tried in a position is passed exclusive as true. All subsequent recursive calls (for moves 2..N) are passed exclusive as false. 3. When the hash table is probed, the exclusive flag is passed in. If a hash cutoff is possible, it is returned no matter what. If no cutoff is possible and exclusive is true and there is another processor already under this node, return "on evaluation" -- a special value. Otherwise increment the numproc for this node and return hash miss. 4. While searching save any moves that return the "on evaluation" value and go on. Having looped through all possible moves (1..N) once without a fail high, retry any move that returned "on evaluation". Repeat until all moves return a real score. This should be cheap because we hope the other processor(s) under these moves have finished by now and it should simply be a matter of making the move, making a recursive call, and getting a hash cutoff[?]. 5. When exiting a node, in addition to storing its information in the hash table also decrement numproc under the node. 6. Each thread (one for each cpu) starts at the root (with exclusive = false) and searches the tree in parallel. When the search terminates all threads should return the same value. Only one thread should change the PV structure. This makes me wish i didn't have so many tricks in my search routine -- extended transposition cutoff like tries to avoid avoiding a null move... don't store stuff in the hash table if a lot of extended pruning was done at this node, etc... In short this is going to be a mess to implement even when I do fully understand it. Thanks for any explaination / advice. 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.