Active Reparenting
authorMarco Costalba <mcostalba@gmail.com>
Tue, 10 Apr 2012 17:00:31 +0000 (18:00 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Tue, 10 Apr 2012 17:22:58 +0000 (18:22 +0100)
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>
src/search.cpp
src/thread.cpp
src/thread.h
src/types.h

index 1d06dbd..ad3898c 100644 (file)
@@ -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)
+                  }
+              }
+          }
       }
   }
 }
index cb3f822..6d07ec3 100644 (file)
@@ -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);
index 3eb8fc9..d60dd5f 100644 (file)
@@ -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;
index 5b5bc1f..9c99741 100644 (file)
@@ -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);