Question on parallel search

[Michel]

When a thread (say X) is searching a tree spawn from a split point, alpha at the split point will change in the course of the search due to the other threads updating it.

Now it seems to me that thread X should incorporate this updated alpha dynamically in its own search to improve bounds but Stockfish for example does not seem to do this, except of course when there is a beta cutoff at the split point.

Am I making an incorrect reasoning here? I must confess that my mind is not very clear on this.

[Joost Buijs]

When a thread (say X) is searching a tree spawn from a split point, alpha at the split point will change in the course of the search due to the other threads updating it.

Now it seems to me that thread X should incorporate this updated alpha dynamically in its own search to improve bounds but Stockfish for example does not seem to do this, except of course when there is a beta cutoff at the split point.

Am I making an incorrect reasoning here? I must confess that my mind is not very clear on this.

Yes, your reasoning is correct.
Ofcourse alpha has to be updated in the PV search only, in the zero window search there will be an immediate beta cutoff when alfa changes, since it's very complicated to update alpha dynamically in all spawned threads, I assume most programs use the updated alpha only when they grab a new move from the splitpoint.
I have tried several times to update alpha dynamically, the result was a lot of search instability that made the search less efficient.

[bob]

When a thread (say X) is searching a tree spawn from a split point, alpha at the split point will change in the course of the search due to the other threads updating it.

Now it seems to me that thread X should incorporate this updated alpha dynamically in its own search to improve bounds but Stockfish for example does not seem to do this, except of course when there is a beta cutoff at the split point.

Am I making an incorrect reasoning here? I must confess that my mind is not very clear on this.

This is VERY rare in PVS. Almost all nodes are searched with a zero-width window. There is very little loss in not trying to broadcast a new bound to other threads. It would require some complicated code because if you change a single bound, other searches would have to stop, update ALL their bounds since bounds are propagated through the tree, then determine if they would now be able to cutoff any parts of the search that were within the previous bounds...

I doubt you could measure the performance difference in most positions.. In Cray Blitz I did this. Today I do not.

[mcostalba]

When a thread (say X) is searching a tree spawn from a split point, alpha at the split point will change in the course of the search due to the other threads updating it.

Now it seems to me that thread X should incorporate this updated alpha dynamically in its own search to improve bounds but Stockfish for example does not seem to do this, except of course when there is a beta cutoff at the split point.

Am I making an incorrect reasoning here? I must confess that my mind is not very clear on this.

The point is that increasing alpha is a very rare event, apart of course from the PV move (but there is still no split point there: first split is after first move). So I'd guess there is very little gain in broadcasting a new (bigger) alpha because all the remaining moves are likely to fail low anyhow even with the old alpha.

[Michel]

I was just thinking of updating the (alpha,beta) which are passed to the search
at a certain node with the alpha from the split point (of course how
one should do this depends on whether one is at even or odd distance
from the split point, the alpha from the split point may actually update the node's beta). That seemed not at all complex to me. However it is not completely
clear to me if it is the right thing to do.

But since the experts agree that it is not necessary I will not think about it for now. There are enough other things to think about.

[bob]

I was just thinking of updating the (alpha,beta) which are passed to the search
at a certain node with the alpha from the split point (of course how
one should do this depends on whether one is at even or odd distance
from the split point, the alpha from the split point may actually update the node's beta). That seemed not at all complex to me. However it is not completely
clear to me if it is the right thing to do.

But since the experts agree that it is not necessary I will not think about it for now. There are enough other things to think about.

Not only is it not that important, it is quite difficult. If you were to try to change the alpha value at ply=6 for some thread, but that thread is actually down into the tree at ply 20, how would you update all of those recursive stack frames that have the WRONG alpha value (or beta value for every other ply)?

Messy. VERY messy...

[Michel]

how would you update all of those recursive stack frames that have the WRONG alpha value (or beta value for every other ply)?

Is it really? It seems to me that whenever the thread looks at alpha and beta
it can combine their values with the ones currently in use at the split point....

No locking is necessary for this as access to integers is atomic.

[bob]

how would you update all of those recursive stack frames that have the WRONG alpha value (or beta value for every other ply)?

Is it really? It seems to me that whenever the thread looks at alpha and beta
it can combine their values with the ones currently in use at the split point....

No locking is necessary for this as access to integers is atomic.

Throughout the tree you do this;

v = -Search(-beta, -alpha).

If you change alpha at ply=M, and you are currently at ply=N (N > M) in that thread, how do you change all those values that are stored on the STACK, not in one shared memory location???

BTW NOTHING is atomic when using multiple threads on Intel/AMD unless you use the intel "lock prefix" on the instruction that simultaneously reads the old value and writes a new value.

[Michel]

If you change alpha at ply=M, and you are currently at ply=N (N > M) in that thread, how do you change all those values that are stored on the STACK, not in one shared memory location???

Obviously you cannot change values on the stack but you can use
the updated alpha,beta which may produce cutoffs. I.e. you may find
that you are searching a node which is not important with the updated alpha, beta.

BTW NOTHING is atomic when using multiple threads on Intel/AMD unless you use the intel "lock prefix" on the instruction that simultaneously reads the old value and writes a new value.

Well I am not an expert but this web page says that simple load and stores are atomic

http://software.intel.com/en-us/forums/ ... hp?t=48395

Note that we only want to ensure that what we read from the split point
is not garbled because some other thread is writing a value at the same time.

[hgm]

I side with Michel on this. I my design for an SMP engine I also planned to test each newly returned score against both the alpha and beta of the current node, as well as against the alpha at the split-point. (Or in fact first compare the local alpha or beta against alpha or -alpha at the split point, and,hen needed, update those first before comparing them to the returned score.) That doesn't sound like much work at all, because (as remarked) the split-point alpha almost never changes, and thus should stay in the cache of the thread in the Shared state of the MESI protocol. Only when it is increased by another thread the currently cached value becomes Invalidated,and it would requirecompritvely expensive inter-processor communication to read the value. But this is very likely to save you nodes.