WebSVN – Games.Chess Giants – Diff – /engine-crafty/thread.c

 #include "data.h"
 #include "epdglue.h"
+#if (CPUS > 1)
-/* modified 04/30/14 */
+/* modified 11/04/15 */
 /*
  *******************************************************************************
  *                                                                             *
- *   Thread() is the driver for the threaded parallel search in Crafty.  The   *
+ *   Split() is the driver for the threaded parallel search in Crafty.  The    *
  *   basic idea is that whenever we notice that one (or more) threads are in   *
- *   their idle loop, we drop into thread, from Search(), and begin a new      *
+ *   their idle loop, we drop into Split(), from Search(), and begin a new     *
- *   parallel search from this node.  This is simply a problem of copying the  *
+ *   parallel search from this node.  This is simply a problem of establishing *
+ *   a new split point, and then letting each thread join this split point and *
+ *   copy whatever data they need.                                             *
+ *                                                                             *
+ *   This is generation II of Split().  The primary differences address two    *
+ *   specific performance-robbing issues.  (1) Excessive waiting for a split   *
+ *   to be done, and (b) excessive waiting on specific locks.  Generation II   *
+ *   addresses both of these to significantly improve performance.             *
+ *                                                                             *
+ *   The main difference between Gen I and Gen II is the effort required to    *
- *   search state space for each thread working at this node, then sending     *
+ *   split the tree and which thread(s) expend this effort.  In generation I,  *
+ *   the parent thread was responsible for allocating a split block for each   *
+ *   child thread, and then copying the necessary data from the parent split   *
+ *   block to these child split blocks.  When all of this was completed, the   *
+ *   child processes were released to start the parallel search after being    *
+ *   held while the split / copy operations were done.  In the generation II   *
+ *   Split() we now simply allocate a new split block for THIS thread, flag    *
+ *   the parent split block as joinable, and then go directly to ThreadWait()  *
+ *   which will drop us back in to the search immediately.  The idle threads   *
+ *   are continually looping on Join() which will jump them right into this    *
+ *   split block letting them do ALL the work of allocating a split block,     *
+ *   filling it in, and then copying the data to their local split block.      *
+ *   This distributes the split overhead among all the threads that split,     *
+ *   rather than this thread having to do all the work while the other threads *
+ *   sit idle.                                                                 *
+ *                                                                             *
+ *   Generation II is also much more lightweight, in that it copies only the   *
+ *   bare minimum from parent to child.  Generation I safely copied far too    *
+ *   much since this code was being changed regularly, but that is no longer   *
+ *   necessary overhead.                                                       *
+ *                                                                             *
+ *   Generation II has a zero contention split algorithm.  In the past, when a *
+ *   thread became idle, it posted a global split request and any thread that  *
+ *   was at an appropriate point would try to split.  But while it was doing   *
+ *   the splitting, other threads that were also willing to split would "get   *
+ *   in line" because Crafty used a global lock to prevent two threads from    *
+ *   attempting to split at the same instant in time.  They got in line, and   *
+ *   waited for the original splitter to release the lock, but now they have   *
+ *   no idle threads to split with.  A waste of time.  Now we allow ANY thread *
+ *   to attempt to split at the current ply.  When we do what might be called  *
+ *   a "gratuitous split" the only restriction is that if we have existing     *
+ *   "gratuitous split points" (split blocks that are joinable but have not    *
+ *   yet been joined), then we limit the number of such splits (per thread) to *
+ *   avoid excessive overhead.                                                 *
+ *                                                                             *
+ *   Generation II takes another idea from DTS, the idea of "late-join".  The  *
+ *   idea is fairly simple.  If, when a thread becomes idle, there are already *
+ *   other split points being searched in parallel, then we will try to join   *
+ *   one of them rather than waiting for someone to ask us to help.  We use    *
+ *   some simple criteria:  (1) The split point must be joinable, which simply *
+ *   means that no processor has exited the split point yet (which would let   *
+ *   us know there is no more work here and a join would be futile);  (2) We   *
+ *   compute an "interest" value which is a simple formula based on depth at   *
+ *   the split point, and the number of moves already searched.  It seems less *
+ *   risky to choose a split point with max depth AND minimum moves already    *
- *   everyone off to SearchParallel() to search this node in parallel.         *
+ *   searched so that there is plenty to do.  This was quite simple to add     *
+ *   after the rest of the Generation II rewrite.  In fact, this is now THE    *
+ *   way threads join a split point, period, which further simplifies the code *
+ *   and improves efficiency.  IE, a thread can split when idle threads are    *
+ *   noticed, or if it is far enough away from the tips to make the cost       *
+ *   negligible.  At that point any idle thread(s) can join immediately, those *
+ *   that become idle later can join when they are ready.                      *
  *                                                                             *
  *   There are a number of settable options via the command-line or .craftyrc  *
  *   initialization file.  Here's a concise explanation for each option and an *
  *   occasional suggestion for testing/tuning.                                 *
+ *                                                                             *
+ *   smp_affinity (command = smpaffinity=<n> is used to enable or disable      *
+ *      processor affinity.  -1 disables affinity and lets threads run on any  *
+ *      available core.  If you use an integer <n> then thread zero will bind  *
+ *      itself to cpu <n> and each additional thread will bind to the next     *
+ *      higher cpu number.  This is useful if you try to run two copies of     *
+ *      crafty on the same machine, now you can cause one to bind to the first *
+ *      <n> cores, and the second to the last <n> cores.  For the first        *
+ *      instance of Crafty, you would use smpaffinity=0, and for the second    *
+ *      smpaffinity=8, assuming you are running 8 threads per copy on a 16 cpu *
+ *      machine.  If you get this wrong, you can have more than one thread on  *
+ *      the same cpu which will significantly impact performance.              *
  *                                                                             *
  *   smp_max_threads (command = smpmt=n) sets the total number of allowable    *
  *      threads for the search.  The default is one (1) as Crafty does not     *
  *      assume it should use all available resources.  For optimal performance *
  *      this should be set to the number of physical cores your machine has,   *
  *      which does NOT include hyperthreaded cores.                            *
  *                                                                             *
  *   smp_split_group (command = smpgroup=n) sets the maximum number of threads *
- *      at any single split point, with the exception of split points where    *
+ *      at any single split point, with the exception of split points fairly   *
- *      ply <= 4 where ALL threads are allowed to split together ignoring this *
+ *      close to the root where ALL threads are allowed to split together,     *
+ *      ignoring this limit.  Note that this is ignored in the first 1/2 of    *
+ *      the tree (the nodes closer to the root).  There it is actually good to *
- *      limit.                                                                 *
+ *      split and get all active threads involved.                             *
  *                                                                             *
  *   smp_min_split_depth (command = smpmin=n) avoids splitting when remaining  *
  *      depth < n.  This is used to balance splitting overhead cost against    *
- *      the speed gain the parallel search produes.  The default is currently  *
+ *      the speed gain the parallel search produces.  The default is currently *
  *      5 (which could change with future generations of Intel hardware) but   *
  *      values between 4 and 8 will work.  Larger values allow somewhat fewer  *
  *      splits, which reduces overhead, but it also increases the percentage   *
  *      of the time where a thread is waiting on work.                         *
  *                                                                             *
- *   smp_split_nodes (command = smpnodes=n) will not allow a thread to split   *
- *      until it has searched at least N nodes, to prevent excessive splitting *
- *      out near the tips in endgames.  The default is 2000.  Larger values    *
- *      will reduce splitting overhead but will increase the amoutn of time    *
- *      a thread is waiting on work.                                           *
- *                                                                             *
- *   smp_split_at_root (command=smproot=0 or 1) enables (1) or disables (0)    *
+ *   smp_split_at_root (command = smproot=0 or 1) enables (1) or disables (0)  *
  *      splitting the tree at the root.  This defaults to 1 which produces the *
  *      best performance by a signficiant margin.  But it can be disabled if   *
  *      you are playing with code changes.                                     *
  *                                                                             *
+ *   smp_gratuitous_depth (command = smpgd=<n>) controls " gratuitous splits"  *
+ *      which are splits that are done without any idle threads.  This sets a  *
+ *      depth limit (remaining depth) that must be present before such a split *
+ *      can be done.  Making this number larger will reduce the number of      *
+ *      these splits.  Making it too small will increase overhead slightly and *
+ *      increase split block usage significantly.                              *
+ *                                                                             *
+ *   smp_gratuitous_limit (command = smpgl=<n>) limits the number of these     *
- *   The best way to tune any of these parameters is to run SEVERAL test cases *
+ *      splits that a thread can do.  Once a thread has this number of         *
+ *      unjoined split points, it will not be allowed to split any more until  *
- *   (positions) with max threads set.  Run each set of positions several      *
+ *      one or more threads join at least one of the existing split points.    *
- *   times with each parameter change you want to try (do them ONE at a time   *
+ *      In the smp search statistics, where you see output that looks like     *
+ *      this:                                                                  *
+ *                                                                             *
+ *        splits=m(n) ...                                                      *
- *   for obvious reasons).  Pick the value with the smallest overall search    *
+ *                                                                             *
- *   time.  The more cores you use, the more times you should run each test,   *
+ *      m is the total splits done, n is the number of "wasted splits" which   *
- *   since parallel search is highly non-deterministic and you need several    *
+ *      are basically gratuitous splits where no thread joined before this     *
+ *      split point was completed and deallocated.                             *
- *   runs to get a reasonable average.                                         *
+ *                                                                             *
+ *   The best way to tune all of these paramenters is to use the "autotune"    *
+ *   command (see autotune.c and help autotune) which will automatically run   *
+ *   tests and optimize the parameters.  More details are in the autotune.c    *
+ *   source file.                                                              *
  *                                                                             *
  *   A few basic "rules of the road" for anyone interested in changing or      *
  *   adding to any of this code.                                               *
  *                                                                             *
  *   1.  If, at any time, you want to modify your private split block, no lock *
  *       is required.                                                          *
  *                                                                             *
  *   2.  If, at any time, you want to modify another split block, such as the  *
  *       parent split block shared move list, you must acquire the lock in the *
- *       split block first.  IE (tree->parent->lock to lock the parent split   *
+ *       split block first.  IE tree->parent->lock to lock the parent split    *
- *       block during NextMove() and such).  Note that this ONLY applies to    *
+ *       block during NextMove() and such.                                     *
- *       search-related data, NOT the SMP data within the split block (parent  *
- *       pointer, sibling pointers, number of processors working here, etc).   *
- *       Modifying those falls under the next lock below.                      *
  *                                                                             *
- *   3.  If you want to modify any SMP-related data, such as allocating a      *
+ *   3.  If you want to modify any SMP-related data that spans multiple split  *
- *       split block, or telling sibling processes to stop, etc, then you must *
+ *       blocks, such as telling sibling processes to stop, etc, then you must *
- *       acquire the global "smp_lock" lock first.  This prevents any sort of  *
+ *       acquire the global "lock_smp" lock first.  This prevents a deadlock   *
- *       race condition that could corrupt the split block tree organization.  *
+ *       caused by two different threads walking the split block chain from    *
- *       This applies to ANY smp-related variable from the simple smp_idle     *
+ *       different directions, and acquiring the split block locks in          *
+ *       different orders, which could cause a catastrophic deadlock to occur. *
- *       variable through the various sibling chains and such.                 *
+ *       This is an infrequent event so the overhead is not significant.       *
  *                                                                             *
  *   4.  If you want to do any sort of I/O operation, you must acquire the     *
  *       "lock_io" lock first.  Since threads share descriptors, there are     *
  *       lots of potential race conditions, from the simple tty-output getting *
  *       interlaced from different threads, to outright data corruption in the *
  *       book or log files.                                                    *
- *                                                                             *
- *   5.  There is a specific "lock_split" that is used to prevent a lot of     *
- *       queued waiting to do splits, but it is unlikely that lock would ever  *
- *       be used anywhere other than where it is currently accessed in         *
- *       Search() at the parallel split initiation code.                       *
- *                                                                             *
- *   6.  If you want to alter the root move list, you must first acquire       *
- *       lock_root, since the root move list is shared and multiple threads    *
- *       can attempt to modify it at the same time.  Overlooking this can      *
- *       result in a corrupted root move list with one or more moves missing   *
- *       or duplicated.                                                        *
  *                                                                             *
  *   Some of the bugs caused by failing to acquire the correct lock will only  *
  *   occur infrequently, and they are extremely difficult to find.  Some only  *
  *   show up in a public game where everyone is watching, to cause maximum     *
  *   embarassment and causes the program to do something extremely stupid.     *
  *                                                                             *
  *******************************************************************************
  */
-int Thread(TREE * RESTRICT tree) {
+int Split(TREE * RESTRICT tree) {
+  TREE *child;
-  int proc, tsplit = 0, nblocks = 0;
+  int tid, tstart, tend;
 /*
  ************************************************************
  *                                                          *
- *  First, we make sure that there are idle threads. It is  *
+ *  Here we prepare to split the tree.  All we really do in *
+ *  the Generation II threading is grab a split block for   *
- *  possible that we get here after they have all been      *
+ *  this thread, then flag the parent as "joinable" and     *
+ *  then jump right to ThreadWait() to resume where we left *
+ *  off, with the expectation (but not a requirement) that  *
+ *  other threads will join us to help.                     *
+ *                                                          *
+ *  Idle threads are sitting in ThreadWait() repeatedly     *
+ *  calling Join() to find them a split point, which we are *
+ *  fixing to provide.  They will then join as quickly as   *
- *  claimed by another thread.  In that case we return.     *
+ *  they can, and other threads that become idle later can  *
+ *  also join without any further splitting needed.         *
+ *                                                          *
+ *  If we are unable to allocate a split block, we simply   *
+ *  abort this attempted split and return to the search     *
+ *  since other threads will also split quickly.            *
  *                                                          *
  ************************************************************
  */
+  tstart = ReadClock();
-  Lock(lock_smp);
+  tree->nprocs = 0;
-  for (proc = 0; proc < smp_max_threads && !thread[proc].idle; proc++);
+  for (tid = 0; tid < (int) smp_max_threads; tid++) // Pierre-Marie Baty -- added type cast
-  if (proc == smp_max_threads) {
+    tree->siblings[tid] = 0;
-    smp_split = 0;
+  child = GetBlock(tree, tree->thread_id);
-    Unlock(lock_smp);
+  if (!child)
     return 0;
+  CopyFromParent(child);
+  thread[tree->thread_id].tree = child;
+  tree->joined = 0;
+  tree->joinable = 1;
+  parallel_splits++;
-  }
+  smp_split = 0;
+  tend = ReadClock();
+  thread[tree->thread_id].idle += tend - tstart;
 /*
  ************************************************************
  *                                                          *
+ *  We have successfully created a split point, which means *
- *  Now we start copying the current "state" from this      *
+ *  we are done.  The instant we set the "joinable" flag,   *
+ *  idle threads may begin to join in at this split point   *
+ *  to help.  Since this thread may finish before any or    *
- *  thread into new thread blocks so that the threads can   *
+ *  all of the other parallel threads, this thread is sent  *
- *  search this position without interfering with each      *
+ *  to ThreadWait() which will immediately send it to       *
+ *  SearchMoveList() like the other threads; however, going *
+ *  to ThreadWait() allows this thread to join others if it *
+ *  runs out of work to do.  We do pass ThreadWait() the    *
+ *  address of the parent split block, so that if this      *
- *  other.  As we copy, we link those blocks as siblings of *
+ *  thread becomes idle, and this thread block shows no     *
+ *  threads are still busy, then this thread can return to  *
+ *  here and then back up into the previous ply as it       *
- *  the parent node, and point each sibling back to the     *
+ *  should.  Note that no other thread can back up to the   *
- *  parent so we can unwind this confusion as the threads   *
+ *  previous ply since their recursive call stacks are not  *
+ *  set for that, while this call stack will bring us back  *
+ *  to this point where we return to the normal search,     *
- *  complete their work.                                    *
+ *  which we just completed.                                *
  *                                                          *
+ ************************************************************
+ */
+  ThreadWait(tree->thread_id, tree);
+  if (!tree->joined)
+    parallel_splits_wasted++;
+  return 1;
+}
+/* modified 12/16/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   Join() is called just when we enter the usual spin-loop waiting for work. *
- *  CopyToChild() allocates a split block optimally (see    *
+ *   We take a quick look at all active split blocks to see if any look        *
+ *   "joinable".  If so, we compute an "interest" value, which will be defined *
+ *   below.  We then join the most interesting split point directly. This      *
+ *   split point might have been created specifically for this thread to join, *
+ *   or it might be one that was already active when this thread became idle,  *
- *  that code for an explanation) and then copies anything  *
+ *   which allows us to join that existing split point and not request a new   *
- *  necessary for the parallel search.                      *
+ *   split operation, saving time.                                             *
+ *                                                                             *
+ *******************************************************************************
+ */
+int Join(int64_t tid) {
+  TREE *tree, *join_block, *child;
+  int interest, best_interest, current, pass = 0;
+/*
+ ************************************************************
  *                                                          *
- *  Special case 1:  In the loop to allocate a split block  *
- *  and copy current data to the new child thread, we skip  *
- *  over the current splitting thread's data.  After the    *
- *  loop we then explicitly allocate a block for this       *
+ *  First we pass over ALL split blocks, looking for those  *
- *  thread so that it will be included in the thread group  *
+ *  flagged as "joinable" (which means they are actually    *
- *  (remember that this thread is the one that has to back  *
+ *  active split points and that no processor at that split *
- *  up through the split block, so it will always call      *
- *  ThreadWait() telling it to do so.  There was a peculiar *
- *  condition that caused an inefficiency.  If we are at    *
- *  a depth where we honor the smp_split_group limit, it is *
+ *  point has run out of work (there is no point in joining *
- *  possible that on occasion, there could be so many idle  *
+ *  a split point with no remaining work) and no fail high  *
- *  processors that we would not include ourself.  For      *
+ *  has been found which would raise the "stop" flag.) This *
- *  example, suppose we are thread 6, and when we enter     *
+ *  is "racy" because we do not acquire any locks, which    *
- *  Thread() to do the split, threads 0-5 are idle, and     *
+ *  means that the busy threads continue working, and there *
- *  smp_split_group = 6.  We would pick up the first 6 idle *
+ *  is a small probability that the split point will        *
- *  threads and sic them on this split point, but we would  *
+ *  disappear while we are in this loop.  To resolve the    *
- *  fail to include ourself.  We would hit ThreadWait()     *
+ *  potential race, after we find the most attractive split *
- *  with no work to do, and then split somewhere else.      *
+ *  point, we acquire the lock for that split block and     *
- *  Unfortunately, THIS thread is the one that needs to     *
+ *  test again, but this time if the block is joinable, we  *
- *  wait for all the other threads to complete so that it   *
+ *  can safely join under control of the lock, which is not *
- *  can back up to the previous ply.  But if it is busy on  *
+ *  held for very long at all.  If the block is not         *
- *  another split point, it won't be able to return to this *
+ *  joinable once we acquire the lock, we abort joining     *
- *  point until it is idle.  Which means progress at this   *
+ *  since it is futile.  Note that if this happens, we will *
- *  split point is held up.  We now forcefully include the  *
+ *  try to find an existing split point we can join three   *
- *  current thread, and only include smp_split_group - 1    *
+ *  times before we exit, setting split to 1 to ask other   *
- *  other threads to work here with this thread.            *
+ *  threads to produce more candidate split points.         *
  *                                                          *
+ ************************************************************
+ */
+  for (pass = 0; pass < 3; pass++) {
+    best_interest = -999999;
+    join_block = 0;
+    for (current = 0; current <= (int) smp_max_threads * 64; current++) { // Pierre-Marie Baty -- added type cast
+      tree = block[current];
+      if (tree->joinable && (tree->ply <= tree->depth / 2 ||
+              tree->nprocs < (int) smp_split_group)) { // Pierre-Marie Baty -- added type cast
+        interest = tree->depth * 2 - tree->searched[0];
+        if (interest > best_interest) {
+          best_interest = interest;
+          join_block = tree;
+        }
+      }
+    }
+/*
+ ************************************************************
+ *                                                          *
+ *  Now we acquire the lock for this split block, and then  *
- *  Special case 2:  it is possible that there are no split *
+ *  check to see if the block is still flagged as joinable. *
+ *  If so, we set things up, and then we get pretty tricky  *
- *  blocks available.  In that case, CopyToChild() will     *
+ *  as we then release the lock, and then copy the data     *
- *  terminate Crafty with a log-file error message telling  *
+ *  from the parent to our split block.  There is a chance  *
- *  the user to re-compile with a larger number of split    *
+ *  that while we are copying this data, the split point    *
+ *  gets completed by other threads.  Which would leave an  *
+ *  apparent race condition exposed where we start copying  *
- *  blocks (the probability of this actually happening is   *
+ *  data here, the split point is completed, the parent     *
- *  incredibly small, but it is non-zero.  We use a VERY    *
+ *  block is released and then reacquired and we continue   *
+ *  if nothing has happened here, getting data copied from  *
- *  liberal estimate for the number of split blocks to      *
+ *  two different positions.                                *
- *  allocate to avoid this.)                                *
+ *                                                          *
+ *  Fortunately, we linked this new split block to the old  *
+ *  (original parent).  If that split block is released, we *
+ *  will discover this because that operation will also set *
+ *  our "stop" flag which will prevent us from using this   *
+ *  data and breaking things.  We allow threads to copy     *
+ *  this data without any lock protection to eliminate a    *
+ *  serialization (each node would copy the data serially,  *
+ *  rather than all at once) with the only consequence to   *
+ *  this being the overhead of copying and then throwing    *
+ *  the data away, which can happen on occasion even if we  *
+ *  used a lock for protection, since once we release the   *
+ *  lock it still takes time to get into the search and we  *
+ *  could STILL find that this split block has already been *
+ *  completed, once again.  Less contention and serial      *
+ *  computing improves performance.                         *
  *                                                          *
  ************************************************************
  */
+    if (join_block) {
+      Lock(join_block->lock);
+      if (join_block->joinable) {
+        child = GetBlock(join_block, (int) tid); // Pierre-Marie Baty -- added type cast
-  thread[tree->thread_id].tree = 0;
+        Unlock(join_block->lock);
-  tree->nprocs = 0;
+        if (child) {
-  for (proc = 0; proc < smp_max_threads; proc++) {
+          CopyFromParent(child);
-    tree->siblings[proc] = 0;
+          thread[tid].tree = child;
-    if (thread[proc].idle) {
+          parallel_joins++;
-      CopyToChild(tree, proc);
+          return 1;
+        }
-      nblocks++;
+      } else {
-      if (nblocks >= smp_split_group && tree->ply > tree->depth / 2)
+        Unlock(join_block->lock);
         break;
+      }
+    }
+  }
-  CopyToChild(tree, tree->thread_id);
-  nblocks++;
 /*
  ************************************************************
  *                                                          *
- *  Everything is set.  Now we can stuff the address of the *
+ *  We did not acquire a split point to join, so we set     *
- *  thread blocks into thread[i].tree so that those idle    *
+ *  smp_split to 1 to ask busy threads to create joinable   *
- *  threads can begin the parallel search.  We also flag    *
- *  them as "not idle" so that a split immediately after we *
- *  exit won't try to pick them up again, breaking things.  *
+ *  split points.                                           *
  *                                                          *
  ************************************************************
  */
-  parallel_splits++;
+  smp_split = 1;
+  return 0;
+}
+/* modified 11/04/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   ThreadInit() is called after a process is created.  Its main task is to   *
+ *   initialize the process local memory so that it will fault in and be       *
+ *   allocated on the local node rather than the node where the original       *
+ *   (first) process was running.  All threads will hang here via a custom     *
+ *   WaitForALlThreadsInitialized() procedure so that all the local thread     *
+ *   blocks are usable before the search actually begins.                      *
+ *                                                                             *
+ *******************************************************************************
+ */
+void *STDCALL ThreadInit(void *t) {
+  int tid = (int64_t) t;
+  ThreadAffinity(tid);
+#  if !defined(UNIX)
+  ThreadMalloc((uint64_t) tid);
+#  endif
-  for (proc = 0; proc < smp_max_threads; proc++)
+  thread[tid].blocks = 0xffffffffffffffffull;
+  Lock(lock_smp);
+  initialized_threads++;
+  Unlock(lock_smp);
+  WaitForAllThreadsInitialized();
+  ThreadWait(tid, (TREE *) 0);
+  Lock(lock_smp);
+  smp_threads--;
+  Unlock(lock_smp);
+  return 0;
+}
+/* modified 01/08/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   ThreadAffinity() is called to "pin" a thread to a specific processor.  It *
+ *   is a "noop" (no-operation) if Crafty was not compiled with -DAFFINITY, or *
+ *   if smp_affinity is negative (smpaffinity=-1 disables affinity).  It       *
+ *   simply sets the affinity for the current thread to the requested CPU and  *
+ *   returns.  NOTE:  If hyperthreading is enabled, there is no guarantee that *
+ *   this will work as expected and pin one thread per physical core.  It      *
+ *   depends on how the O/S numbers the SMT cores.                             *
+ *                                                                             *
+ *******************************************************************************
+ */
-    if (tree->siblings[proc]) {
+void ThreadAffinity(int cpu) {
+#  if defined(AFFINITY)
+  cpu_set_t cpuset;
-      thread[proc].tree = tree->siblings[proc];
+  pthread_t current_thread = pthread_self();
-      thread[proc].idle = 0;
+  if (smp_affinity >= 0) {
+    CPU_ZERO(&cpuset);
+    CPU_SET(cpu + smp_affinity, &cpuset);
+    pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset);
-    }
+  }
+#  endif
+}
+/* modified 11/04/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   ThreadSplit() is used to determine if we should split at the current ply. *
+ *   There are some basic constraints on when splits can be done, such as the  *
+ *   depth remaining in the search (don't split to near the tips), and have we *
+ *   searched at least one move to get a score or bound (YBW condition).       *
+ *                                                                             *
+ *   If those conditions are satisfied, AND either a thread has requested a    *
+ *   split OR we are far enough away from the tips of the tree to justify a    *
+ *   "gratuitout split" then we return "success."  A "gratuitout split" is a   *
+ *   split done without any idle threads.  Since splits are not free, we only  *
+ *   do this well away from tips to limit overhead.  We do this so that when a *
+ *   thread becomes idle, it will find these split points immediately and not  *
+ *   have to wait for a split after the fact.                                  *
+ *                                                                             *
+ *******************************************************************************
+ */
+int ThreadSplit(TREE *RESTRICT tree, int ply, int depth, int alpha, int o_alpha, // Pierre-Marie Baty -- missing keyword
+    int done) {
+  TREE *used;
+  int64_t tblocks;
+  int temp, unused = 0;
 /*
  ************************************************************
  *                                                          *
- *  One final test before leaving.  We test all threads to  *
- *  determine if any are still idle (most likely due to the *
+ *  First, we see if we meet the basic criteria to create a *
- *  smp_split_group limit, but a thread could go idle after *
- *  our loop to pick up idle threads).  If so we set split  *
- *  back to one (actually a temporary split variable since  *
- *  we don't want to remove the split=-1 state until just   *
+ *  split point, that being that we must not be too far     *
- *  before we exit to avoid any races.)                     *
+ *  from the root (smp_min_split_depth).                    *
  *                                                          *
  ************************************************************
  */
-  for (proc = 0; proc < smp_max_threads; proc++)
+  if (depth < (int) smp_min_split_depth) // Pierre-Marie Baty -- added type cast
-    if (thread[proc].idle)
-      tsplit = 1;
+    return 0;
 /*
  ************************************************************
  *                                                          *
- *  After the threads are kicked off to start the parallel  *
+ *  If smp_split is NOT set, we are checking to see if it   *
- *  search using the idle threads, this thread has to be    *
+ *  is acceptable to do a gratuitous split here.            *
- *  inserted as well.  However, since it is possible that   *
+ *                                                          *
- *  this thread may finish before any or all of the other   *
+ *  (1) if we are too far from the root we do not do        *
- *  parallel threads, this thread is sent to ThreadWait()   *
+ *      gratuitous splits to avoid the overhead.            *
- *  which will immediately send it to SearchParallel() like *
+ *                                                          *
- *  the other threads.  Going to ThreadWait() allows this   *
+ *  (2) if we have searched more than one move at this ply, *
- *  thread to join others if it runs out of work to do.  We *
+ *      we don't do any further tests to see if a           *
- *  do pass ThreadWait() the address of the parent thread   *
+ *      gratuitous split is acceptable, since we have       *
- *  block, so that if this thread becomes idle, and this    *
+ *      previously done this test at this ply and decided   *
- *  thread block shows no threads are still busy, then this *
+ *      one should not be done.  That condition has likely  *
- *  thread can return to here and then back up into the     *
+ *      not changed.                                        *
+ *                                                          *
+ *  (3) if we have pre-existing gratuitous split points for *
- *  previous ply as it should.  Note that no other thread   *
+ *      this thread, we make certain we don't create more   *
- *  can back up to the previous ply since their recursive   *
+ *      than the gratuitous split limit as excessive splits *
- *  call stacks are not set for that.                       *
+ *      just add to the overhead with no benefit.           *
  *                                                          *
  ************************************************************
  */
-  smp_split = tsplit;
+  if (!smp_split) {
+    if (depth < (int) smp_gratuitous_depth || done > 1) // Pierre-Marie Baty -- added type cast
+      return 0;
+    tblocks = ~thread[tree->thread_id].blocks;
-  Unlock(lock_smp);
+    while (tblocks) {
+      temp = LSB(tblocks);
+      used = block[temp + tree->thread_id * 64 + 1];
+      if (used->joinable && !used->joined)
+        unused++;
+      Clear(temp, tblocks);
+    }
+    if (unused > (int) smp_gratuitous_limit) // Pierre-Marie Baty -- added type cast
+      return 0;
+  }
+/*
+ ************************************************************
+ *                                                          *
+ *  If smp_split IS set, we are checking to see if it is    *
+ *  acceptable to do a split because there are idle threads *
+ *  that need work to do.                                   *
+ *                                                          *
+ *  The only reason this would be false is if we have a     *
+ *  pre-existing split point that is joinable but has not   *
+ *  been joined. If one exists, there is no need to split   *
+ *  again as there is already an accessible split point.    *
+ *  Otherwise, if we are at the root and we are either not  *
+ *  allowed to split at the root, or we have additional     *
+ *  root moves that have to be searched one at a time using *
+ *  all available threads we also can not split here.       *
+ *                                                          *
+ ************************************************************
+ */
+  else {
+    if (ply == 1 && (!smp_split_at_root || !NextRootMoveParallel() ||
+            alpha == o_alpha))
+      return 0;
-  ThreadWait(tree->thread_id, tree);
+    tblocks = ~thread[tree->thread_id].blocks;
+    while (tblocks) {
+      temp = LSB(tblocks);
+      used = block[temp + tree->thread_id * 64 + 1];
+      if (used->joinable && !used->joined)
+        unused++;
+      Clear(temp, tblocks);
+    }
+    if (unused > (int) smp_gratuitous_limit) // Pierre-Marie Baty -- added type cast
+      return 0;
+  }
   return 1;
+}
-/* modified 04/30/14 */
+/* modified 11/04/15 */
 /*
  *******************************************************************************
  *                                                                             *
- *   CopyToChild() is used to copy data from a parent thread to a particular   *
+ *   ThreadStop() is called from SearchMoveList() when it detects a beta       *
+ *   cutoff (fail high) at a node that is being searched in parallel.  We need *
+ *   to stop all threads here, and since this threading algorithm is recursive *
+ *   it may be necessary to stop other threads that are helping search this    *
+ *   branch further down into the tree.  This function simply sets appropriate *
- *   child thread.  This only copies the appropriate parts of the TREE         *
+ *   tree->stop variables to 1, which will stop those particular threads       *
- *   structure to avoid burning memory bandwidth by copying everything.        *
+ *   instantly and return them to the idle loop in ThreadWait().               *
  *                                                                             *
  *******************************************************************************
  */
+void ThreadStop(TREE * RESTRICT tree) {
+  int proc;
+  Lock(tree->lock);
+  tree->stop = 1;
+  tree->joinable = 0;
+  for (proc = 0; proc < (int) smp_max_threads; proc++) // Pierre-Marie Baty -- added type cast
+    if (tree->siblings[proc])
+      ThreadStop(tree->siblings[proc]);
+  Unlock(tree->lock);
+}
+/* modified 11/04/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   ThreadTrace() is a debugging tool that simply walks the split block tree  *
+ *   and displays interesting data to help debug the parallel search whenever  *
+ *   changes break things.                                                     *
+ *                                                                             *
+ *******************************************************************************
+ */
-void CopyToChild(TREE * RESTRICT parent, int thread) {
+void ThreadTrace(TREE * RESTRICT tree, int depth, int brief) {
+  int proc, i;
+  Lock(tree->lock);
+  Lock(lock_io);
+  if (!brief) {
+    for (i = 0; i < 4 * depth; i++)
+      Print(4095, " ");
+    depth++;
+    Print(4095, "block[%d]  thread=%d  ply=%d  nprocs=%d  ",
+        FindBlockID(tree), tree->thread_id, tree->ply, tree->nprocs);
+    Print(4095, "joined=%d  joinable=%d  stop=%d  nodes=%d", tree->joined,
+        tree->joinable, tree->stop, tree->nodes_searched);
+    Print(4095, "  parent=%d\n", FindBlockID(tree->parent));
+  } else {
+    if (tree->nprocs > 1) {
+      for (i = 0; i < 4 * depth; i++)
+        Print(4095, " ");
+      depth++;
-  int i, j, /*max, */ply = parent->ply;
+      Print(4095, "(ply %d)", tree->ply);
+    }
+  }
+  if (tree->nprocs) {
+    if (!brief) {
+      for (i = 0; i < 4 * depth; i++)
+        Print(4095, " ");
+      Print(4095, "          parent=%d  sibling threads=",
+          FindBlockID(tree->parent));
-  unsigned int max_; // Pierre-Marie Baty -- should be unsigned
+      for (proc = 0; proc < (int) smp_max_threads; proc++) // Pierre-Marie Baty -- added type cast
+        if (tree->siblings[proc])
+          Print(4095, " %d(%d)", proc, FindBlockID(tree->siblings[proc]));
+      Print(4095, "\n");
-  TREE *child;
+    } else {
-  static int warnings = 0;
+      if (tree->nprocs > 1) {
+        Print(4095, " helping= ");
+        for (proc = 0; proc < (int) smp_max_threads; proc++) // Pierre-Marie Baty -- added type cast
+          if (tree->siblings[proc]) {
-  int first = thread * MAX_BLOCKS_PER_CPU + 1;
+            if (proc == tree->thread_id)
+              Print(4095, "[");
+            Print(4095, "%d", proc);
-  int last = first + MAX_BLOCKS_PER_CPU;
+            if (proc == tree->thread_id)
+              Print(4095, "]");
+            Print(4095, " ");
+          }
+        Print(4095, "\n");
+      }
+    }
+  }
+  Unlock(lock_io);
+  for (proc = 0; proc < (int) smp_max_threads; proc++) // Pierre-Marie Baty -- added type cast
+    if (tree->siblings[proc])
+      ThreadTrace(tree->siblings[proc], depth, brief);
+  Unlock(tree->lock);
+}
+/* modified 11/04/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   ThreadWait() is the idle loop for the N threads that are created at the   *
+ *   beginning when Crafty searches.  Threads are "parked" here waiting on a   *
+ *   pointer to something they should search (a parameter block built in the   *
+ *   function Split() in this case.  When this pointer becomes non-zero, each  *
+ *   thread "parked" here will immediately call SearchMoveList() and begin the *
+ *   parallel search as directed.                                              *
+ *                                                                             *
+ *   Upon entry, all threads except for the "master" will arrive here with a   *
+ *   value of zero (0) in the waiting parameter below.  This indicates that    *
+ *   they will search and them be done.  The "master" will arrive here with a  *
+ *   pointer to the parent split block in "waiting" which says I will sit here *
+ *   waiting for work OR when the waiting split block has no threads working   *
+ *   on it, at which point I should return which will let me "unsplit" here    *
+ *   and clean things up.  The call to here in Split() passes this block       *
+ *   address while threads that are helping get here with a zero.              *
+ *                                                                             *
+ *******************************************************************************
+ */
-  int maxb = smp_max_threads * MAX_BLOCKS_PER_CPU + 1;
+int ThreadWait(int tid, TREE * RESTRICT waiting) {
+  int value, tstart, tend;
 /*
  ************************************************************
  *                                                          *
- *  One NUMA-related trick is that we first try to allocate *
+ *  When we reach this point, one of three possible         *
- *  a split block in the thread's local memory.  Each       *
+ *  conditions is true (1) we already have work to do, as   *
- *  thread has a group of split blocks that were first      *
+ *  we are the "master thread" and we have already split    *
- *  touched by the correct CPU so that the split blocks     *
+ *  the tree, we are coming here to join in;  (2) we are    *
- *  page faulted into local memory for that specific        *
+ *  the master, and we are waiting on our split point to    *
- *  processor.  If we can't find an optimal-placed block,   *
+ *  complete, so we come here to join and help currently    *
+ *  active threads;  (3) we have no work to do, so we will  *
+ *  spin until Join() locates a split pont we can join to   *
+ *  help out.                                               *
+ *                                                          *
- *  the second pass will find the first available block.    *
+ *  Note that when we get here, the parent already has a    *
+ *  split block and does not need to call Join(), it simply *
- *  If none can be found, we return as we can not split     *
+ *  falls through the while spin loop below because its     *
- *  until other split blocks are freed up.                  *
+ *  "tree" pointer is already non-zero.                     *
  *                                                          *
  ************************************************************
  */
+  while (1) {
-  for (i = first; i < last && block[i]->used; i++);
+    tstart = ReadClock();
+    while (!thread[tid].tree && (!waiting || waiting->nprocs) && !Join(tid) &&
+        !thread[tid].terminate)
-  if (i >= last) {
+      Pause();
+    tend = ReadClock();
-    if (++warnings < 6)
+    if (!thread[tid].tree)
+      thread[tid].tree = waiting;
+    thread[tid].idle += tend - tstart;
+    if (thread[tid].tree == waiting || thread[tid].terminate)
-      Print(128,
+      return 0;
+/*
+ ************************************************************
+ *                                                          *
+ *  Once we get here, we have a good split point, so we are *
+ *  ready to participate in a parallel search.  Once we     *
+ *  return from SearchMoveList() we copy our results back   *
+ *  to the parent via CopyToParent() before we look for a   *
+ *  new split point.  If we are a parent, we will slip out  *
-          "WARNING.  optimal SMP block cannot be allocated, thread %d\n",
+ *  of the spin loop at the top and return to the normal    *
+ *  serial search to finish up here.                        *
+ *                                                          *
+ *  When we return from SearchMoveList(), we need to        *
+ *  decrement the "nprocs" value since there is now one     *
+ *  less thread working at this split point.                *
+ *                                                          *
+ *  Note:  CopyToParent() marks the current split block as  *
+ *  unused once the copy is completed, so we don't have to  *
+ *  do anything about that here.                            *
+ *                                                          *
+ ************************************************************
+ */
-          thread);
+    value =
+        SearchMoveList(thread[tid].tree, thread[tid].tree->ply,
+        thread[tid].tree->depth, thread[tid].tree->wtm,
-    for (i = 1; i < maxb && block[i]->used; i++);
+        thread[tid].tree->alpha, thread[tid].tree->beta,
+        thread[tid].tree->searched, thread[tid].tree->in_check, 0, parallel);
-    if (i >= maxb) {
+    tstart = ReadClock();
+    Lock(thread[tid].tree->parent->lock);
+    thread[tid].tree->parent->joinable = 0;
-      Print(128, "ERROR.  no SMP block can be allocated\n");
+    CopyToParent((TREE *) thread[tid].tree->parent, thread[tid].tree, value);
+    thread[tid].tree->parent->nprocs--;
+    thread[tid].tree->parent->siblings[tid] = 0;
+    Unlock(thread[tid].tree->parent->lock);
-      exit(1);
+    thread[tid].tree = 0;
-    }
+    tend = ReadClock();
+    thread[tid].idle += tend - tstart;
+  }
+}
-  max_ = 0;
+/* modified 11/04/15 */
+/*
+ *******************************************************************************
+ *                                                                             *
+ *   CopyFromParent() is used to copy data from a parent thread to a child     *
+ *   thread.  This only copies the appropriate parts of the TREE structure to  *
+ *   avoid burning memory bandwidth by copying everything.                     *
+ *                                                                             *
+ *******************************************************************************
+ */
-  for (j = 1; j < maxb; j++)
+void CopyFromParent(TREE * RESTRICT child) {
-    if (block[j]->used)
+  TREE *parent = child->parent;
-      max_++;
+  int i, ply;
-  max_split_blocks = Max(max_split_blocks, max_);
 /*
  ************************************************************
  *                                                          *
  *  We have allocated a split block.  Now we copy the tree  *
  *  search state from the parent block to the child in      *
  *  preparation for starting the parallel search.           *
  *                                                          *
  ************************************************************
  */
-  child = block[i];
+  ply = parent->ply;
-  child->used = 1;
-  child->stop = 0;
-  for (i = 0; i < smp_max_threads; i++)
-    child->siblings[i] = 0;
-  child->nprocs = 0;
   child->ply = ply;
   child->position = parent->position;
-  child->pv[ply - 1] = parent->pv[ply - 1];
-  child->pv[ply] = parent->pv[ply];
-  child->next_status[ply] = parent->next_status[ply];
-  child->save_hash_key[ply] = parent->save_hash_key[ply];
-  child->save_pawn_hash_key[ply] = parent->save_pawn_hash_key[ply];
-  child->rep_index = parent->rep_index;
-  for (i = 0; i <= parent->rep_index + parent->ply; i++)
+  for (i = 0; i <= rep_index + parent->ply; i++)
     child->rep_list[i] = parent->rep_list[i];
-  child->last[ply] = child->move_list;
+  for (i = ply - 1; i < MAXPLY; i++)
-  child->hash_move[ply] = parent->hash_move[ply];
+    child->killers[i] = parent->killers[i];
-  for (i = 1; i <= ply + 1; i++) {
+  for (i = ply - 1; i <= ply; i++) {
-    child->status[i] = parent->status[i];
     child->curmv[i] = parent->curmv[i];
-    child->inchk[i] = parent->inchk[i];
-    child->phase[i] = parent->phase[i];
+    child->pv[i] = parent->pv[i];
+  }
-  for (i = 1; i < MAXPLY; i++)
+  child->in_check = parent->in_check;
+  child->last[ply] = child->move_list;
+  child->status[ply] = parent->status[ply];
-    child->killers[i] = parent->killers[i];
+  child->status[1] = parent->status[1];
+  child->save_hash_key[ply] = parent->save_hash_key[ply];
+  child->save_pawn_hash_key[ply] = parent->save_pawn_hash_key[ply];
   child->nodes_searched = 0;
   child->fail_highs = 0;
   child->fail_high_first_move = 0;
   child->evaluations = 0;
   child->egtb_probes = 0;
-  child->egtb_probes_successful = 0;
+  child->egtb_hits = 0;
   child->extensions_done = 0;
   child->qchecks_done = 0;
-  child->reductions_done = 0;
   child->moves_fpruned = 0;
+  child->moves_mpruned = 0;
+  for (i = 0; i < 16; i++) {
+    child->LMR_done[i] = 0;
+    child->null_done[i] = 0;
+  }
   child->alpha = parent->alpha;
   child->beta = parent->beta;
   child->value = parent->value;
-  child->side = parent->side;
+  child->wtm = parent->wtm;
   child->depth = parent->depth;
-  parent->siblings[thread] = child;
-  child->thread_id = thread;
-  child->parent = parent;
+  child->searched = parent->searched;
-  parent->nprocs++;
-  strcpy_s(child->root_move_text, sizeof (child->root_move_text), parent->root_move_text); // Pierre-Marie Baty -- use safe version
+  strcpy(child->root_move_text, parent->root_move_text);
-  strcpy_s(child->remaining_moves_text, sizeof (child->remaining_moves_text), parent->remaining_moves_text); // Pierre-Marie Baty -- use safe version
+  strcpy(child->remaining_moves_text, parent->remaining_moves_text);
+}
-/* modified 04/18/14 */
+/* modified 11/04/15 */
 /*
  *******************************************************************************
  *                                                                             *
  *   CopyToParent() is used to copy data from a child thread to a parent       *
  *   thread.  This only copies the appropriate parts of the TREE structure to  *
  *   avoid burning memory bandwidth by copying everything.                     *
  *                                                                             *
  *******************************************************************************
  */
 void CopyToParent(TREE * RESTRICT parent, TREE * RESTRICT child, int value) {
-  int ply = parent->ply;
+  int i, ply = parent->ply, which;
 /*
  ************************************************************
  *                                                          *
- *  Only concern here is to make sure that the info is only *
+ *  The only concern here is to make sure that the info is  *
- *  copied to the parent if our score is > than the parent  *
+ *  only copied to the parent if our score is > than the    *
- *  value, and that we were not stopped for any reason      *
+ *  parent value, and that we were not stopped for any      *
- *  which could produce a partial score that is worthless.  *
+ *  reason which could produce a partial score that is      *
+ *  worthless and dangerous to use.                         *
+ *                                                          *
+ *  One important special case.  If we get here with the    *
+ *  thread->stop flag set, and ply is 1, then we need to    *
+ *  clear the "this move has been searched" flag in the ply *
+ *  1 move list since we did not complete the search.  If   *
+ *  we fail to do this, then a move being searched in       *
+ *  parallel at the root will be "lost" for this iteration  *
+ *  and won't be searched again until the next iteration.   *
  *                                                          *
  *  In any case, we add our statistical counters to the     *
  *  parent's totals no matter whether we finished or not    *
  *  since the total nodes searched and such should consider *
  *  everything searched, not just the "useful stuff."       *
+ *                                                          *
+ *  After we finish copying everything, we mark this split  *
+ *  block as free in the split block bitmap.                *
  *                                                          *
  ************************************************************
  */
   if (child->nodes_searched && !child->stop && value > parent->value &&
       !abort_search) {
     parent->pv[ply] = child->pv[ply];
     parent->value = value;
     parent->cutmove = child->curmv[ply];
+  }
+  if (child->stop && ply == 1)
+    for (which = 0; which < n_root_moves; which++)
+      if (root_moves[which].move == child->curmv[ply]) {
+        root_moves[which].status &= 7;
+        break;
+      }
   parent->nodes_searched += child->nodes_searched;
   parent->fail_highs += child->fail_highs;
   parent->fail_high_first_move += child->fail_high_first_move;
   parent->evaluations += child->evaluations;
   parent->egtb_probes += child->egtb_probes;
-  parent->egtb_probes_successful += child->egtb_probes_successful;
+  parent->egtb_hits += child->egtb_hits;
   parent->extensions_done += child->extensions_done;
   parent->qchecks_done += child->qchecks_done;
-  parent->reductions_done += child->reductions_done;
   parent->moves_fpruned += child->moves_fpruned;
+  parent->moves_mpruned += child->moves_mpruned;
-  child->used = 0;
+  for (i = 1; i < 16; i++) {
+    parent->LMR_done[i] += child->LMR_done[i];
+    parent->null_done[i] += child->null_done[i];
+  }
+  which = FindBlockID(child) - 64 * child->thread_id - 1;
+  Set(which, thread[child->thread_id].blocks);
+}
+/* modified 11/04/15 */
 /*
  *******************************************************************************
  *                                                                             *
- *   WaitForAllThreadsInitialized() waits until all smp_max_threads are        *
+ *   GetBlock() is used to allocate a split block and fill in only SMP-        *
- *   initialized.  We have to initialize each thread and malloc() its split    *
+ *   critical information.  The child process will copy the rest of the split  *
- *   blocks before we start the actual parallel search.  Otherwise we will see *
+ *   block information as needed.                                              *
- *   invalid memory accesses and crash instantly.                              *
+ *                                                                             *
+ *   When we arrive here, the parent split block must be locked since we are   *
+ *   going to change data in that block as well as copy data from that block   *
+ *   the current split block.  The only exception is when this is the original *
+ *   split operation, since this is done "out of sight" of other threads which *
+ *   means no locks are needed until after the "joinable" flag is set, which   *
+ *   exposes this split point to other threads instantly.                      *
  *                                                                             *
  *******************************************************************************
  */
+TREE *GetBlock(TREE * /*RESTRICT*/ parent, int tid) { // Pierre-Marie Baty -- keyword not present in declaration
+  TREE *child;
+  static int warnings = 0;
+  int i, unused;
+/*
+ ************************************************************
+ *                                                          *
+ *  One NUMA-related trick is that we only allocate a split *
+ *  block in the thread's local memory.  Each thread has a  *
+ *  group of split blocks that were first touched by the    *
+ *  correct CPU so that the split blocks page-faulted into  *
+ *  local memory for that specific processor.  If we can't  *
+ *  find an optimally-placed block, we return a zero which  *
+ *  will prevent this thread from joining the split point.  *
+ *  This is highly unlikely as it would mean the current    *
+ *  thread has 64 active split blocks where it is waiting   *
+ *  on other threads to complete the last bit of work at    *
+ *  each.  This is extremely unlikely.                      *
+ *                                                          *
+ *  Here we use a simple 64 bit bit-map per thread that     *
+ *  indicates which blocks are free (1) and which blocks    *
+ *  used (0).  We simply use LSB() to find the rightmost    *
+ *  one-bit set and that is the local block number.  We     *
+ *  convert that to a global block number by doing the      *
+ *  simple computation:                                     *
+ *                                                          *
+ *     global = local + 64 * tid + 1                        *
+ *                                                          *
+ *  Each thread has exactly 64 split blocks, and block 0    *
+ *  is the "master block" that never gets allocated or      *
+ *  freed.  Once we find a free block for the current       *
+ *  thread, we zero that bit so that the block won't be     *
+ *  used again until it is released.                        *
+ *                                                          *
+ ************************************************************
+ */
-void WaitForAllThreadsInitialized(void) {
+  if (thread[tid].blocks) {
+    unused = LSB(thread[tid].blocks);
+    Clear(unused, thread[tid].blocks);
+    Set(unused, thread[tid].max_blocks);
+  } else {
+    if (++warnings < 6)
+      Print(2048,
+          "WARNING.  local SMP block cannot be allocated, thread %d\n", tid);
+    return 0;
+  }
+  child = block[unused + tid * 64 + 1];
+/*
+ ************************************************************
+ *                                                          *
+ *  Found a split block.  Now we need to fill in only the   *
+ *  critical information that can't be delayed due to race  *
+ *  conditions.  When we get here, the parent split block   *
+ *  must be locked, that lets us safely update the number   *
+ *  of processors working here, etc, without any ugly race  *
+ *  conditions that would corrupt this critical data.       *
+ *                                                          *
+ ************************************************************
+ */
-  while (initialized_threads < smp_max_threads);        /* Do nothing */
+  for (i = 0; i < (int) smp_max_threads; i++) // Pierre-Marie Baty -- added type cast
+    child->siblings[i] = 0;
+  child->nprocs = 0;
+  child->stop = 0;
+  child->joinable = 0;
+  child->joined = 0;
+  child->parent = parent;
+  child->thread_id = tid;
+  parent->nprocs++;
+  parent->siblings[tid] = child;
+  parent->joined = 1;
+  return child;
+}
-/* modified 06/07/09 */
 /*
  *******************************************************************************
  *                                                                             *
- *   ThreadInit() is called after a process is created.  Its main task is to   *
+ *   WaitForAllThreadsInitialized() waits until all smp_max_threads are        *
- *   initialize the process local memory so that it will fault in and be       *
+ *   initialized.  We have to initialize each thread and malloc() its split    *
- *   allocated on the local node rather than the node where the original       *
+ *   blocks before we start the actual parallel search.  Otherwise we will see *
- *   (first) process was running.  All threads will hang here via a custom     *
- *   WaitForALlThreadsInitialized() procedure so that all the local thread     *
- *   blocks are usable before the search actually begins.                      *
+ *   invalid memory accesses and crash instantly.                              *
  *                                                                             *
  *******************************************************************************
  */
-void *STDCALL ThreadInit(void *tid) {
+void WaitForAllThreadsInitialized(void) {
-  int i, j;
-#if defined(AFFINITY)
-  int64_t k;
-  cpu_set_t cpuset;
-  pthread_t current_thread = pthread_self();
-  k = (int64_t) tid;
-  CPU_ZERO(&cpuset);
-  CPU_SET(k, &cpuset);
-  pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset);
-#endif
-#if !defined(UNIX)
-  ThreadMalloc((uint64_t) tid);
-#endif
-  for (i = 0; i < MAX_BLOCKS_PER_CPU; i++) {
-    memset((void *) block[(uint64_t) tid * MAX_BLOCKS_PER_CPU + i + 1], 0,
+  while (initialized_threads < (int) smp_max_threads); /* Do nothing */ // Pierre-Marie Baty -- added type cast
-        sizeof(TREE));
-    block[(uint64_t) tid * MAX_BLOCKS_PER_CPU + i + 1]->used = 0;
-    block[(uint64_t) tid * MAX_BLOCKS_PER_CPU + i + 1]->parent = NULL;
-    LockInit(block[(uint64_t) tid * MAX_BLOCKS_PER_CPU + i + 1]->lock);
-    for (j = 0; j < 64; j++)
-      block[(uint64_t) tid * MAX_BLOCKS_PER_CPU + i + 1]->cache_n[j] = ~0ull;
-  }
-  Lock(lock_smp);
-  initialized_threads++;
-  Unlock(lock_smp);
-  WaitForAllThreadsInitialized();
-  ThreadWait((uint64_t) tid, (TREE *) 0);
-  Lock(lock_smp);
-  smp_threads--;
-  Unlock(lock_smp);
-  return 0;
+}
-#if !defined (UNIX)
+#  if !defined (UNIX)
 /* modified 01/17/09 */
 /*
  *******************************************************************************
  *                                                                             *
  *   ThreadMalloc() is called from the ThreadInit() function.  It malloc's the *
  *                                                                             *
  *******************************************************************************
  */
 extern void *WinMalloc(size_t, int);
 void ThreadMalloc(int64_t tid) {
-  int i, n = MAX_BLOCKS_PER_CPU;
+  int i;
-  for (i = MAX_BLOCKS_PER_CPU * (int) (tid) + 1; n; i++, n--) { // Pierre-Marie Baty -- added type cast
+  for (i = (int) tid * 64 + 1; i < (int) tid * 64 + 65; i++) { // Pierre-Marie Baty -- added type casts
     if (block[i] == NULL)
       block[i] =
           (TREE *) ((~(size_t) 127) & (127 + (size_t) WinMalloc(sizeof(TREE) +
 , (int) tid))); // Pierre-Marie Baty -- added type cast
-    block[i]->used = 0;
     block[i]->parent = NULL;
     LockInit(block[i]->lock);
+  }
+}
+#  endif
 #endif
-/* modified 01/17/09 */
-/*
- *******************************************************************************
- *                                                                             *
- *   ThreadStop() is called from SearchParallel() when it detects a beta       *
- *   cutoff (fail high) at a node that is being searched in parallel.  We need *
- *   to stop all threads here, and since this threading algorithm is recursive *
- *   it may be necessary to stop other threads that are helping search this    *
- *   branch further down into the tree.  This function simply sets tree->stop  *
- *   to 1, which will stop that particular thread instantly and return it to   *
- *   the idle loop in ThreadWait().                                            *
- *                                                                             *
- *******************************************************************************
- */
-void ThreadStop(TREE * RESTRICT tree) {
-  int proc;
-  Lock(tree->lock);
-  tree->stop = 1;
-  for (proc = 0; proc < smp_max_threads; proc++)
-    if (tree->siblings[proc])
-      ThreadStop(tree->siblings[proc]);
-  Unlock(tree->lock);
-}
-/* modified 04/23/14 */
-/*
- *******************************************************************************
- *                                                                             *
- *   ThreadWait() is the idle loop for the N threads that are created at the   *
- *   beginning when Crafty searches.  Threads are "parked" here waiting on a   *
- *   pointer to something they should search (a parameter block built in the   *
- *   function Thread() in this case.  When this pointer becomes non-zero, each *
- *   thread "parked" here will immediately call SearchParallel() and begin the *
- *   parallel search as directed.                                              *
- *                                                                             *
- *******************************************************************************
- */
-int ThreadWait(int64_t tid, TREE * RESTRICT waiting) {
-  int value, tstart, tend;
-/*
- ************************************************************
- *                                                          *
- *  The N initial threads enter here and are kept penned    *
- *  here forever.  However, once a thread leaves here it    *
- *  may well re-enter ThreadWait() from the top while it    *
- *  waits for a parallel search to complete.  While it      *
- *  waits here it can also join in to help other busy       *
- *  threads search their subtrees as well.                  *
- *                                                          *
- ************************************************************
- */
-  while (1) {
-    tstart = ReadClock();
-    Lock(lock_split);
-    Lock(lock_smp);
-    smp_idle++;
-    if (!waiting && smp_split == 0)
-      smp_split = 1;
-    if (!thread[tid].tree)
-      thread[tid].idle = 1;
-    Unlock(lock_smp);
-    Unlock(lock_split);
-/*
- ************************************************************
- *                                                          *
- *  We can exit if our thread[i] is non-zero, or if we are  *
- *  waiting on others to finish a block that *we* have to   *
- *  return through.  When the busy count on such a block    *
- *  hits zero, we return immediately which unwinds the      *
- *  search as it should be.                                 *
- *                                                          *
- ************************************************************
- */
-    while (!thread[tid].tree && (!waiting || waiting->nprocs))
-      Pause();
-    thread[tid].idle = 0;
-    tend = ReadClock();
-    Lock(lock_smp);
-    idle_time += tend - tstart;
-    if (!thread[tid].tree)
-      thread[tid].tree = waiting;
-/*
- ************************************************************
- *                                                          *
- *  We either have work to do, or threads we were waiting   *
- *  on have finished their work.                            *
- *                                                          *
- ************************************************************
- */
-    smp_idle--;
-    Unlock(lock_smp);
-/*
- ************************************************************
- *                                                          *
- *  If we are waiting on a block and the busy count is now  *
- *  zero, we simply return to finish up the bookkeeping at  *
- *  that point.                                             *
- *                                                          *
- ************************************************************
- */
-    if (thread[tid].tree == waiting || thread[tid].tree == (TREE *) - 1)
-      return 0;
-/*
- ************************************************************
- *                                                          *
- *  Else our thread[i] pointer is non-zero, meaning we have *
- *  been assigned something to search.  Hi-ho, hi-ho, it's  *
- *  off to work we go...                                    *
- *                                                          *
- ************************************************************
- */
-    value =
-        SearchParallel(thread[tid].tree, thread[tid].tree->alpha,
-        thread[tid].tree->beta, thread[tid].tree->value,
-        thread[tid].tree->side, thread[tid].tree->depth,
-        thread[tid].tree->ply);
-    Lock(thread[tid].tree->parent->lock);
-    CopyToParent((TREE *) thread[tid].tree->parent, thread[tid].tree, value);
-    thread[tid].tree->parent->nprocs--;
-    thread[tid].tree->parent->siblings[tid] = 0;
-    Unlock(thread[tid].tree->parent->lock);
-    thread[tid].tree = 0;
-  }
-}

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-crafty/thread.c – Rev 33 → 108