Allow a slave to 'late join' another splitpoint
authorJoona Kiiski <joona.kiiski@gmail.com>
Sat, 3 May 2014 17:29:31 +0000 (18:29 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Wed, 7 May 2014 06:38:56 +0000 (08:38 +0200)
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

src/search.cpp
src/thread.cpp
src/thread.h

index fbe6b2c052fa3fee50e7f98bcf37639134e438a1..60d1a86866d74b4cd3753cdc3df80ff78c525fd5 100644 (file)
@@ -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
index 432d573d42ce2b2746a1f11cac6610979d8097ba..f5aab2b13366e3a3850dfb2979080d489c33b648 100644 (file)
@@ -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;
index 44aa68835f892a56113f58de9a2a4f1d6ba6d2bd..edc4ee31833d38a0779f39233a8db280e9983ab4 100644 (file)
@@ -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,