SMP and helpfull master concept

[hcyrano]

hi all

thread T1 create splitPoint at node N1 :
T1 and T2 work for N1

T2 create splitPoint at N2
T2 and T3 work for N2

T1 have finished his job (so wait T2)
all moves at N2 are busy

T3 try to create splitPoint at N3

normaly T1 must be available for T3 (helpfull master concept "recursif")

right?

bah : poor english

regards

[Gian-Carlo Pascutto]

Yes. You don't want to do this if the subtrees below the splitpoint get too small.

[bob]

hi all

thread T1 create splitPoint at node N1 :
T1 and T2 work for N1

T2 create splitPoint at N2
T2 and T3 work for N2

T1 have finished his job (so wait T2)
all moves at N2 are busy

T3 try to create splitPoint at N3

normaly T1 must be available for T3 (helpfull master concept "recursif")

right?

bah : poor english

regards

There are two solutions.

In Crafty, I do what you are describing. I never have a process idle if others have work left to do.

In Ferret, Bruce used way more threads than processors, but had them blocked. Then when you split, the thread that is in control at that point will block, but it will first unblock another thread to take its place and continue to keep all cpus busy. I like my approach better as you don't have to try to figure out how many threads you need to start up front...

[Gian-Carlo Pascutto]

Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.

[bob]

Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.

Why the limit? I let the "master" help anywhere in the tree...

[Gian-Carlo Pascutto]

Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.

Why the limit? I let the "master" help anywhere in the tree...

IIRC this gave a small extra speedup on low numbers of CPUs at some point. I no longer do this, though. It will also save splitpoint memory.

I think it helps in those cases where the first move doesn't give a cutoff but the second one does. After all, if there are no usable split points left in the tree below the master, this means that the master is about to finish.

Anyway, no guarantees, but it might be easy to try and see.

[bob]

Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.

Why the limit? I let the "master" help anywhere in the tree...

IIRC this gave a small extra speedup on low numbers of CPUs at some point. I no longer do this, though. It will also save splitpoint memory.

I think it helps in those cases where the first move doesn't give a cutoff but the second one does. After all, if there are no usable split points left in the tree below the master, this means that the master is about to finish.

Anyway, no guarantees, but it might be easy to try and see.

My point was that I am willing to split _anywhere_. There is always some "shallow split point" where I can't split above it, because I can't split until I am in the search for a node and have satisfied the YBW criterion. But once this "shallow split point is established, I can split anywhere below it multiple times.k

[Gian-Carlo Pascutto]

My point was that I am willing to split _anywhere_.

Sure you can, but that doesn't make that SMART

Let me put it differently:

your helpful master can go help the search for move 2 out of 20, or it can go help the search for move 20 out of 20.

I'd rather have my master do the first than the latter.

[bob]

My point was that I am willing to split _anywhere_.

Sure you can, but that doesn't make that SMART

Let me put it differently:

your helpful master can go help the search for move 2 out of 20, or it can go help the search for move 20 out of 20.

I'd rather have my master do the first than the latter.

Depends. If there is one move left at the root, I would rather help out there with a processor that deep in the tree where there are lots of moves left but they take almost no time...

My implementation of YBW tries to do just that. It will certainly split anywhere, but as the search progresses, the splits tend to get closer to the root for the most part...

Had I chosen to go back and do a full DTS again, that was one advantage since you can now split anywhere with DTS, whereas with a recursive it is either split here or split somewhere else, but you have no clude where somewhere else will end up being...

[Edmund]

There are two solutions.

In Crafty, I do what you are describing. I never have a process idle if others have work left to do.

In Ferret, Bruce used way more threads than processors, but had them blocked. Then when you split, the thread that is in control at that point will block, but it will first unblock another thread to take its place and continue to keep all cpus busy. I like my approach better as you don't have to try to figure out how many threads you need to start up front...

I understand Bruce's idea, though it seems a little bit messy. But how is the concept of DTS implemented in Crafty?

To stick with bruno causse's example, T1 stops working at N1, helps working at N3 and when finished (if T2 still isn't finished yet do some more work in between) go back to N1 and finish the job by propagating the values up.

How does this switching between tasks work for the master process? Are the functions from the first task (N1) still on the call stack when it returns from its task on N3?

Or is it possible to, once T1 is finished on N1, give T2 the responsibility to in the end also deal with the propagating of values, so that T1 doesn't have to return to the node and could erase its stack.

The latter option seems more advantageous to me but I am not quite sure how to implement it recursively.