src/split.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     split.c
   8
   9 Abstract:
  10
  11     This code is the glue needed to run a parallel search.  Let me
  12     encourage other chess programmers to read this code carefully.
  13     Implementing a parallel search is pretty easy and I procrastinated
  14     doing it for WAY too long because I was afraid to sink multiple
  15     months into coding it up.  It's not as hard as you think.  If you
  16     have a good handle on multi-threaded programming then you can do
  17     something that works pretty well in a week.
  18
  19     Here's my system (which is not original -- I believe this is the
  20     same idea that Bruce Moreland used for Ferret and I've been told
  21     it's simiar to what Bob Hyatt does in Crafty).  You want to split
  22     the search on all-nodes.  There is some overhead involved in
  23     splitting the tree and, after you paid the price, you do not want
  24     one of the moves failing high... because then you have to abort
  25     the split and return a fail high.
  26
  27     Once my search has one of these nodes, it calls in here to split
  28     the tree.  What's involved with splitting the tree is:
  29
  30         1. populating a "split node" with data about the position
  31            we are splitting in.
  32         2. grabbing zero or more idle "worker threads" to come help
  33            with the split.
  34         3. all threads searching under the split grab a move from
  35            the move list and search that move's subtree in parallel.
  36         4. when a subtree is evaluated... all threads update the
  37            split node with new information (i.e. raise alpha or, in
  38            the undesirable case that a thread failed high, toggles
  39            a flag in the split node to inform the rest of the
  40            searchers).
  41         5. before grabbing the next move, each thread updates its
  42            local alpha to pick up window-narrowing information
  43            encountered by other threads.
  44         6. goto step 3, stop when there are no more moves or
  45            thread finds a fail high.
  46
  47     ------------------------------------------------------------------
  48
  49     This is a quote from some win32 blog about the x86 memory model
  50     which I found helpful to read while I was thinking about
  51     multithreaded code in this module:
  52
  53     "The most familiar model is X86.  It's a relatively strong model.
  54      Stores are never reordered with respect to other stores.  But, in
  55      the absence of data dependence, loads can be reordered with
  56      respect to other loads and stores.  Many X86 developers don't
  57      realize that this reordering is possible, though it can lead to
  58      some nasty failures under stress on big MP machines.
  59
  60      In terms of the above, the memory model for X86 can be described as:
  61
  62         1. All stores are actually store.release (upward memory fence).
  63            This means that normal loads can be moved above the
  64            store.release but nothing can be moved below it.
  65         2. All loads are normal loads.
  66         3. Any use of the LOCK prefix (e.g. LOCK CMPXCHG or LOCK INC)
  67            creates a full memory fence."
  68
  69 Author:
  70
  71     Scott Gasch ([email protected]) 25 Jun 2004
  72
  73 Revision History:
  74
  75     $Id: split.c 345 2007-12-02 22:56:42Z scott $
  76
  77 **/
  78 #ifdef MP
  79
  80 #include "chess.h"
  81
  82 extern ULONG g_uIterateDepth;
  83 ULONG g_uNumHelperThreads = 0;
  84 #define MAX_SPLITS          (20)
  85 #define IDLE                ((ULONG)-1)
  86
  87 void
  88 HelpSearch(SEARCHER_THREAD_CONTEXT *ctx, ULONG u);
  89
  90 //
  91 // A struct that holds information about helper threads.
  92 //
  93 typedef struct _HELPER_THREAD
  94 {
  95     ULONG uHandle;
  96     volatile ULONG uAssignment;
  97     SEARCHER_THREAD_CONTEXT ctx;
  98 #ifdef PERF_COUNTERS
  99     UINT64 u64IdleCycles;
 100     UINT64 u64BusyCycles;
 101 #endif
 102 } HELPER_THREAD;
 103
 104 //
 105 // An array of these structs that is alloced dynamically so that N
 106 // cpus is not a hardcoded thing, the engine can scale N based on
 107 // where it is running.
 108 //
 109 static HELPER_THREAD *g_HelperThreads = NULL;
 110
 111 //
 112 // An array of structs that hold information about where we have split
 113 // the search tree.
 114 //
 115 static SPLIT_INFO g_SplitInfo[MAX_SPLITS];
 116
 117 //
 118 // In addition to this main split database lock each split entry has
 119 // its own private lock.  This way contention between searcher threads
 120 // operating on different split nodes is eliminated.
 121 //
 122 volatile static ULONG g_uSplitLock = 0;
 123 #define SPLITS_LOCKED (g_uSplitLock != 0)
 124 #define LOCK_SPLITS \
 125     AcquireSpinLock(&g_uSplitLock); \
 126     ASSERT(SPLITS_LOCKED);
 127 #define UNLOCK_SPLITS \
 128     ASSERT(SPLITS_LOCKED); \
 129     ReleaseSpinLock(&g_uSplitLock);
 130
 131 static ULONG g_uNumSplitsAvailable;
 132 volatile ULONG g_uNumHelpersAvailable;
 133
 134
 135 ULONG
 136 HelperThreadIdleLoop(IN ULONG uMyId)
 137 /**
 138
 139 Routine description:
 140
 141     The entry point of a helper thread.  It will spin in the idle loop
 142     here until another thread splits the search tree, sees that it is
 143     idle, and notifies it to come help by changing the assignment
 144     field in its struct.
 145
 146 Parameters:
 147
 148     ULONG uMyId : this thread's index in g_HelperThreads
 149
 150 Return value:
 151
 152     ULONG
 153
 154 **/
 155 {
 156     SEARCHER_THREAD_CONTEXT *ctx = &(g_HelperThreads[uMyId].ctx);
 157     ULONG u, v;
 158     MOVE mv;
 159     ULONG uIdleLoops = 0;
 160 #ifdef PERF_COUNTERS
 161     UINT64 u64Then;
 162     UINT64 u64Now;
 163 #endif
 164 #ifdef DEBUG
 165     POSITION board;
 166 #endif
 167     InitializeSearcherContext(NULL, ctx);
 168     ctx->uThreadNumber = uMyId + 1;
 169     do
 170     {
 171 #ifdef PERF_COUNTERS
 172         if (uIdleLoops == 0) u64Then = SystemReadTimeStampCounter();
 173 #endif
 174         //
 175         // Did someone tell us to come help?
 176         //
 177         if ((u = g_HelperThreads[uMyId].uAssignment) != IDLE)
 178         {
 179             //
 180             // By now the split info is populated.
 181             //
 182             uIdleLoops = 0;
 183             ReInitializeSearcherContext(&(g_SplitInfo[u].sRootPosition), ctx);
 184             ctx->pSplitInfo[0] = &(g_SplitInfo[u]);
 185             ctx->uPositional = g_SplitInfo[u].uSplitPositional;
 186
 187             //
 188             // Note: the main thread could have already exhausted the
 189             // split and decremented it from 3->2.  When we leave it
 190             // will fall to 1 and allow the main thread to continue.
 191             //
 192             ASSERT(g_SplitInfo[u].uNumThreadsHelping >= 2);
 193
 194             //
 195             // Get from the root of the search to the split position.
 196             // We do this instead of just initializing the searcher
 197             // context at the split node so that historic things like
 198             // draw detection still work in the helper threads.
 199             //
 200             v = 0;
 201             do
 202             {
 203                 ASSERT(v < MAX_PLY_PER_SEARCH);
 204                 mv.uMove = g_SplitInfo[u].mvPathToHere[v].uMove;
 205                 if (ILLEGALMOVE == mv.uMove) break;
 206 #ifdef DEBUG
 207                 if (mv.uMove)
 208                 {
 209                     ASSERT(SanityCheckMove(&ctx->sPosition, mv));
 210                 }
 211 #endif
 212                 if (FALSE == MakeMove(ctx, mv))
 213                 {
 214                     UtilPanic(CANNOT_INITIALIZE_SPLIT,
 215                               &ctx->sPosition,
 216                               (void *)mv.uMove,
 217                               &g_SplitInfo[u],
 218                               (void *)v,
 219                               __FILE__, __LINE__);
 220                 }
 221                 v++;
 222             }
 223             while(1);
 224 #ifdef DEBUG
 225             ASSERT(g_SplitInfo[u].uSplitPly == ctx->uPly);
 226             ASSERT(v > 0);
 227             ASSERT(IS_SAME_MOVE(g_SplitInfo[u].mvPathToHere[v-1],
 228                                 g_SplitInfo[u].mvLast));
 229             ASSERT(PositionsAreEquivalent(&(ctx->sPosition),
 230                                           &(g_SplitInfo[u].sSplitPosition)));
 231             VerifyPositionConsistency(&(ctx->sPosition), FALSE);
 232             memcpy(&board, &(ctx->sPosition), sizeof(POSITION));
 233 #endif
 234             //
 235             // Populate the move stack of this helper context to make
 236             // it look like it generated to moves at the split.  The
 237             // reason I do this is so that ComputeMoveExtension (which
 238             // looks at the move stack) will work at a split node even
 239             // if the context it gets is a helper thread's.
 240             //
 241             ctx->sMoveStack.uBegin[ctx->uPly] = 0;
 242             ctx->sMoveStack.uBegin[ctx->uPly + 1] =
 243                 ctx->sMoveStack.uEnd[ctx->uPly] = g_SplitInfo[u].uNumMoves;
 244
 245             for (v = 0;
 246                  v < g_SplitInfo[u].uNumMoves;
 247                  v++)
 248             {
 249                 ctx->sMoveStack.mvf[v] = g_SplitInfo[u].mvf[v];
 250                 ASSERT(SanityCheckMove(&ctx->sPosition,
 251                                        g_SplitInfo[u].mvf[v].mv));
 252             }
 253
 254             //
 255             // Go help with the search
 256             //
 257             HelpSearch(ctx, u);
 258             ASSERT(PositionsAreEquivalent(&board, &(ctx->sPosition)));
 259
 260             //
 261             // Done with this assignment, wrap up and go back to idle state
 262             //
 263             LOCK_SPLITS;
 264             g_HelperThreads[uMyId].uAssignment = IDLE;
 265             g_uNumHelpersAvailable++;
 266             UNLOCK_SPLITS;
 267 #ifdef PERF_COUNTERS
 268             u64Now = SystemReadTimeStampCounter();
 269             g_HelperThreads[uMyId].u64BusyCycles += (u64Now - u64Then);
 270 #endif
 271         }
 272 #if PERF_COUNTERS
 273         //
 274         // There was nothing for us to do, if that happens often
 275         // enough remember the idle cycles.
 276         //
 277         else
 278         {
 279             uIdleLoops++;
 280             if (uIdleLoops > 1000)
 281             {
 282                 u64Now = SystemReadTimeStampCounter();
 283                 LOCK_SPLITS;
 284                 g_HelperThreads[uMyId].u64IdleCycles += (u64Now - u64Then);
 285                 UNLOCK_SPLITS;
 286                 uIdleLoops = 0;
 287 #ifdef DEBUG
 288                 SystemDeferExecution(1);
 289 #endif
 290             }
 291         }
 292 #endif
 293     }
 294     while(FALSE == g_fExitProgram);
 295     Trace("HELPER THREAD: thread terminating.\n");
 296
 297     return(0);                                // ExitThread
 298 }
 299
 300
 301 FLAG
 302 InitializeParallelSearch(void)
 303 /**
 304
 305 Routine description:
 306
 307     This routine must be called before any thread can split the search
 308     tree because it sets up the parallel search system.
 309
 310 Parameters:
 311
 312     void
 313
 314 Return value:
 315
 316     FLAG
 317
 318 **/
 319 {
 320     ULONG u;
 321
 322     if (g_Options.uNumProcessors < 2) return(FALSE);
 323
 324     //
 325     // Initialize split entries
 326     //
 327     g_uSplitLock = 0;
 328     for (u = 0; u < MAX_SPLITS; u++)
 329     {
 330         memset(&(g_SplitInfo[u]), 0, sizeof(g_SplitInfo[u]));
 331     }
 332     g_uNumSplitsAvailable = MAX_SPLITS;
 333     ASSERT(NUM_SPLIT_PTRS_IN_CONTEXT <= MAX_SPLITS);
 334
 335     //
 336     // Create and initialize helper threads
 337     //
 338     g_uNumHelperThreads = g_Options.uNumProcessors - 1;
 339     ASSERT(g_uNumHelperThreads >= 1);
 340     g_HelperThreads = SystemAllocateMemory(sizeof(HELPER_THREAD) *
 341                                            g_uNumHelperThreads);
 342     ASSERT(g_HelperThreads != NULL);
 343     for (u = 0; u < g_uNumHelperThreads; u++)
 344     {
 345         memset(&(g_HelperThreads[u]), 0, sizeof(g_HelperThreads[u]));
 346         g_HelperThreads[u].uAssignment = IDLE;
 347         if (FALSE == SystemCreateThread(HelperThreadIdleLoop,
 348                                         u,
 349                                         &(g_HelperThreads[u].uHandle)))
 350         {
 351             UtilPanic(UNEXPECTED_SYSTEM_CALL_FAILURE,
 352                       NULL,
 353                       "creating a thread",
 354                       0,
 355                       NULL,
 356                       __FILE__, __LINE__);
 357         }
 358     }
 359     g_uNumHelpersAvailable = g_uNumHelperThreads;
 360     return(TRUE);
 361 }
 362
 363
 364 #ifdef PERF_COUNTERS
 365 void
 366 ClearHelperThreadIdleness(void)
 367 /**
 368
 369 Routine description:
 370
 371     Called at the start of a search, if PERF_COUNTERS is
 372     defined... this function's job is to reset the idleness counter
 373     for all helper threads.
 374
 375 Parameters:
 376
 377     void
 378
 379 Return value:
 380
 381     void
 382
 383 **/
 384 {
 385     ULONG u;
 386
 387     LOCK_SPLITS;
 388     for (u = 0; u < g_uNumHelperThreads; u++)
 389     {
 390         g_HelperThreads[u].u64BusyCycles =
 391             g_HelperThreads[u].u64IdleCycles = 0ULL;
 392     }
 393     UNLOCK_SPLITS;
 394 }
 395
 396
 397 void
 398 DumpHelperIdlenessReport(void)
 399 /**
 400
 401 Routine description:
 402
 403     Called at the end of a search, this function's job is to print
 404     out a report of how busy/idle each helper threads was.
 405
 406 Parameters:
 407
 408     void
 409
 410 Return value:
 411
 412     void
 413
 414 **/
 415 {
 416     ULONG u;
 417     double n, d;
 418
 419     for (u = 0;
 420          u < g_uNumHelperThreads;
 421          u++)
 422     {
 423         n = (double)g_HelperThreads[u].u64BusyCycles;
 424         d = (double)g_HelperThreads[u].u64IdleCycles;
 425         d += n;
 426         Trace("Helper thread %u: %5.2f percent busy.\n", u, (n / d) * 100.0);
 427     }
 428 }
 429 #endif
 430
 431
 432 FLAG
 433 CleanupParallelSearch(void)
 434 /**
 435
 436 Routine description:
 437
 438     Cleanup parallel search system before program shutdown.
 439
 440 Parameters:
 441
 442     void
 443
 444 Return value:
 445
 446     FLAG
 447
 448 **/
 449 {
 450     if (g_HelperThreads != NULL )
 451     {
 452         SystemFreeMemory(g_HelperThreads);
 453     }
 454     g_uNumHelperThreads = 0;
 455     return(TRUE);
 456 }
 457
 458
 459 SCORE
 460 StartParallelSearch(IN SEARCHER_THREAD_CONTEXT *ctx,
 461                     IN OUT SCORE *piAlpha,
 462                     IN SCORE iBeta,
 463                     IN OUT SCORE *piBestScore,
 464                     IN OUT MOVE *pmvBest,
 465                     IN ULONG uMoveNum,
 466                     IN INT iPositionExtend,
 467                     IN ULONG uDepth)
 468 {
 469 /**
 470
 471 Routine description:
 472
 473     This routine is called from the main Search (not RootSearch or QSearch)
 474     when:
 475
 476         1. it thinks the current search tree node looks like it could
 477            be searched in parallel -and-
 478
 479         2. it's likely that there are idle helper thread(s) to help.
 480
 481     It job is to find a free split node, populate it, find idle helper
 482     threads, assign them to help, and search this node in parallel.
 483     It _must_ be called after generating moves at this node.
 484
 485 Parameters:
 486
 487     SEARCHER_THREAD_CONTEXT *ctx : context of thread requesting split
 488     SCORE *piAlpha : in/out alpha of split node
 489     SCORE iBeta : in only (beta doesn't change) beta of split node
 490     SCORE *piBestScore : in/out best score seen so far at split node
 491     MOVE *pmvBest : in/out best move seen so far at split node
 492     ULONG uMoveNum : in next move number in ctx->sMoveStack
 493     INT iPositionExtend : in position based extensions for split node
 494     ULONG uDepth : in the depth we need to search to
 495
 496 Return value:
 497
 498     SCORE : the score of this split subtree, along with out params above
 499
 500 **/
 501     SCORE iScore;
 502     ULONG u, v;
 503     ULONG uSplitNum;
 504     ULONG uOldStart;
 505 #ifdef DEBUG
 506     POSITION board;
 507
 508     ASSERT(IS_VALID_SCORE(*piAlpha));
 509     ASSERT(IS_VALID_SCORE(iBeta));
 510     ASSERT(IS_VALID_SCORE(*piBestScore));
 511     ASSERT(*piBestScore > -INFINITY);
 512     ASSERT(pmvBest->uMove);
 513     ASSERT(*piAlpha < iBeta);
 514
 515     memcpy(&board, &(ctx->sPosition), sizeof(POSITION));
 516     VerifyPositionConsistency(&board, FALSE);
 517 #endif
 518
 519     //
 520     // Note: This is a lazy lock construction: search.c has peeked at
 521     // g_uNumHelperThreads before calling us and only calls when it
 522     // thinks there's a helper available.  (1) We could find that
 523     // there is no helper available now because of the race condition.
 524     // (2) On IA64 memory model this type of construct is
 525     // _not_supported_ (my understanding is that this is supported on
 526     // X86 and AMD64, though).
 527     //
 528     LOCK_SPLITS;
 529     for (u = 0; u < MAX_SPLITS; u++)
 530     {
 531         //
 532         // Try to find a vacant split
 533         //
 534         if (g_SplitInfo[u].uNumThreadsHelping == 0)
 535         {
 536             //
 537             // Found one, populate it.
 538             //
 539             ASSERT(g_uNumSplitsAvailable > 0);
 540             g_uNumSplitsAvailable--;
 541
 542             //
 543             // We initialize this to two to double-reference this
 544             // split node.  This guarantees we are the last ones
 545             // holding a reference to it (since we want to be the last
 546             // one out of this split node)
 547             //
 548             g_SplitInfo[u].uNumThreadsHelping = 2;
 549
 550             //
 551             // Store the path from the root to the split node and the
 552             // root position to start at.  This is done so that
 553             // ponders that convert into searches don't crash us and
 554             // so that helper threads can detect repeated positions
 555             // before the split point.
 556             //
 557             ASSERT(ctx->uPly >= 1);
 558             ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH);
 559             for (v = 0; v < ctx->uPly; v++)
 560             {
 561                 g_SplitInfo[u].mvPathToHere[v] = ctx->sPlyInfo[v].mv;
 562             }
 563             g_SplitInfo[u].mvPathToHere[v].uMove = ILLEGALMOVE;
 564             ASSERT(v >= 1);
 565             g_SplitInfo[u].mvLast = g_SplitInfo[u].mvPathToHere[v-1];
 566             memcpy(&(g_SplitInfo[u].sRootPosition),
 567                    GetRootPosition(),
 568                    sizeof(POSITION));
 569 #if DEBUG
 570             g_SplitInfo[u].uSplitPly = ctx->uPly;
 571             memcpy(&(g_SplitInfo[u].sSplitPosition),
 572                    &(ctx->sPosition),
 573                    sizeof(POSITION));
 574 #endif
 575             //
 576             // What has happened here is that another thread has
 577             // triggered the "stop searching" bit in the move timer.
 578             // This also means that the root position may have changed
 579             // and therefore the split we just populated can be
 580             // useless.  Before we grab any helper threads, see if we
 581             // need to bail out of this split.
 582             //
 583             if (g_MoveTimer.bvFlags & TIMER_STOPPING)
 584             {
 585                 g_uNumSplitsAvailable++;
 586                 g_SplitInfo[u].uNumThreadsHelping = 0;
 587                 UNLOCK_SPLITS;
 588                 return(INVALID_SCORE);
 589             }
 590
 591             //
 592             // More split node initialization
 593             //
 594             g_SplitInfo[u].uLock = 0;
 595             g_SplitInfo[u].fTerminate = FALSE;
 596             g_SplitInfo[u].uDepth = uDepth;
 597             g_SplitInfo[u].iPositionExtend = iPositionExtend;
 598             g_SplitInfo[u].iAlpha = *piAlpha;
 599             g_SplitInfo[u].iBeta = iBeta;
 600             g_SplitInfo[u].uSplitPositional = ctx->uPositional;
 601             g_SplitInfo[u].sSearchFlags = ctx->sSearchFlags;
 602             ASSERT(FALSE == ctx->sSearchFlags.fAvoidNullmove);
 603             g_SplitInfo[u].mvBest = *pmvBest;
 604             g_SplitInfo[u].iBestScore = *piBestScore;
 605             ASSERT(g_SplitInfo[u].iBestScore <= g_SplitInfo[u].iAlpha);
 606             g_SplitInfo[u].sCounters.tree.u64TotalNodeCount = 0;
 607             g_SplitInfo[u].sCounters.tree.u64BetaCutoffs = 0;
 608             g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove = 0;
 609             g_SplitInfo[u].PV[0] = NULLMOVE;
 610
 611             //
 612             // Copy the remaining moves to be searched from the
 613             // searcher context that called us into the split node.
 614             // Note: this thread must have already called
 615             // GenerateMoves at the split node!
 616             //
 617             uOldStart = ctx->sMoveStack.uBegin[ctx->uPly];
 618             g_SplitInfo[u].uAlreadyDone = uMoveNum - uOldStart + 1;
 619             ASSERT(g_SplitInfo[u].uAlreadyDone >= 1);
 620             ctx->sMoveStack.uBegin[ctx->uPly] = uMoveNum;
 621             for (v = uMoveNum, g_SplitInfo[u].uRemainingMoves = 0;
 622                  (v < ctx->sMoveStack.uEnd[ctx->uPly]);
 623                  v++, g_SplitInfo[u].uRemainingMoves++)
 624             {
 625                 ASSERT(g_SplitInfo[u].uRemainingMoves >= 0);
 626                 ASSERT(g_SplitInfo[u].uRemainingMoves < MAX_MOVES_PER_PLY);
 627
 628                 //
 629                 // If we fail high at this node we have done a lot of
 630                 // work for naught.  We also want to know as soon as
 631                 // possible so that we can vacate this split point,
 632                 // free up a worker thread and get back to the main
 633                 // search.  So forget about the SEARCH_SORT_LIMIT
 634                 // stuff here and sort the whole list of moves from
 635                 // best..worst.
 636                 //
 637                 SelectBestWithHistory(ctx, v);
 638                 ctx->sMoveStack.mvf[v].mv.bvFlags |=
 639                     WouldGiveCheck(ctx, ctx->sMoveStack.mvf[v].mv);
 640                 ASSERT(!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED));
 641                 g_SplitInfo[u].mvf[g_SplitInfo[u].uRemainingMoves] =
 642                     ctx->sMoveStack.mvf[v];
 643 #ifdef DEBUG
 644                 ctx->sMoveStack.mvf[v].bvFlags |= MVF_MOVE_SEARCHED;
 645 #endif
 646             }
 647             g_SplitInfo[u].uOnDeckMove = 0;
 648             g_SplitInfo[u].uNumMoves = g_SplitInfo[u].uRemainingMoves;
 649 #ifdef DEBUG
 650             for (v = uMoveNum;
 651                  v < ctx->sMoveStack.uEnd[ctx->uPly];
 652                  v++)
 653             {
 654                 ASSERT(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED);
 655                 ASSERT(SanityCheckMove(&ctx->sPosition,
 656                                        ctx->sMoveStack.mvf[v].mv));
 657             }
 658 #endif
 659
 660             //
 661             // See if we can get some help here or we have to go it
 662             // alone.  Note: past this point the split we are using
 663             // may have threads under it -- be careful.
 664             //
 665             for (v = 0; v < g_uNumHelperThreads; v++)
 666             {
 667                 if (g_HelperThreads[v].uAssignment == IDLE)
 668                 {
 669                     //
 670                     // Note: there could already be a thread searching
 671                     // this split; we must obtain its lock now to mess
 672                     // with the helper count.
 673                     //
 674                     AcquireSpinLock(&(g_SplitInfo[u].uLock));
 675                     g_SplitInfo[u].uNumThreadsHelping += 1;
 676                     ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 677                     ASSERT(g_SplitInfo[u].uNumThreadsHelping > 2);
 678                     ASSERT(g_uNumHelpersAvailable > 0);
 679                     g_uNumHelpersAvailable -= 1;
 680                     ASSERT(g_uNumHelpersAvailable >= 0);
 681                     ASSERT(g_uNumHelpersAvailable < g_uNumHelperThreads);
 682                     g_HelperThreads[v].uAssignment = u;
 683                 }
 684             }
 685             UNLOCK_SPLITS;
 686
 687             //
 688             // Update the context of the thread that is initiating the
 689             // split with a pointer to the split info node we are using.
 690             //
 691             for (uSplitNum = 0;
 692                  uSplitNum < NUM_SPLIT_PTRS_IN_CONTEXT;
 693                  uSplitNum++)
 694             {
 695                 if (ctx->pSplitInfo[uSplitNum] == NULL)
 696                 {
 697                     ctx->pSplitInfo[uSplitNum] = &(g_SplitInfo[u]);
 698                     break;
 699                 }
 700             }
 701             if (uSplitNum >= NUM_SPLIT_PTRS_IN_CONTEXT)
 702             {
 703                 ASSERT(FALSE);
 704                 return(INVALID_SCORE);
 705             }
 706             ASSERT(ctx->pSplitInfo[uSplitNum] == &(g_SplitInfo[u]));
 707
 708             //
 709             // Go search it
 710             //
 711             INC(ctx->sCounters.parallel.uNumSplits);
 712             HelpSearch(ctx, u);
 713
 714             //
 715             // We are done searching under this node... make sure all
 716             // helpers are done too.  When everyone is finished the
 717             // refcount on this split node will be one because every
 718             // thread decremented it once and we double referenced
 719             // it initially.
 720             //
 721             while(g_SplitInfo[u].uNumThreadsHelping != 1)
 722             {
 723                 ASSERT(g_SplitInfo[u].uNumThreadsHelping != 0);
 724                 if (g_fExitProgram) break;
 725             }
 726
 727             //
 728             // Note: past this point we are the only ones using the
 729             // split until we return it to the pool by making its
 730             // refcount zero again.
 731             //
 732 #ifdef DEBUG
 733             ASSERT((g_SplitInfo[u].uNumThreadsHelping == 1) ||
 734                    (g_fExitProgram));
 735             SystemDeferExecution(rand() % 2);
 736             ASSERT((g_SplitInfo[u].uNumThreadsHelping == 1) ||
 737                    (g_fExitProgram));
 738             if (g_SplitInfo[u].iBestScore < g_SplitInfo[u].iBeta)
 739             {
 740                 for (v = 0;
 741                      v < g_SplitInfo[u].uRemainingMoves;
 742                      v++)
 743                 {
 744                     ASSERT(g_SplitInfo[u].mvf[v].mv.uMove);
 745                     ASSERT(g_SplitInfo[u].mvf[v].bvFlags & MVF_MOVE_SEARCHED);
 746                 }
 747             }
 748 #endif
 749 #ifdef PERF_COUNTERS
 750             //
 751             // Grab counters.  Technically we should do with under a
 752             // lock b/c we want to ensure that any pending memory
 753             // operations from other cpus are flushed.  But I don't
 754             // really care too much about these counters and am trying
 755             // to reduce lock contention.
 756             //
 757             if (TRUE == g_SplitInfo[u].fTerminate)
 758             {
 759                 ASSERT(g_SplitInfo[u].iBestScore >= g_SplitInfo[u].iBeta);
 760                 INC(ctx->sCounters.parallel.uNumSplitsTerminated);
 761             }
 762             ctx->sCounters.tree.u64BetaCutoffs =
 763                 g_SplitInfo[u].sCounters.tree.u64BetaCutoffs;
 764             ctx->sCounters.tree.u64BetaCutoffsOnFirstMove =
 765                 g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove;
 766 #endif
 767             //
 768             // Pop off the split info ptr from the stack in the thread's
 769             // context.
 770             //
 771             ASSERT(ctx->pSplitInfo[uSplitNum] == &(g_SplitInfo[u]));
 772             ctx->pSplitInfo[uSplitNum] = NULL;
 773
 774             //
 775             // Grab alpha, bestscore, bestmove, PV etc...  The lock
 776             // needs to be here to flush any pending memory writes
 777             // from other processors.
 778             //
 779             LOCK_SPLITS;
 780             ctx->sCounters.tree.u64TotalNodeCount =
 781                 g_SplitInfo[u].sCounters.tree.u64TotalNodeCount;
 782             iScore = *piBestScore = g_SplitInfo[u].iBestScore;
 783             *pmvBest = g_SplitInfo[u].mvBest;
 784             if ((*piAlpha < iScore) && (iScore < iBeta))
 785             {
 786                 ASSERT(IS_SAME_MOVE(*pmvBest, g_SplitInfo[u].PV[0]));
 787                 ASSERT((*pmvBest).uMove != 0);
 788                 v = 0;
 789                 do
 790                 {
 791                     ASSERT((ctx->uPly + v) < MAX_PLY_PER_SEARCH);
 792                     ASSERT(v < MAX_PLY_PER_SEARCH);
 793                     ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly+v] =
 794                         g_SplitInfo[u].PV[v];
 795                     if (0 == g_SplitInfo[u].PV[v].uMove) break;
 796                     v++;
 797                 }
 798                 while(1);
 799             }
 800             *piAlpha = g_SplitInfo[u].iAlpha;
 801             ASSERT(iBeta == g_SplitInfo[u].iBeta);
 802             g_uNumSplitsAvailable++;
 803             g_SplitInfo[u].uNumThreadsHelping = 0;
 804             UNLOCK_SPLITS;
 805             ctx->sMoveStack.uBegin[ctx->uPly] = uOldStart;
 806
 807 #ifdef DEBUG
 808             ASSERT(PositionsAreEquivalent(&board, &ctx->sPosition));
 809             VerifyPositionConsistency(&ctx->sPosition, FALSE);
 810             ASSERT(IS_VALID_SCORE(iScore) || WE_SHOULD_STOP_SEARCHING);
 811 #endif
 812             return(iScore);
 813         }
 814     }
 815
 816     //
 817     // There was no split available for us; unlock and continue in
 818     // search.
 819     //
 820     UNLOCK_SPLITS;
 821     return(INVALID_SCORE);
 822 }
 823
 824
 825 static void
 826 _UpdateSplitInfo(IN SEARCHER_THREAD_CONTEXT *ctx,
 827                  IN MOVE mv,
 828                  IN SCORE iScore,
 829                  IN ULONG u)
 830 /**
 831
 832 Routine description:
 833
 834     We think we have some information learned from search to store in
 835     the split node.  Take the lock and see if we really do.
 836
 837 Parameters:
 838
 839     SEARCHER_THREAD_CONTEXT *ctx : context of thread updating split
 840     MOVE mv : move it just searched
 841     SCORE iScore : score of the move's subtree
 842     ULONG u : split node number
 843
 844 Return value:
 845
 846     static void
 847
 848 **/
 849 {
 850     ULONG v;
 851
 852     AcquireSpinLock(&(g_SplitInfo[u].uLock));
 853
 854     //
 855     // See if this split is shutting down
 856     //
 857     if (TRUE == g_SplitInfo[u].fTerminate)
 858     {
 859         ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 860         return;
 861     }
 862
 863     if (iScore > g_SplitInfo[u].iBestScore)
 864     {
 865         //
 866         // We found a move better than the best so far, so we want to
 867         // update the split node and possibly raise alpha.
 868         //
 869         g_SplitInfo[u].iBestScore = iScore;
 870         g_SplitInfo[u].mvBest = mv;
 871         if (iScore > g_SplitInfo[u].iAlpha)
 872         {
 873             if (iScore >= g_SplitInfo[u].iBeta)
 874             {
 875                 //
 876                 // We failed high so we want to update the split node
 877                 //
 878                 g_SplitInfo[u].fTerminate = TRUE;
 879                 g_SplitInfo[u].PV[0] = NULLMOVE;
 880                 ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 881                 return;
 882             }
 883
 884             //
 885             // Normal PV move, update the split's PV.
 886             //
 887             g_SplitInfo[u].iAlpha = iScore;
 888             UpdatePV(ctx, mv);
 889             ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH);
 890             ASSERT(ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly].uMove);
 891             for (v = 0; v < MAX_PLY_PER_SEARCH; v++)
 892             {
 893                 ASSERT((ctx->uPly + v) < MAX_PLY_PER_SEARCH);
 894                 mv = ctx->sPlyInfo[ctx->uPly].PV[ctx->uPly + v];
 895                 g_SplitInfo[u].PV[v] = mv;
 896                 if (0 == mv.uMove) break;
 897             }
 898         }
 899     }
 900     ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 901 }
 902
 903
 904 static void
 905 _SetFinalStats(IN SEARCHER_THREAD_CONTEXT *ctx,
 906                IN ULONG u)
 907 /**
 908
 909 Routine description:
 910
 911     We are exiting the split node (because it ran out of moves or
 912     because someone failed high).  Update some stats on the way out.
 913
 914 Parameters:
 915
 916     SEARCHER_THREAD_CONTEXT *ctx,
 917     ULONG u
 918
 919 Return value:
 920
 921     static void
 922
 923 **/
 924 {
 925     //
 926     // Before we stop searching this node, update some stuff.
 927     //
 928     AcquireSpinLock(&(g_SplitInfo[u].uLock));
 929
 930     //
 931     // Counters to persist in the main counter struct via the split.
 932     //
 933     g_SplitInfo[u].sCounters.tree.u64TotalNodeCount +=
 934         ctx->sCounters.tree.u64TotalNodeCount;
 935     g_SplitInfo[u].sCounters.tree.u64BetaCutoffs +=
 936         ctx->sCounters.tree.u64BetaCutoffs;
 937     g_SplitInfo[u].sCounters.tree.u64BetaCutoffsOnFirstMove +=
 938         ctx->sCounters.tree.u64BetaCutoffsOnFirstMove;
 939
 940     //
 941     // TODO: Any other counters we care about?
 942     //
 943
 944     //
 945     // IDEA: Save the killers from this context to bring back to main
 946     //
 947
 948     //
 949     // Decrement threadcount in this split.  Note: the main thread
 950     // incremented it by two.
 951     //
 952     ASSERT((g_SplitInfo[u].uNumThreadsHelping > 1) || (g_fExitProgram));
 953     g_SplitInfo[u].uNumThreadsHelping -= 1;
 954     ASSERT((g_SplitInfo[u].uNumThreadsHelping >= 1) || (g_fExitProgram));
 955     ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 956 }
 957
 958
 959 static MOVE
 960 _GetNextParallelMove(OUT SCORE *piAlpha,
 961                      OUT SCORE *piBestScore,
 962                      OUT ULONG *puMoveNumber,
 963                      IN ULONG u)
 964 /**
 965
 966 Routine description:
 967
 968     Retrieve the next parallel move to search at the split node.  Also
 969     update alpha and bestscore.
 970
 971 Parameters:
 972
 973     SCORE *piAlpha : current alpha
 974     SCORE *piBestScore : current bestscore
 975     ULONG u : split number
 976
 977 Return value:
 978
 979     static MOVE
 980
 981 **/
 982 {
 983     MOVE mv = {0};
 984
 985     AcquireSpinLock(&(g_SplitInfo[u].uLock));
 986     if (g_SplitInfo[u].fTerminate)
 987     {
 988         ReleaseSpinLock(&(g_SplitInfo[u].uLock));
 989         return(mv);
 990     }
 991
 992     if (g_SplitInfo[u].uRemainingMoves != 0)
 993     {
 994         //
 995         // There is another move to search, get it.
 996         //
 997         mv = g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].mv;
 998 #ifdef DEBUG
 999         ASSERT(!(g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags &
1000                  MVF_MOVE_SEARCHED));
1001         g_SplitInfo[u].mvf[g_SplitInfo[u].uOnDeckMove].bvFlags |=
1002             MVF_MOVE_SEARCHED;
1003         ASSERT(mv.uMove);
1004         ASSERT(SanityCheckMove(&g_SplitInfo[u].sSplitPosition, mv));
1005 #endif
1006         g_SplitInfo[u].uRemainingMoves--;
1007         *puMoveNumber = g_SplitInfo[u].uOnDeckMove;
1008         g_SplitInfo[u].uOnDeckMove++;
1009     }
1010     *piAlpha = g_SplitInfo[u].iAlpha;
1011     *piBestScore = g_SplitInfo[u].iBestScore;
1012     ReleaseSpinLock(&(g_SplitInfo[u].uLock));
1013     ASSERT(*piBestScore <= *piAlpha);
1014     return(mv);
1015 }
1016
1017
1018 void
1019 HelpSearch(IN OUT SEARCHER_THREAD_CONTEXT *ctx,
1020            IN ULONG u)
1021 /**
1022
1023 Routine description:
1024
1025     Help search the split position.
1026
1027 Parameters:
1028
1029     SEARCHER_THREAD_CONTEXT *ctx : thread context
1030     ULONG u : the split index to help search
1031
1032 Return value:
1033
1034     void
1035
1036 **/
1037 {
1038     SCORE iScore;
1039     SCORE iAlpha = 0;
1040     SCORE iBeta;
1041     SCORE iBestScore = 0;
1042     SCORE iRoughEval;
1043     ULONG uOrigDepth;
1044     ULONG uDepth;
1045     ULONG uMoveNum = 0;
1046     INT iOrigExtend;
1047     INT iExtend;
1048     MOVE mv;
1049 #ifdef DEBUG
1050     POSITION board;
1051
1052     memcpy(&board, &ctx->sPosition, sizeof(POSITION));
1053     ASSERT(PositionsAreEquivalent(&board, &g_SplitInfo[u].sSplitPosition));
1054 #endif
1055
1056     iOrigExtend = g_SplitInfo[u].iPositionExtend;
1057     iBeta = g_SplitInfo[u].iBeta;
1058     uOrigDepth = g_SplitInfo[u].uDepth;
1059     ctx->sSearchFlags = g_SplitInfo[u].sSearchFlags;
1060     do
1061     {
1062         iExtend = iOrigExtend;
1063         uDepth = uOrigDepth;
1064         ASSERT(ctx->uPly == g_SplitInfo[u].uSplitPly);
1065
1066         mv = _GetNextParallelMove(&iAlpha,
1067                                   &iBestScore,
1068                                   &uMoveNum,
1069                                   u);
1070         if (mv.uMove == 0) break;              // Split is terminating
1071
1072         ASSERT(IS_VALID_SCORE(iBestScore));
1073         ASSERT(uMoveNum < MAX_MOVES_PER_PLY);
1074         ASSERT(IS_SAME_MOVE(mv,
1075           ctx->sMoveStack.mvf[ctx->sMoveStack.uBegin[ctx->uPly]+uMoveNum].mv));
1076         ASSERT(uDepth <= MAX_DEPTH_PER_SEARCH);
1077         ASSERT(IS_VALID_SCORE(iAlpha));
1078         ASSERT(IS_VALID_SCORE(iBeta));
1079         ASSERT(iAlpha < iBeta);
1080         ASSERT(iExtend >= -ONE_PLY);
1081         ASSERT(iExtend <= +ONE_PLY);
1082
1083         if (MakeMove(ctx, mv))
1084         {
1085             ASSERT((IS_CHECKING_MOVE(mv) &&
1086                     InCheck(&ctx->sPosition, ctx->sPosition.uToMove)) ||
1087                    (!IS_CHECKING_MOVE(mv) &&
1088                     !InCheck(&ctx->sPosition, ctx->sPosition.uToMove)));
1089             iRoughEval = GetRoughEvalScore(ctx, iAlpha, iBeta, TRUE);
1090
1091             // Compute extension
1092             ComputeMoveExtension(ctx,
1093                                  iAlpha,
1094                                  iBeta,
1095                                  (ctx->sMoveStack.uBegin[ctx->uPly - 1] +
1096                                   uMoveNum),
1097                                  iRoughEval,
1098                                  uDepth,
1099                                  &iExtend);
1100
1101             //
1102             // Decide whether to history prune
1103             //
1104             if (TRUE == WeShouldDoHistoryPruning(iRoughEval,
1105                                                  iAlpha,
1106                                                  iBeta,
1107                                                  ctx,
1108                                                  uDepth,
1109                                                  (g_SplitInfo[u].uAlreadyDone +
1110                                                   uMoveNum + 1),
1111                                                  mv,
1112                                                  (g_SplitInfo[u].uAlreadyDone +
1113                                                   uMoveNum + 1),
1114                                                  iExtend))
1115             {
1116                 ASSERT(iExtend == 0);
1117                 iExtend = -ONE_PLY;
1118                 ctx->sPlyInfo[ctx->uPly].iExtensionAmount = -ONE_PLY;
1119             }
1120
1121             //
1122             // Compute next depth
1123             //
1124             uDepth = uDepth - ONE_PLY + iExtend;
1125             if (uDepth >= MAX_DEPTH_PER_SEARCH) uDepth = 0;
1126
1127             iScore = -Search(ctx, -iAlpha - 1, -iAlpha, uDepth);
1128             if ((iAlpha < iScore) && (iScore < iBeta))
1129             {
1130                 iScore = -Search(ctx, -iBeta, -iAlpha, uDepth);
1131             }
1132
1133             //
1134             // Decide whether to research reduced branches to full depth.
1135             //
1136             if ((iExtend < 0) && (iScore >= iBeta))
1137             {
1138                 uDepth += ONE_PLY;
1139                 ctx->sPlyInfo[ctx->uPly].iExtensionAmount = 0;
1140                 iScore = -Search(ctx, -iBeta, -iAlpha, uDepth);
1141             }
1142             UnmakeMove(ctx, mv);
1143             ASSERT(PositionsAreEquivalent(&ctx->sPosition, &board));
1144             if (TRUE == g_SplitInfo[u].fTerminate) break;
1145             if (iScore > iBestScore)
1146             {
1147                 _UpdateSplitInfo(ctx, mv, iScore, u);
1148             }
1149         }
1150     }
1151     while(1);
1152     _SetFinalStats(ctx, u);
1153 }
1154 #endif