From 44432f67d724573d0f6e3cfea6165c9b1d125d72 Mon Sep 17 00:00:00 2001
From: Marco Costalba <mcostalba@gmail.com>
Date: Tue, 10 Apr 2012 18:00:31 +0100
Subject: [PATCH] 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>
---
 src/search.cpp | 43 +++++++++++++++++++++++++++++++++++++++++++
 src/thread.cpp |  5 +++++
 src/thread.h   |  1 +
 src/types.h    |  1 -
 4 files changed, 49 insertions(+), 1 deletion(-)

diff --git a/src/search.cpp b/src/search.cpp
index 1d06dbd0..ad3898c1 100644
--- 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 cb3f8223..6d07ec35 100644
--- 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 3eb8fc9c..d60dd5f7 100644
--- 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 5b5bc1f2..9c997418 100644
--- 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);
-- 
2.39.2