SMP questions

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.
Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

SMP questions

Post by Patrice Duhamel » Wed Mar 25, 2015 5:45 pm

I start reading documents on YBWC.

If I understand, we can "split" the search at any node after the search of the first move, then all waiting threads (including the current thread) will search remaining moves at this node in parallel ?

This means only the thread that split can ask other threads to search moves at this node, or later other threads will be able to help at this node ?

The search can split in any thread ?

How many threads to create, ex: for 4 threads (4 core), should I create 3 new threads, or create 4 threads searching while the program main thread is waiting for inputs ?

jdart
Posts: 3825
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: SMP questions

Post by jdart » Wed Mar 25, 2015 6:30 pm

As I understand it, the master thread allocates one or more other threads to search in parallel. Later other threads will not join this split point but could be allocated to search other split points that are below it in the tree.

Re how many threads to allocate, the main thread counts so you would allocate 3 more if you have 4 available total.

-Jon

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

Re: SMP questions

Post by bob » Wed Mar 25, 2015 6:38 pm

Patrice Duhamel wrote:I start reading documents on YBWC.

If I understand, we can "split" the search at any node after the search of the first move, then all waiting threads (including the current thread) will search remaining moves at this node in parallel ?

This means only the thread that split can ask other threads to search moves at this node, or later other threads will be able to help at this node ?

The search can split in any thread ?

How many threads to create, ex: for 4 threads (4 core), should I create 3 new threads, or create 4 threads searching while the program main thread is waiting for inputs ?
Couple of quibbles.

1. You can split at any move after the first. If you search the first, then you can split. If you search the first two, you can split. Just not before the first was searched, because you need a good set of bounds before starting the parallel search to make the search more efficient.

2. Create as many threads as you want, just so that no more than N of them are busy at any instant in time where N = actual number of cores you have available. I simply create N-1 (the first one also searches). Some dedicate one to handling input. Some create many but just pick N to execute (this simplifies recursive call stack issues a bit but adds to overhead somewhat.)

Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: SMP questions

Post by Patrice Duhamel » Wed Mar 25, 2015 10:01 pm

Thanks for all the answers.

And if the thread that create a splitpoint finish searching moves before the other threads at this node, it could search for other splitpoints ? or there are some conditions where it should wait the other threads ?

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

Re: SMP questions

Post by bob » Thu Mar 26, 2015 1:19 am

Patrice Duhamel wrote:Thanks for all the answers.

And if the thread that create a splitpoint finish searching moves before the other threads at this node, it could search for other splitpoints ? or there are some conditions where it should wait the other threads ?
I try to avoid all waiting. If the thread that creates a split point finishes, it goes and helps other threads.

I can't imagine any place where it would choose to wait rather than searching, unless there is simply no work left somehow.

jdart
Posts: 3825
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: SMP questions

Post by jdart » Thu Mar 26, 2015 2:28 pm

Patrice Duhamel wrote:
And if the thread that create a splitpoint finish searching moves before the other threads at this node, it could search for other splitpoints ? or there are some conditions where it should wait the other threads ?
The thread that initiates the split can join the search again if it finishes. This is known as the "helpful master" concept. It will only finish if no more moves remain to search at the current split point. In such cases it can assist other threads by searching other split points below the current split point. But it will not join split points that are in some other part of the tree.

--Jon

Patrice Duhamel
Posts: 133
Joined: Sat May 25, 2013 9:17 am
Location: France
Full name: Patrice Duhamel
Contact:

Re: SMP questions

Post by Patrice Duhamel » Thu Mar 26, 2015 5:46 pm

Yes, my question was in the case the thread that initiate the split has finish and there are no more moves to search.

I thought that in some cases the other threads searching at this node have "almost finish" and it could be a waste of time to help with the thread that split, but I guess we can't detect it or it's a bad idea ?

jdart
Posts: 3825
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: SMP questions

Post by jdart » Thu Mar 26, 2015 6:56 pm

The helpful master idea is useful to implement but does not actually help that much, especially with moderate numbers of cores, because the master may not finish first, and even if it does, as you say, the other threads may have relatively little left to do.

That said though, there should not be a large overhead in joining a thread to a split point, so I would go ahead and do it if possible.

--Jon

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

Re: SMP questions

Post by bob » Thu Mar 26, 2015 7:19 pm

jdart wrote:The helpful master idea is useful to implement but does not actually help that much, especially with moderate numbers of cores, because the master may not finish first, and even if it does, as you say, the other threads may have relatively little left to do.

That said though, there should not be a large overhead in joining a thread to a split point, so I would go ahead and do it if possible.

--Jon
It is actually a pretty significant gain. Take the simple case where you split at the root. the master runs out of work and sits. One of the other threads is hung up on a long search because the move it is searching will eventually fail high. Why wouldn't you want the original master to join in and help resolve that fail high before time runs out and you miss it completely.

jdart
Posts: 3825
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: SMP questions

Post by jdart » Fri Mar 27, 2015 12:05 am

One of the other threads is hung up on a long search because the move it is searching will eventually fail high. Why wouldn't you want the original master to join in and help resolve that fail high before time runs out and you miss it completely.
Sure, but that is the best case for helpful master. In general the gain is less.

--Jon

Post Reply