X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fthread.cpp;h=7507ded119e5329f5df4cb9170ce5e79769c54d1;hp=002819de566ce71a2c91e2566ca481bf1376445c;hb=6088ac210883c272832360f28c8922ff1514ef87;hpb=339e1b49f619ceffa75019e196adf4de74b32cce diff --git a/src/thread.cpp b/src/thread.cpp index 002819de..7507ded1 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -17,213 +17,271 @@ along with this program. If not, see . */ +#include #include +#include "movegen.h" +#include "search.h" #include "thread.h" #include "ucioption.h" -ThreadsManager ThreadsMgr; // Global object definition +using namespace Search; -namespace { +ThreadsManager Threads; // Global object - // init_thread() is the function which is called when a new thread is - // launched. It simply calls the idle_loop() function with the supplied - // threadID. There are two versions of this function; one for POSIX - // threads and one for Windows threads. +namespace { extern "C" { -#if !defined(_MSC_VER) + // start_routine() is the C function which is called when a new thread + // is launched. It simply calls idle_loop() of the supplied thread. The first + // and last thread are special. First one is the main search thread while the + // last one mimics a timer, they run in main_loop() and timer_loop(). - void* init_thread(void* threadID) { +#if defined(_WIN32) || defined(_WIN64) + DWORD WINAPI start_routine(LPVOID thread) { +#else + void* start_routine(void* thread) { +#endif - ThreadsMgr.idle_loop(*(int*)threadID, NULL); - return NULL; - } + Thread* th = (Thread*)thread; -#else + if (th->threadID == 0) + th->main_loop(); - DWORD WINAPI init_thread(LPVOID threadID) { + else if (th->threadID == MAX_THREADS) + th->timer_loop(); + + else + th->idle_loop(NULL); - ThreadsMgr.idle_loop(*(int*)threadID, NULL); return 0; } -#endif +} } + + +// Thread::timer_loop() is where the timer thread waits maxPly milliseconds and +// then calls do_timer_event(). If maxPly is 0 thread sleeps until is woken up. +extern void check_time(); +void Thread::timer_loop() { + + while (!do_exit) + { + lock_grab(sleepLock); + timed_wait(sleepCond, sleepLock, maxPly ? maxPly : INT_MAX); + lock_release(sleepLock); + check_time(); + } } -// read_uci_options() updates number of active threads and other internal -// parameters according to the UCI options values. It is called before -// to start a new search. +// Thread::main_loop() is where the main thread is parked waiting to be started +// when there is a new search. Main thread will launch all the slave threads. -void ThreadsManager::read_uci_options() { +void Thread::main_loop() { + + while (true) + { + lock_grab(sleepLock); + + do_sleep = true; // Always return to sleep after a search + is_searching = false; - maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value(); - minimumSplitDepth = Options["Minimum Split Depth"].value() * ONE_PLY; - useSleepingThreads = Options["Use Sleeping Threads"].value(); - activeThreads = Options["Threads"].value(); + while (do_sleep && !do_exit) + { + cond_signal(Threads.sleepCond); // Wake up UI thread if needed + cond_wait(sleepCond, sleepLock); + } + + lock_release(sleepLock); + + if (do_exit) + return; + + is_searching = true; + + Search::think(); + } } -// init_threads() is called during startup. Initializes locks and condition -// variables and launches all threads sending them immediately to sleep. +// Thread::wake_up() wakes up the thread, normally at the beginning of the search +// or, if "sleeping threads" is used, when there is some work to do. -void ThreadsManager::init_threads() { +void Thread::wake_up() { - int arg[MAX_THREADS]; + lock_grab(sleepLock); + cond_signal(sleepCond); + lock_release(sleepLock); +} - // This flag is needed to properly end the threads when program exits - allThreadsShouldExit = false; - // Threads will sent to sleep as soon as created, only main thread is kept alive - activeThreads = 1; - threads[0].state = THREAD_SEARCHING; +// Thread::wait_for_stop_or_ponderhit() is called when the maximum depth is +// reached while the program is pondering. The point is to work around a wrinkle +// in the UCI protocol: When pondering, the engine is not allowed to give a +// "bestmove" before the GUI sends it a "stop" or "ponderhit" command. We simply +// wait here until one of these commands (that raise StopRequest) is sent and +// then return, after which the bestmove and pondermove will be printed. - // Allocate pawn and material hash tables for main thread - init_hash_tables(); +void Thread::wait_for_stop_or_ponderhit() { - lock_init(&mpLock); + Signals.stopOnPonderhit = true; - // Initialize thread and split point locks - for (int i = 0; i < MAX_THREADS; i++) - { - lock_init(&threads[i].sleepLock); - cond_init(&threads[i].sleepCond); + lock_grab(sleepLock); - for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) - lock_init(&(threads[i].splitPoints[j].lock)); - } + while (!Signals.stop) + cond_wait(sleepCond, sleepLock); - // Create and startup all the threads but the main that is already running - for (int i = 1; i < MAX_THREADS; i++) - { - threads[i].state = THREAD_INITIALIZING; - arg[i] = i; + lock_release(sleepLock); +} -#if !defined(_MSC_VER) - pthread_t pthread[1]; - bool ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0); - pthread_detach(pthread[0]); -#else - bool ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL); -#endif - if (!ok) - { - std::cout << "Failed to create thread number " << i << std::endl; - exit(EXIT_FAILURE); - } - // Wait until the thread has finished launching and is gone to sleep - while (threads[i].state == THREAD_INITIALIZING) {} - } +// cutoff_occurred() checks whether a beta cutoff has occurred in the current +// active split point, or in some ancestor of the split point. + +bool Thread::cutoff_occurred() const { + + for (SplitPoint* sp = curSplitPoint; sp; sp = sp->parent) + if (sp->cutoff) + return true; + + return false; } -// exit_threads() is called when the program exits. It makes all the -// helper threads exit cleanly. +// is_available_to() checks whether the thread is available to help the thread with +// threadID "master" at a split point. An obvious requirement is that thread must be +// idle. With more than two threads, this is not by itself sufficient: If the thread +// is the master of some active split point, it is only available as a slave to the +// threads which are busy searching the split point at the top of "slave"'s split +// point stack (the "helpful master concept" in YBWC terminology). -void ThreadsManager::exit_threads() { +bool Thread::is_available_to(int master) const { - // Force the woken up threads to exit idle_loop() and hence terminate - allThreadsShouldExit = true; + if (is_searching) + return false; - for (int i = 0; i < MAX_THREADS; i++) - { - // Wake up all the threads and waits for termination - if (i != 0) - { - threads[i].wake_up(); - while (threads[i].state != THREAD_TERMINATED) {} - } + // Make a local copy to be sure doesn't become zero under our feet while + // testing next condition and so leading to an out of bound access. + int spCnt = splitPointsCnt; - // Now we can safely destroy the locks and wait conditions - lock_destroy(&threads[i].sleepLock); - cond_destroy(&threads[i].sleepCond); + // No active split points means that the thread is available as a slave for any + // other thread otherwise apply the "helpful master" concept if possible. + return !spCnt || (splitPoints[spCnt - 1].slavesMask & (1ULL << master)); +} - for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) - lock_destroy(&(threads[i].splitPoints[j].lock)); - } - lock_destroy(&mpLock); +// read_uci_options() updates internal threads parameters from the corresponding +// UCI options. It is called before to start a new search. + +void ThreadsManager::read_uci_options() { + + maxThreadsPerSplitPoint = Options["Max Threads per Split Point"]; + minimumSplitDepth = Options["Min Split Depth"] * ONE_PLY; + useSleepingThreads = Options["Use Sleeping Threads"]; } -// init_hash_tables() dynamically allocates pawn and material hash tables -// according to the number of active threads. This avoids preallocating -// memory for all possible threads if only few are used as, for instance, -// on mobile devices where memory is scarce and allocating for MAX_THREADS -// threads could even result in a crash. +// set_size() changes the number of active threads and raises do_sleep flag for +// all the unused threads that will go immediately to sleep. -void ThreadsManager::init_hash_tables() { +void ThreadsManager::set_size(int cnt) { - for (int i = 0; i < activeThreads; i++) - { - threads[i].pawnTable.init(); - threads[i].materialTable.init(); - } + assert(cnt > 0 && cnt < MAX_THREADS); + + activeThreads = cnt; + + for (int i = 0; i < MAX_THREADS; i++) + if (i < activeThreads) + { + // Dynamically allocate pawn and material hash tables according to the + // number of active threads. This avoids preallocating memory for all + // possible threads if only few are used. + threads[i].pawnTable.init(); + threads[i].materialTable.init(); + threads[i].maxPly = 0; + + threads[i].do_sleep = false; + + if (!useSleepingThreads) + threads[i].wake_up(); + } + else + threads[i].do_sleep = true; } -// cutoff_at_splitpoint() checks whether a beta cutoff has occurred in -// the thread's currently active split point, or in some ancestor of -// the current split point. +// init() is called during startup. Initializes locks and condition variables +// and launches all threads sending them immediately to sleep. + +void ThreadsManager::init() { + + cond_init(sleepCond); + lock_init(splitLock); -bool ThreadsManager::cutoff_at_splitpoint(int threadID) const { + for (int i = 0; i <= MAX_THREADS; i++) + { + lock_init(threads[i].sleepLock); + cond_init(threads[i].sleepCond); + + for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++) + lock_init(threads[i].splitPoints[j].lock); + } - assert(threadID >= 0 && threadID < activeThreads); + // Allocate main thread tables to call evaluate() also when not searching + threads[0].pawnTable.init(); + threads[0].materialTable.init(); - SplitPoint* sp = threads[threadID].splitPoint; + // Create and launch all the threads, threads will go immediately to sleep + for (int i = 0; i <= MAX_THREADS; i++) + { + threads[i].is_searching = false; + threads[i].do_sleep = (i != 0); // Avoid a race with start_thinking() + threads[i].threadID = i; - for ( ; sp && !sp->betaCutoff; sp = sp->parent) {} - return sp != NULL; + if (!thread_create(threads[i].handle, start_routine, threads[i])) + { + std::cerr << "Failed to create thread number " << i << std::endl; + ::exit(EXIT_FAILURE); + } + } } -// thread_is_available() checks whether the thread with threadID "slave" is -// available to help the thread with threadID "master" at a split point. An -// obvious requirement is that "slave" must be idle. With more than two -// threads, this is not by itself sufficient: If "slave" is the master of -// some active split point, it is only available as a slave to the other -// threads which are busy searching the split point at the top of "slave"'s -// split point stack (the "helpful master concept" in YBWC terminology). +// exit() is called to cleanly terminate the threads when the program finishes -bool ThreadsManager::thread_is_available(int slave, int master) const { +void ThreadsManager::exit() { - assert(slave >= 0 && slave < activeThreads); - assert(master >= 0 && master < activeThreads); - assert(activeThreads > 1); + for (int i = 0; i <= MAX_THREADS; i++) + { + assert(threads[i].do_sleep); - if (threads[slave].state != THREAD_AVAILABLE || slave == master) - return false; + threads[i].do_exit = true; // Search must be already finished + threads[i].wake_up(); - // Make a local copy to be sure doesn't change under our feet - int localActiveSplitPoints = threads[slave].activeSplitPoints; + thread_join(threads[i].handle); // Wait for thread termination - // No active split points means that the thread is available as - // a slave for any other thread. - if (localActiveSplitPoints == 0 || activeThreads == 2) - return true; + lock_destroy(threads[i].sleepLock); + cond_destroy(threads[i].sleepCond); - // Apply the "helpful master" concept if possible. Use localActiveSplitPoints - // that is known to be > 0, instead of threads[slave].activeSplitPoints that - // could have been set to 0 by another thread leading to an out of bound access. - if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master]) - return true; + for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++) + lock_destroy(threads[i].splitPoints[j].lock); + } - return false; + lock_destroy(splitLock); + cond_destroy(sleepCond); } -// available_thread_exists() tries to find an idle thread which is available as -// a slave for the thread with threadID "master". +// available_slave_exists() tries to find an idle thread which is available as +// a slave for the thread with threadID 'master'. -bool ThreadsManager::available_thread_exists(int master) const { +bool ThreadsManager::available_slave_exists(int master) const { assert(master >= 0 && master < activeThreads); - assert(activeThreads > 1); for (int i = 0; i < activeThreads; i++) - if (thread_is_available(i, master)) + if (threads[i].is_available_to(master)) return true; return false; @@ -231,117 +289,183 @@ bool ThreadsManager::available_thread_exists(int master) const { // split() does the actual work of distributing the work at a node between -// several available threads. If it does not succeed in splitting the -// node (because no idle threads are available, or because we have no unused -// split point objects), the function immediately returns. If splitting is -// possible, a SplitPoint object is initialized with all the data that must be -// copied to the helper threads and we tell our helper threads that they have -// been assigned work. This will cause them to instantly leave their idle loops and -// call search().When all threads have returned from search() then split() returns. +// several available threads. If it does not succeed in splitting the node +// (because no idle threads are available, or because we have no unused split +// point objects), the function immediately returns. If splitting is possible, a +// SplitPoint object is initialized with all the data that must be copied to the +// helper threads and then helper threads are told that they have been assigned +// work. This will cause them to instantly leave their idle loops and call +// search(). When all threads have returned from search() then split() returns. template -void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta, - Value* bestValue, Depth depth, Move threatMove, - int moveCount, MovePicker* mp, bool pvNode) { - assert(pos.is_ok()); - assert(*bestValue >= -VALUE_INFINITE); - assert(*bestValue <= *alpha); - assert(*alpha < beta); +Value ThreadsManager::split(Position& pos, Stack* ss, Value alpha, Value beta, + Value bestValue, Depth depth, Move threatMove, + int moveCount, MovePicker* mp, int nodeType) { + assert(pos.pos_is_ok()); + assert(bestValue > -VALUE_INFINITE); + assert(bestValue <= alpha); + assert(alpha < beta); assert(beta <= VALUE_INFINITE); assert(depth > DEPTH_ZERO); assert(pos.thread() >= 0 && pos.thread() < activeThreads); assert(activeThreads > 1); - int i, master = pos.thread(); + int master = pos.thread(); Thread& masterThread = threads[master]; - lock_grab(&mpLock); + if (masterThread.splitPointsCnt >= MAX_SPLITPOINTS_PER_THREAD) + return bestValue; + + // Pick the next available split point from the split point stack + SplitPoint* sp = &masterThread.splitPoints[masterThread.splitPointsCnt]; + + sp->parent = masterThread.curSplitPoint; + sp->master = master; + sp->cutoff = false; + sp->slavesMask = 1ULL << master; + sp->depth = depth; + sp->threatMove = threatMove; + sp->alpha = alpha; + sp->beta = beta; + sp->nodeType = nodeType; + sp->bestValue = bestValue; + sp->mp = mp; + sp->moveCount = moveCount; + sp->pos = &pos; + sp->nodes = 0; + sp->ss = ss; + + assert(masterThread.is_searching); + + int slavesCnt = 0; + + // Try to allocate available threads and ask them to start searching setting + // is_searching flag. This must be done under lock protection to avoid concurrent + // allocation of the same slave by another master. + lock_grab(sp->lock); + lock_grab(splitLock); + + for (int i = 0; i < activeThreads && !Fake; i++) + if (threads[i].is_available_to(master)) + { + sp->slavesMask |= 1ULL << i; + threads[i].curSplitPoint = sp; + threads[i].is_searching = true; // Slave leaves idle_loop() - // If no other thread is available to help us, or if we have too many - // active split points, don't split. - if ( !available_thread_exists(master) - || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS) - { - lock_release(&mpLock); - return; - } + if (useSleepingThreads) + threads[i].wake_up(); - // Pick the next available split point object from the split point stack - SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++]; - - // Initialize the split point object - splitPoint.parent = masterThread.splitPoint; - splitPoint.master = master; - splitPoint.betaCutoff = false; - splitPoint.depth = depth; - splitPoint.threatMove = threatMove; - splitPoint.alpha = *alpha; - splitPoint.beta = beta; - splitPoint.pvNode = pvNode; - splitPoint.bestValue = *bestValue; - splitPoint.mp = mp; - splitPoint.moveCount = moveCount; - splitPoint.pos = &pos; - splitPoint.nodes = 0; - splitPoint.ss = ss; - for (i = 0; i < activeThreads; i++) - splitPoint.slaves[i] = 0; - - masterThread.splitPoint = &splitPoint; - - // If we are here it means we are not available - assert(masterThread.state != THREAD_AVAILABLE); - - int workersCnt = 1; // At least the master is included - - // Allocate available threads setting state to THREAD_BOOKED - for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++) - if (thread_is_available(i, master)) - { - threads[i].state = THREAD_BOOKED; - threads[i].splitPoint = &splitPoint; - splitPoint.slaves[i] = 1; - workersCnt++; + if (++slavesCnt + 1 >= maxThreadsPerSplitPoint) // Master is always included + break; } - assert(Fake || workersCnt > 1); + masterThread.curSplitPoint = sp; + masterThread.splitPointsCnt++; - // We can release the lock because slave threads are already booked and master is not available - lock_release(&mpLock); + lock_release(splitLock); + lock_release(sp->lock); - // Tell the threads that they have work to do. This will make them leave - // their idle loop. - for (i = 0; i < activeThreads; i++) - if (i == master || splitPoint.slaves[i]) - { - assert(i == master || threads[i].state == THREAD_BOOKED); + // Everything is set up. The master thread enters the idle loop, from which + // it will instantly launch a search, because its is_searching flag is set. + // We pass the split point as a parameter to the idle loop, which means that + // the thread will return from the idle loop when all slaves have finished + // their work at this split point. + if (slavesCnt || Fake) + masterThread.idle_loop(sp); - threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop() + // We have returned from the idle loop, which means that all threads are + // finished. Note that setting is_searching and decreasing activeSplitPoints is + // done under lock protection to avoid a race with Thread::is_available_to(). + lock_grab(sp->lock); // To protect sp->nodes + lock_grab(splitLock); - if (useSleepingThreads && i != master) - threads[i].wake_up(); - } + masterThread.is_searching = true; + masterThread.splitPointsCnt--; + masterThread.curSplitPoint = sp->parent; + pos.set_nodes_searched(pos.nodes_searched() + sp->nodes); - // Everything is set up. The master thread enters the idle loop, from - // which it will instantly launch a search, because its state is - // THREAD_WORKISWAITING. We send the split point as a second parameter to the - // idle loop, which means that the main thread will return from the idle - // loop when all threads have finished their work at this split point. - idle_loop(master, &splitPoint); + lock_release(splitLock); + lock_release(sp->lock); + + return sp->bestValue; +} + +// Explicit template instantiations +template Value ThreadsManager::split(Position&, Stack*, Value, Value, Value, Depth, Move, int, MovePicker*, int); +template Value ThreadsManager::split(Position&, Stack*, Value, Value, Value, Depth, Move, int, MovePicker*, int); - // We have returned from the idle loop, which means that all threads are - // finished. Update alpha and bestValue, and return. - lock_grab(&mpLock); - *alpha = splitPoint.alpha; - *bestValue = splitPoint.bestValue; - masterThread.activeSplitPoints--; - masterThread.splitPoint = splitPoint.parent; - pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes); +// ThreadsManager::set_timer() is used to set the timer to trigger after msec +// milliseconds. If msec is 0 then timer is stopped. - lock_release(&mpLock); +void ThreadsManager::set_timer(int msec) { + + Thread& timer = threads[MAX_THREADS]; + + lock_grab(timer.sleepLock); + timer.maxPly = msec; + cond_signal(timer.sleepCond); // Wake up and restart the timer + lock_release(timer.sleepLock); } -// Explicit template instantiations -template void ThreadsManager::split<0>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool); -template void ThreadsManager::split<1>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool); + +// ThreadsManager::start_thinking() is used by UI thread to wake up the main +// thread parked in main_loop() and starting a new search. If asyncMode is true +// then function returns immediately, otherwise caller is blocked waiting for +// the search to finish. + +void ThreadsManager::start_thinking(const Position& pos, const LimitsType& limits, + const std::set& searchMoves, bool async) { + Thread& main = threads[0]; + + lock_grab(main.sleepLock); + + // Wait main thread has finished before to launch a new search + while (!main.do_sleep) + cond_wait(sleepCond, main.sleepLock); + + // Copy input arguments to initialize the search + RootPosition.copy(pos, 0); + Limits = limits; + RootMoves.clear(); + + // Populate RootMoves with all the legal moves (default) or, if a searchMoves + // set is given, with the subset of legal moves to search. + for (MoveList ml(pos); !ml.end(); ++ml) + if (searchMoves.empty() || searchMoves.count(ml.move())) + RootMoves.push_back(RootMove(ml.move())); + + // Reset signals before to start the new search + Signals.stopOnPonderhit = Signals.firstRootMove = false; + Signals.stop = Signals.failedLowAtRoot = false; + + main.do_sleep = false; + cond_signal(main.sleepCond); // Wake up main thread and start searching + + if (!async) + while (!main.do_sleep) + cond_wait(sleepCond, main.sleepLock); + + lock_release(main.sleepLock); +} + + +// ThreadsManager::stop_thinking() is used by UI thread to raise a stop request +// and to wait for the main thread finishing the search. Needed to wait exiting +// and terminate the threads after a 'quit' command. + +void ThreadsManager::stop_thinking() { + + Thread& main = threads[0]; + + Search::Signals.stop = true; + + lock_grab(main.sleepLock); + + cond_signal(main.sleepCond); // In case is waiting for stop or ponderhit + + while (!main.do_sleep) + cond_wait(sleepCond, main.sleepLock); + + lock_release(main.sleepLock); +}