SMP and helpfull master concept

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
hcyrano

SMP and helpfull master concept

Post by hcyrano » Fri Jan 16, 2009 9:41 am

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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: SMP and helpfull master concept

Post by Gian-Carlo Pascutto » Fri Jan 16, 2009 7:46 pm

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

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SMP and helpfull master concept

Post by bob » Fri Jan 16, 2009 8:18 pm

hcyrano wrote: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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: SMP and helpfull master concept

Post by Gian-Carlo Pascutto » Sun Jan 18, 2009 11:54 am

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

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SMP and helpfull master concept

Post by bob » Sun Jan 18, 2009 5:43 pm

Gian-Carlo Pascutto wrote: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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: SMP and helpfull master concept

Post by Gian-Carlo Pascutto » Thu Jan 22, 2009 7:09 am

bob wrote:
Gian-Carlo Pascutto wrote: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
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SMP and helpfull master concept

Post by bob » Thu Jan 22, 2009 4:12 pm

Gian-Carlo Pascutto wrote:
bob wrote:
Gian-Carlo Pascutto wrote: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
Posts: 1184
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: SMP and helpfull master concept

Post by Gian-Carlo Pascutto » Thu Jan 22, 2009 11:09 pm

bob wrote: 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
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SMP and helpfull master concept

Post by bob » Fri Jan 23, 2009 5:46 am

Gian-Carlo Pascutto wrote:
bob wrote: 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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: SMP and helpfull master concept

Post by Edmund » Tue Jun 16, 2009 9:52 am

bob wrote: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.

Post Reply