Smp concepts

[syzygy]

There are multiple issues making limiting the number of threads at one split point beneficial.

(...)

I do allow everyone to split near the root with no limit, but nearer to the tips I impose a limit.

Yes, there can be a benefit near the tips, i.e. at the minimum split depth. Increasing min_split_depth will have roughly the same benefit.

Using a polling approach (i.e. idle threads find candidate split points themselves) solves most problems anyway.

[bob]

There are multiple issues making limiting the number of threads at one split point beneficial.

(...)

I do allow everyone to split near the root with no limit, but nearer to the tips I impose a limit.

Yes, there can be a benefit near the tips, i.e. at the minimum split depth. Increasing min_split_depth will have roughly the same benefit.

Using a polling approach (i.e. idle threads find candidate split points themselves) solves most problems anyway.

They are not quite the same. Increasing min split depth stops ALL splitting below that point. Where as min_thread_group allows some but on a restricted basis.

I'm not sure how you are going to do polling in a recursive search. In an iterated search using a DTS-like approach, yes. I keep thinking about going back to an iterated search, but it is not as clean as recursive, overall.

If you are talking about "late join" (where an idle thread can join at an existing split point after the split has already been done) I have a version of Crafty that does that, but there is no benefit performance-wise I could measure, so I just archived the code in case I want to re-visit this at some point in the future.

[Desperado]

I'm not sure how you are going to do polling in a recursive search.

Where do you see the problem ? It is just a recursive call to the loop where helper threads are parked while there isn't any work.
Well, the helper threads poll within this loop anyway. A helping master just calls this loop too,
but will exit after a poll ( with success then after the search ) and jumps in and out as long as it is waiting.
Just like one of the pseudo code snippets above was showing.
Do i miss the context now ?

[syzygy]

I'm not sure how you are going to do polling in a recursive search. In an iterated search using a DTS-like approach, yes. I keep thinking about going back to an iterated search, but it is not as clean as recursive, overall.

I have explained this various times already, and again earlier in this thread.

Usually you say it is not possible, then I explain how to do it, then you say "but that's not recursive". Anyway, there is no fundamental difficulty at all. There is just one restriction: an idle master is restricted to helping its slaves. But even that can be overcome as I have pointed out above.

If you are talking about "late join" (where an idle thread can join at an existing split point after the split has already been done) I have a version of Crafty that does that, but there is no benefit performance-wise I could measure, so I just archived the code in case I want to re-visit this at some point in the future.

It's essentially "only join late, anywhere".

[Desperado]

Can someone please clarify the term late join.

For me it is simply a thread that joins the party after a group or single
thread is already working on the splitpoint, and it was not considered when
the splitpoint was opened.

Imo there is even no need that the master is the first thread that joins the
party. After the splitpoint has been setup it is flagged as open and does welcome any thread. If the work is done ( no moves left, stopped ) the splitpoint is closed,
which means the worst thing that can happen that the master is running through the SmpSearch() and frees the splitpoint ressource on the splitpoint stack without doing "real" work.
That means further that the splitpoint owner
does not poll for its own splitpoint. The polling is used only if a thread joins
somewhere as slave which includes a waiting master and is solved by a recursive call from the SmpSearch() to the polling function ( commonly named as idleLoop() ) while it is "waiting" ( == polling ).

[syzygy]

Can someone please clarify the term late join.

It just means that the thread is not assigned to the split point by the master of the split point at the time the master decides its current node is ready to become a split point.

For me it is simply a thread that joins the party after a group or single
thread is already working on the splitpoint, and it was not considered when
the splitpoint was opened.

We agree.

Imo there is even no need that the master is the first thread that joins the
party. After the splitpoint has been setup it is flagged as open and does welcome any thread. If the work is done ( no moves left, stopped ) the splitpoint is closed,
which means the worst thing that can happen that the master is running through the SmpSearch() and frees the splitpoint ressource on the splitpoint stack without doing "real" work.
That means further that the splitpoint owner
does not poll for its own splitpoint. The polling is used only if a thread joins
somewhere as slave which includes a waiting master and is solved by a recursive call from the SmpSearch() to the polling function ( commonly named as idleLoop() ) while it is "waiting" ( == polling ).

This is what I do, except that the master, after "opening up" the current node as split point, continues searching the node as normal. Another thread might "late join" the split point, but often that won't even happen.

[Desperado]

The ressource for the polling solution / logic can look like that.

Code: Select all

SingleSearch(tid)
{
  while( moves )
  {
     // continue single search
     SingleSearch()

     // moves are searched parallel
     if( DoSplit() )
     {
         Split(tid); 
         return;
     }
  }
}

Code: Select all

Split(tid)
{
  // Master
  s = TakeUpAnUsedSplitpoint();

  // Setup unused Splitpoint from Splitpoint stack
  SetSplitpointData(s);

  // this can be done within setting up the splitpoint
  // just to demonstrate
  s.open = true 
  
  // meanwhile slaves may have joined or solved the task

  // Master joins the party
  SmpSearch(tid,s);

  // Master disjoining splitpoint
  // Splitpoint is a free ressource now.
  Free(s);
}

Code: Select all

Poll(tid)
{
  while(true)
  {
    // Poll - join as slave
    join = GetSplitpointFromSplitpointStack();
    if( join )
    {
        SmpSearch(tid,join);
    }

   // Polling thread that should exit ( helping master )
   // To be a splitpoint owner means to be a master
   // A master loops from outside. See below SmpSearch().
   if( thread[tid].OwnsASplitpoint() )
   { return; }
  }
}

Code: Select all

SmpSearch(tid,s)
{
  while( SmpGetMoves() )
  {
      SingleSearch(tid);
  }
  s.open = false;

  // Waiting master
  if( Master() )
  {
     while( WaitingForSlaves() )
     {
       // Call Poll() recursively
       Poll(tid);
     }
  }
}

Comments ?

[bob]

I'm not sure how you are going to do polling in a recursive search.

Where do you see the problem ? It is just a recursive call to the loop where helper threads are parked while there isn't any work.
Well, the helper threads poll within this loop anyway. A helping master just calls this loop too,
but will exit after a poll ( with success then after the search ) and jumps in and out as long as it is waiting.
Just like one of the pseudo code snippets above was showing.
Do i miss the context now ?

He specifically said "idle threads find a split point." That's a problem because a thread really can't choose a split point in a recursive search, that is up to the thread that is actually searching...

[syzygy]

He specifically said "idle threads find a split point." That's a problem because a thread really can't choose a split point in a recursive search, that is up to the thread that is actually searching...

My recursive search has been doing it since October 2012 or so.

[bob]

He specifically said "idle threads find a split point." That's a problem because a thread really can't choose a split point in a recursive search, that is up to the thread that is actually searching...

My recursive search has been doing it since October 2012 or so.

How does an idle thread force a split with a thread that is busy? Unless you use what I consider an inefficient approach where you create arbitrary split points in the busy thread hoping that one or more might actually be used?

In a DTS-like approach it is trivial since there is no call stack to deal with and all threads can see/modify everything in the search.

Perhaps we are talking about two different things, as I don't see how thread B can split with thread A whenever B chooses. A's call stack is already established to take it back ply by ply using a non-sharable block of memory to maintain the position... Being able to do that would essentially result in a recursive DTS algorithm, which seems difficult unless the extra split blocks are dribbled around hoping to catch a thread later.

No way I want to incur that kind of overhead.