SMP questions

[hgm]

When in an SMP program one search thread (A) reaches, through its hash move, a node that is currently being searched by another thread (B), what would you do? Let A help B search that sub-tree? Because they might have reached the node through a different path, they might have different ideas about what are rep-draws. Should we care about that? When B had finished the search before A hit upon the node, we would have had B use the score despite the fact that there might be invalid rep-draws in the sub-tree searched by B. So my guess is that it it would not do much extra harm to let the two threads cooperate on the search with different path.

But what to do if you hit on a node that is being seached at a lower depth than you would need? Would you first let thread A help B to finish the lower-depth search, effectively slipping in an IID iteration, before embarking on your own search?

[bob]

When in an SMP program one search thread (A) reaches, through its hash move, a node that is currently being searched by another thread (B), what would you do? Let A help B search that sub-tree? Because they might have reached the node through a different path, they might have different ideas about what are rep-draws. Should we care about that? When B had finished the search before A hit upon the node, we would have had B use the score despite the fact that there might be invalid rep-draws in the sub-tree searched by B. So my guess is that it it would not do much extra harm to let the two threads cooperate on the search with different path.

But what to do if you hit on a node that is being seached at a lower depth than you would need? Would you first let thread A help B to finish the lower-depth search, effectively slipping in an IID iteration, before embarking on your own search?

I assume you mean "position" as opposed to "node" in this context? I am unaware of anyone that would even detect this, since there is no real reason to link a position (entry in a hash table) to a node (specific position in the search three). We hope that one finishes before the other starts, so that the hash table will avoid the second search completely (typical transposition of moves), but if not, I don't do anything since if one gets there first, it will probably leave hash entries here and there along the subtree from that position that will assist the other one. Very similar to what happens in a serial search if the hash entry for a position gets overwritten so that the next transposition is not noticed and the search is repeated.

I think that the overhead for even trying to detect this case would be worth more than what you gain.

Just my $.02 here...

[hgm]

Indeed, I meant position. I was thinking of the search as a graph, rather than a tree, allowing branches to merge again after a transposition. Thanks for the reply. The SMP implementation I had in mind would mark hash entries as 'closed' when it starts working on the critical (= early) moves, and then, once it is convinced it will be an all-node, replace it by an 'open' mark, to indicate to other threads hitting on it that they can (and preferably should) use it as a split point, and randomize their move ordering in that node.

So they would discover another thread is working on the node more or less automatically, during the hash probe, when figuring out on a hit if there is a score they can use.

The reason I am a bit queasy for having two searches at different depth is that I also had planned to use the hash entry to let the searchers 'broadcast' any increases of alpha to their fellow searchers: search threads would periodically probe hash entries for all nodes in their current path to benefit from any contraction of the search window (possibly causing a beta cutoff amputating the sub-tree below the point of change), and report any alpha increase they find through a move out of there by writing the new alpha in the score field. This would become a bit messy if not all searchers were searching all busy nodes at the same depth.

[bob]

Indeed, I meant position. I was thinking of the search as a graph, rather than a tree, allowing branches to merge again after a transposition. Thanks for the reply. The SMP implementation I had in mind would mark hash entries as 'closed' when it starts working on the critical (= early) moves, and then, once it is convinced it will be an all-node, replace it by an 'open' mark, to indicate to other threads hitting on it that they can (and preferably should) use it as a split point, and randomize their move ordering in that node.

So they would discover another thread is working on the node more or less automatically, during the hash probe, when figuring out on a hit if there is a score they can use.

The reason I am a bit queasy for having two searches at different depth is that I also had planned to use the hash entry to let the searchers 'broadcast' any increases of alpha to their fellow searchers: search threads would periodically probe hash entries for all nodes in their current path to benefit from any contraction of the search window (possibly causing a beta cutoff amputating the sub-tree below the point of change), and report any alpha increase they find through a move out of there by writing the new alpha in the score field. This would become a bit messy if not all searchers were searching all busy nodes at the same depth.

The main point is that you do want to be doing parallel searches at different depths. Often. You can alway try the "broadcast" but I have found it to be pretty much useless with PVS, since almost everything is searched with a null window, and you either fail low or fail high. A fail high (in Crafty) instantly results in all threads working anywhere below that node (where the fail high was found) being terminated. I keep all the "split blocks" linked so I can tell who is working together at any split point, and any processors that are helping somewhere below that split point. Not very useful for 2 cores, of course, but once you get to 8 and 16 it becomes an issue.

I've been intending to write up a detailed explanation of Crafty's parallel search implementation for the JICGA, since it really has never been explained in detail. It is simple enough to use, but efficient enough to produce excellent results. And it can provide many enjoyable hours of debugging.