Active Reparenting

In Young Brothers Wait Concept (YBWC) available slaves are
booked by the split point master, then start to search below
the assigned split point and, once finished, return in idle
state waiting to be booked by another master.

This patch introduces "Active Reparenting" so that when a
slave finishes its job on the assigned split point, instead
of passively waiting to be booked, searches a suitable active
split point and reprents itselfs to that split point. Then
immediately starts to search below the split point in exactly
the same way of the others split point's slaves. This reduces
to zero the time waiting in idle loop and should increase
scalability especially whit many (8 or more) cores.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/search.cpp b/src/search.cpp
index 1d06dbd05748d75073647c544a603171e1b5a89b..ad3898c14af9cbe3faf7727ddb4146661691e0b8 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1859,6 +1859,49 @@ void Thread::idle_loop(SplitPoint* sp_master) {
           // our feet by the sp master. Also accessing other Thread objects is
           // unsafe because if we are exiting there is a chance are already freed.
           lock_release(sp->lock);
+
+          // Try to reparent to another split point. Only for slave threads
+          // that are not master of any active split point.
+          if (   !sp_master
+              && !is_searching
+              && !do_sleep
+              && !do_exit
+              && !splitPointsCnt
+              && Threads.size() > 2)
+          {
+              for (int i = 0; i < Threads.size(); i++)
+              {
+                  SplitPoint* oldest = &Threads[i].splitPoints[0];
+
+                  // Find the first oldest split point with still all slaves running
+                  if (   Threads[i].splitPointsCnt
+                      && oldest->slavesMask == oldest->allSlavesMask
+                      && !single_bit(oldest->allSlavesMask))
+                  {
+                      lock_grab(oldest->lock);
+                      lock_grab(Threads.splitLock); // Needed by is_searching
+
+                      // Retest all under lock protection, we are in the middle
+                      // of a race storm !
+                      if (   !is_searching
+                          && !do_sleep
+                          && !do_exit
+                          && Threads[i].splitPointsCnt
+                          && oldest->slavesMask == oldest->allSlavesMask
+                          && !single_bit(oldest->allSlavesMask))
+                      {
+                          oldest->slavesMask |= 1ULL << idx; // allSlavesMask is not updated
+                          curSplitPoint = oldest;
+                          is_searching = true;
+                      }
+
+                      lock_release(Threads.splitLock);
+                      lock_release(oldest->lock);
+
+                      break; // Exit anyhow, only one try (enough in 99% of cases)
+                  }
+              }
+          }
       }
   }
 }

diff --git a/src/thread.cpp b/src/thread.cpp
index cb3f8223aacf26a93199c7c2ed6cef1b8a02916c..6d07ec35f3e29d1e83295c7417481dac7c9ffead 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -319,6 +319,7 @@ Value ThreadsManager::split(Position& pos, Stack* ss, Value alpha, Value beta,
   sp->master = master;
   sp->cutoff = false;
   sp->slavesMask = 1ULL << master->idx;
+  sp->allSlavesMask = 1ULL << master->idx;
   sp->depth = depth;
   sp->bestMove = *bestMove;
   sp->threatMove = threatMove;
@@ -347,6 +348,7 @@ Value ThreadsManager::split(Position& pos, Stack* ss, Value alpha, Value beta,
       if (threads[i]->is_available_to(master))
       {
           sp->slavesMask |= 1ULL << i;
+          sp->allSlavesMask |= 1ULL << i;
           threads[i]->curSplitPoint = sp;
           threads[i]->is_searching = true; // Slave leaves idle_loop()
 
@@ -354,7 +356,10 @@ Value ThreadsManager::split(Position& pos, Stack* ss, Value alpha, Value beta,
               threads[i]->wake_up();
 
           if (++slavesCnt + 1 >= maxThreadsPerSplitPoint) // Master is always included
+          {
+              sp->allSlavesMask = 0; // Disable reparenting to this split point
               break;
+          }
       }
 
   lock_release(splitLock);

diff --git a/src/thread.h b/src/thread.h
index 3eb8fc9cfe4d8f001a5ae8a4d4685a39cc6539f5..d60dd5f7fbc4d3a11ec3c243a96940fce619be3e 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -51,6 +51,7 @@ struct SplitPoint {
   // Shared data
   Lock lock;
   volatile uint64_t slavesMask;
+  volatile uint64_t allSlavesMask;
   volatile int64_t nodes;
   volatile Value alpha;
   volatile Value bestValue;

diff --git a/src/types.h b/src/types.h
index 5b5bc1f227785d6a80b1d7a57e936bfd44df6cae..9c997418afa28d4cf4a38ed35989887d11599709 100644 (file)
--- a/src/types.h
+++ b/src/types.h
@@ -325,7 +325,6 @@ const Value QueenValueEndgame  = Value(0x9FE);
 extern const Value PieceValueMidgame[17]; // Indexed by Piece or PieceType
 extern const Value PieceValueEndgame[17];
 extern int SquareDistance[64][64];
-extern uint8_t BitCount8Bit[256];
 
 inline Color operator~(Color c) {
   return Color(c ^ 1);