Allow a slave to 'late join' another splitpoint

Instead of waiting to be allocated, actively search
for another split point to join when finishes its
search. Also modify split conditions.

This patch has been tested with 7 threads SMP and
passed both STC:

LLR: 2.97 (-2.94,2.94) [-1.50,4.50]
Total: 2885 W: 519 L: 410 D: 1956

And a reduced-LTC at  25+0.05
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 4401 W: 684 L: 566 D: 3151

Was then retested against regression in 3 thread case
at standard LTC of  60+0.05:

LLR: 2.96 (-2.94,2.94) [-4.00,0.00]
Total: 40809 W: 5446 L: 5406 D: 29957

bench: 8802105

diff --git a/src/search.cpp b/src/search.cpp
index fbe6b2c052fa3fee50e7f98bcf37639134e438a1..60d1a86866d74b4cd3753cdc3df80ff78c525fd5 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -984,8 +984,10 @@ moves_loop: // When in check and at SpNode search starts from here
 
       // Step 19. Check for splitting the search
       if (   !SpNode
+          &&  Threads.size() >= 2
           &&  depth >= Threads.minimumSplitDepth
-          &&  Threads.available_slave(thisThread)
+          &&  (   !thisThread->activeSplitPoint
+               || !thisThread->activeSplitPoint->allowLatejoin)
           &&  thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
       {
           assert(bestValue > -VALUE_INFINITE && bestValue < beta);
@@ -1527,9 +1529,9 @@ void Thread::idle_loop() {
 
           assert(searching);
 
-          searching = false;
           activePosition = NULL;
           sp->slavesMask.reset(idx);
+          sp->allowLatejoin = false;
           sp->nodes += pos.nodes_searched();
 
           // Wake up the master thread so to allow it to return from the idle
@@ -1547,6 +1549,10 @@ void Thread::idle_loop() {
           // the sp master. Also accessing other Thread objects is unsafe because
           // if we are exiting there is a chance that they are already freed.
           sp->mutex.unlock();
+
+          // Try to late join to another splitpoint
+          if (Threads.size() <= 2 || !attempt_to_latejoin()) // FIXME: attempt_to_latejoin() is theoretically unsafe when were are exiting the program...
+              searching = false;
       }
 
       // If this thread is the master of a split point and all slaves have finished
@@ -1562,6 +1568,44 @@ void Thread::idle_loop() {
   }
 }
 
+bool Thread::attempt_to_latejoin()
+{
+    SplitPoint *sp;
+    size_t i;
+    bool success = false;
+
+    for (i = 0; i < Threads.size(); ++i)
+    {
+        int size = Threads[i]->splitPointsSize; // Make a local copy to prevent size from changing under our feet.
+
+        sp = size ? &Threads[i]->splitPoints[size - 1] : NULL;
+
+        if (   sp
+            && sp->allowLatejoin
+            && available_to(Threads[i], true))
+            break;
+    }
+
+    if (i == Threads.size())
+        return false; // No suitable splitpoint found!
+
+    // Recheck conditions under lock protection
+    Threads.mutex.lock();
+    sp->mutex.lock();
+
+    if (   sp->allowLatejoin
+        && available_to(Threads[i], true))
+    {
+         activeSplitPoint = sp;
+         sp->slavesMask.set(this->idx);
+         success = true;
+    }
+
+    sp->mutex.unlock();
+    Threads.mutex.unlock();
+
+    return success;
+}
 
 /// check_time() is called by the timer thread when the timer triggers. It is
 /// used to print debug info and, more importantly, to detect when we are out of

diff --git a/src/thread.cpp b/src/thread.cpp
index 432d573d42ce2b2746a1f11cac6610979d8097ba..f5aab2b13366e3a3850dfb2979080d489c33b648 100644 (file)
--- a/src/thread.cpp
+++ b/src/thread.cpp
@@ -112,9 +112,9 @@ bool Thread::cutoff_occurred() const {
 // which are busy searching the split point at the top of slave's split point
 // stack (the "helpful master concept" in YBWC terminology).
 
-bool Thread::available_to(const Thread* master) const {
+bool Thread::available_to(const Thread* master, bool latejoin) const {
 
-  if (searching)
+  if (searching && !latejoin)
       return false;
 
   // Make a local copy to be sure it doesn't become zero under our feet while
@@ -239,7 +239,7 @@ void ThreadPool::read_uci_options() {
 Thread* ThreadPool::available_slave(const Thread* master) const {
 
   for (const_iterator it = begin(); it != end(); ++it)
-      if ((*it)->available_to(master))
+      if ((*it)->available_to(master, false))
           return *it;
 
   return NULL;
@@ -292,6 +292,7 @@ void Thread::split(Position& pos, const Stack* ss, Value alpha, Value beta, Valu
   Threads.mutex.lock();
   sp.mutex.lock();
 
+  sp.allowLatejoin = true; // Only set this under lock protection
   ++splitPointsSize;
   activeSplitPoint = &sp;
   activePosition = NULL;

diff --git a/src/thread.h b/src/thread.h
index 44aa68835f892a56113f58de9a2a4f1d6ba6d2bd..edc4ee31833d38a0779f39233a8db280e9983ab4 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -77,6 +77,7 @@ struct SplitPoint {
   // Shared data
   Mutex mutex;
   std::bitset<MAX_THREADS> slavesMask;
+  volatile bool allowLatejoin;
   volatile uint64_t nodes;
   volatile Value alpha;
   volatile Value bestValue;
@@ -113,8 +114,9 @@ struct Thread : public ThreadBase {
 
   Thread();
   virtual void idle_loop();
+  bool attempt_to_latejoin();
   bool cutoff_occurred() const;
-  bool available_to(const Thread* master) const;
+  bool available_to(const Thread* master, bool latejoin) const;
 
   template <bool Fake>
   void split(Position& pos, const Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,