Subversion Repositories Games.Chess Giants

#include "chess.h"

#include "data.h"

#include "epdglue.h"

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 Split(), from Search(), and begin a new     *

 *   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    *

 *   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    *

 *   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> <p> 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 fairly   *

 *      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 *

 *      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 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_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     *

 *      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  *

 *      one or more threads join at least one of the existing split points.    *

 *      In the smp search statistics, where you see output that looks like     *

 *      this:                                                                  *

 *                                                                             *

 *        splits=m(n) ...                                                      *

 *                                                                             *

 *      m is the total splits done, n is the number of "wasted splits" which   *

 *      are basically gratuitous splits where no thread joined before this     *

 *      split point was completed and deallocated.                             *

 *                                                                             *

 *   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    *

 *       block during NextMove() and such.                                     *

 *                                                                             *

 *   3.  If you want to modify any SMP-related data that spans multiple split  *

 *       blocks, such as telling sibling processes to stop, etc, then you must *

 *       acquire the global "lock_smp" lock first.  This prevents a deadlock   *

 *       caused by two different threads walking the split block chain from    *

 *       different directions, and acquiring the split block locks in          *

 *       different orders, which could cause a catastrophic deadlock to occur. *

 *       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.                                                    *

 *                                                                             *

 *   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 Split(TREE * RESTRICT tree) {

  TREE *child;

  int tid, tstart, tend;

/*

 ************************************************************

 *                                                          *

 *  Here we prepare to split the tree.  All we really do in *

 *  the Generation II threading is grab a split block for   *

 *  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   *

 *  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();

  tree->nprocs = 0;

  for (tid = 0; tid < smp_max_threads; tid++)

    tree->siblings[tid] = 0;

  child = GetBlock(tree, tree->thread_id);

  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 *

 *  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    *

 *  all of the other parallel threads, this thread is sent  *

 *  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      *

 *  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       *

 *  should.  Note that no other thread can back up to the   *

 *  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,     *

 *  which we just completed.                                *

 *                                                          *

 ************************************************************

 */

  ThreadWait(tree->thread_id, tree);

  if (!tree->joined)

    parallel_splits_wasted++;

  return 1;

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   Join() is called just when we enter the usual spin-loop waiting for work. *

 *   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,  *

 *   which allows us to join that existing split point and not request a new   *

 *   split operation, saving time.                                             *

 *                                                                             *

 *******************************************************************************

 */

int Join(int64_t tid) {

  TREE *tree, *join_block, *child;

  int interest, best_interest, current, pass = 0;

/*

 ************************************************************

 *                                                          *

 *  First we pass over ALL split blocks, looking for those  *

 *  flagged as "joinable" (which means they are actually    *

 *  active split points and that no processor at that split *

 *  point has run out of work (there is no point in joining *

 *  a split point with no remaining work) and no fail high  *

 *  has been found which would raise the "stop" flag.) This *

 *  is "racy" because we do not acquire any locks, which    *

 *  means that the busy threads continue working, and there *

 *  is a small probability that the split point will        *

 *  disappear while we are in this loop.  To resolve the    *

 *  potential race, after we find the most attractive split *

 *  point, we acquire the lock for that split block and     *

 *  test again, but this time if the block is joinable, we  *

 *  can safely join under control of the lock, which is not *

 *  held for very long at all.  If the block is not         *

 *  joinable once we acquire the lock, we abort joining     *

 *  since it is futile.  Note that if this happens, we will *

 *  try to find an existing split point we can join three   *

 *  times before we exit, setting split to 1 to ask other   *

 *  threads to produce more candidate split points.         *

 *                                                          *

 *  Special case:  We don't want to join a split point that *

 *  was created by this thread.  While it works, it can add *

 *  overhead since we can encounter a later split point     *

 *  that originated at the current split point, and we      *

 *  would continue searching even though most of the work   *

 *  has already been completed.  The hash table would help  *

 *  avoid most (if not all) of this overhead, but there is  *

 *  no good reason to take the chance of this happening.    *

 *                                                          *

 ************************************************************

 */

  for (pass = 0; pass < 3; pass++) {

    best_interest = -999999;

    join_block = 0;

    for (current = 0; current <= smp_max_threads * 64; current++) {

      tree = block[current];

      if (tree->joinable && (tree->ply <= tree->depth / 2 ||

              tree->nprocs < smp_split_group) && tree->thread_id != tid) {

        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  *

 *  check to see if the block is still flagged as joinable. *

 *  If so, we set things up, and then we get pretty tricky  *

 *  as we then release the lock, and then copy the data     *

 *  from the parent to our split block.  There is a chance  *

 *  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  *

 *  data here, the split point is completed, the parent     *

 *  block is released and then reacquired and we continue   *

 *  if nothing has happened here, getting data copied from  *

 *  two different positions.                                *

 *                                                          *

 *  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, tid);

        Unlock(join_block->lock);

        if (child) {

          CopyFromParent(child);

          thread[tid].tree = child;

          parallel_joins++;

          return 1;

        }

      } else {

        Unlock(join_block->lock);

        break;

      }

    }

  }

/*

 ************************************************************

 *                                                          *

 *  We did not acquire a split point to join, so we set     *

 *  smp_split to 1 to ask busy threads to create joinable   *

 *  split points.                                           *

 *                                                          *

 ************************************************************

 */

  smp_split = 1;

  return 0;

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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.                             *

 *                                                                             *

 *******************************************************************************

 */

void ThreadAffinity(int cpu) {

#if defined(AFFINITY)

  cpu_set_t cpuset;

  pthread_t current_thread = pthread_self();

  if (smp_affinity >= 0) {

    CPU_ZERO(&cpuset);

    CPU_SET(smp_affinity_increment * (cpu + smp_affinity), &cpuset);

    pthread_setaffinity_np(current_thread, sizeof(cpu_set_t), &cpuset);

  }

#endif

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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

  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 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 * tree, int ply, int depth, int alpha, int o_alpha,

    int done) {

  TREE *used;

  int64_t tblocks;

  int temp, unused = 0;

/*

 ************************************************************

 *                                                          *

 *  First, we see if we meet the basic criteria to create a *

 *  split point, that being that we must not be too far     *

 *  from the root (smp_min_split_depth).                    *

 *                                                          *

 ************************************************************

 */

  if (depth < smp_min_split_depth)

    return 0;

/*

 ************************************************************

 *                                                          *

 *  If smp_split is NOT set, we are checking to see if it   *

 *  is acceptable to do a gratuitous split here.            *

 *                                                          *

 *  (1) if we are too far from the root we do not do        *

 *      gratuitous splits to avoid the overhead.            *

 *                                                          *

 *  (2) if we have searched more than one move at this ply, *

 *      we don't do any further tests to see if a           *

 *      gratuitous split is acceptable, since we have       *

 *      previously done this test at this ply and decided   *

 *      one should not be done.  That condition has likely  *

 *      not changed.                                        *

 *                                                          *

 *  (3) if we have pre-existing gratuitous split points for *

 *      this thread, we make certain we don't create more   *

 *      than the gratuitous split limit as excessive splits *

 *      just add to the overhead with no benefit.           *

 *                                                          *

 ************************************************************

 */

  if (!smp_split) {

    if (depth < smp_gratuitous_depth || done > 1)

      return 0;

    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 > smp_gratuitous_limit)

      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;

    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 > smp_gratuitous_limit)

      return 0;

  }

  return 1;

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 *

 *   tree->stop variables to 1, which will stop those particular threads       *

 *   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 < smp_max_threads; proc++)

    if (tree->siblings[proc])

      ThreadStop(tree->siblings[proc]);

  Unlock(tree->lock);

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 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++;

      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));

      for (proc = 0; proc < smp_max_threads; proc++)

        if (tree->siblings[proc])

          Print(4095, " %d(%d)", proc, FindBlockID(tree->siblings[proc]));

      Print(4095, "\n");

    } else {

      if (tree->nprocs > 1) {

        Print(4095, " helping= ");

        for (proc = 0; proc < smp_max_threads; proc++)

          if (tree->siblings[proc]) {

            if (proc == tree->thread_id)

              Print(4095, "[");

            Print(4095, "%d", proc);

            if (proc == tree->thread_id)

              Print(4095, "]");

            Print(4095, " ");

          }

        Print(4095, "\n");

      }

    }

  }

  Unlock(lock_io);

  for (proc = 0; proc < smp_max_threads; proc++)

    if (tree->siblings[proc])

      ThreadTrace(tree->siblings[proc], depth, brief);

  Unlock(tree->lock);

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 ThreadWait(int tid, TREE * RESTRICT waiting) {

  int value, tstart, tend;

/*

 ************************************************************

 *                                                          *

 *  When we reach this point, one of three possible         *

 *  conditions is true (1) we already have work to do, as   *

 *  we are the "master thread" and we have already split    *

 *  the tree, we are coming here to join in;  (2) we are    *

 *  the master, and we are waiting on our split point to    *

 *  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.                                               *

 *                                                          *

 *  Note that when we get here, the parent already has a    *

 *  split block and does not need to call Join(), it simply *

 *  falls through the while spin loop below because its     *

 *  "tree" pointer is already non-zero.                     *

 *                                                          *

 ************************************************************

 */

  while (FOREVER) {

    tstart = ReadClock();

    while (!thread[tid].tree && (!waiting || waiting->nprocs) && !Join(tid) &&

        !thread[tid].terminate);

    tend = ReadClock();

    if (!thread[tid].tree)

      thread[tid].tree = waiting;

    thread[tid].idle += tend - tstart;

    if (thread[tid].tree == waiting || thread[tid].terminate)

      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  *

 *  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.                            *

 *                                                          *

 ************************************************************

 */

    value =

        SearchMoveList(thread[tid].tree, thread[tid].tree->ply,

        thread[tid].tree->depth, thread[tid].tree->wtm,

        thread[tid].tree->alpha, thread[tid].tree->beta,

        thread[tid].tree->searched, thread[tid].tree->in_check, 0, parallel);

    tstart = ReadClock();

    Lock(thread[tid].tree->parent->lock);

    thread[tid].tree->parent->joinable = 0;

    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;

    tend = ReadClock();

    thread[tid].idle += tend - tstart;

  }

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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.                     *

 *                                                                             *

 *******************************************************************************

 */

void CopyFromParent(TREE * RESTRICT child) {

  TREE *parent = child->parent;

  int i, ply;

/*

 ************************************************************

 *                                                          *

 *  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.           *

 *                                                          *

 ************************************************************

 */

  ply = parent->ply;

  child->ply = ply;

  child->position = parent->position;

  for (i = 0; i <= rep_index + parent->ply; i++)

    child->rep_list[i] = parent->rep_list[i];

  for (i = ply - 1; i < MAXPLY; i++)

    child->killers[i] = parent->killers[i];

  for (i = 0; i < 4096; i++) {

    child->counter_move[i] = parent->counter_move[i];

    child->move_pair[i] = parent->move_pair[i];

  }

  for (i = ply - 1; i <= ply; i++) {

    child->curmv[i] = parent->curmv[i];

    child->pv[i] = parent->pv[i];

  }

  child->in_check = parent->in_check;

  child->last[ply] = child->move_list;

  child->status[ply] = parent->status[ply];

  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_hits = 0;

  child->extensions_done = 0;

  child->qchecks_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->wtm = parent->wtm;

  child->depth = parent->depth;

  child->searched = parent->searched;

  strcpy(child->root_move_text, parent->root_move_text);

  strcpy(child->remaining_moves_text, parent->remaining_moves_text);

}

/* modified 08/03/16 */

/*

 *******************************************************************************

 *                                                                             *

 *   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 i, ply = parent->ply, which;

/*

 ************************************************************

 *                                                          *

 *  The only concern here is to make sure that the info is  *

 *  only copied to the parent if our score is > than the    *

 *  parent value, and that we were not stopped for any      *

 *  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) {