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
SMP and helpfull master concept
Moderators: hgm, Rebel, chrisw
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: SMP and helpfull master concept
Yes. You don't want to do this if the subtrees below the splitpoint get too small.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: SMP and helpfull master concept
There are two solutions.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
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...
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: SMP and helpfull master concept
Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: SMP and helpfull master concept
Why the limit? I let the "master" help anywhere in the tree...Gian-Carlo Pascutto wrote:Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: SMP and helpfull master concept
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.bob wrote:Why the limit? I let the "master" help anywhere in the tree...Gian-Carlo Pascutto wrote:Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: SMP and helpfull master concept
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.kGian-Carlo Pascutto wrote: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.bob wrote:Why the limit? I let the "master" help anywhere in the tree...Gian-Carlo Pascutto wrote:Another trick which you can try is to only allow the master to help in subtrees below its own splitpoint.
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.
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: SMP and helpfull master concept
Sure you can, but that doesn't make that SMARTbob wrote: My point was that I am willing to split _anywhere_.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: SMP and helpfull master concept
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...Gian-Carlo Pascutto wrote:Sure you can, but that doesn't make that SMARTbob wrote: My point was that I am willing to split _anywhere_.
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.
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...
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: SMP and helpfull master concept
I understand Bruce's idea, though it seems a little bit messy. But how is the concept of DTS implemented in Crafty?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...
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.