X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fthread.cpp;h=f2a2c821151aa0219d525be1779e83d86c9dd2d1;hp=30c921d1808ebd4716dee58bab6deeefe0e54279;hb=32d3a07c6710e84d78999cb69c6a866b0bfff482;hpb=fecefbb99cb0147f37d6895765a315f34c935786 diff --git a/src/thread.cpp b/src/thread.cpp index 30c921d1..f2a2c821 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,199 +17,275 @@ 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 is a wrapper to member function pointed by start_fn. - void* init_thread(void* threadID) { + long start_routine(Thread* th) { (th->*(th->start_fn))(); return 0; } - ThreadsMgr.idle_loop(*(int*)threadID, NULL); - return NULL; - } +} } -#else - DWORD WINAPI init_thread(LPVOID threadID) { +// Thread c'tor starts a newly-created thread of execution that will call +// the idle loop function pointed by start_fn going immediately to sleep. - ThreadsMgr.idle_loop(*(int*)threadID, NULL); - return 0; - } +Thread::Thread(Fn fn) { + + is_searching = do_exit = false; + maxPly = splitPointsCnt = 0; + curSplitPoint = NULL; + start_fn = fn; + threadID = Threads.size(); + + do_sleep = (fn != &Thread::main_loop); // Avoid a race with start_thinking() -#endif + lock_init(sleepLock); + cond_init(sleepCond); + for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++) + lock_init(splitPoints[j].lock); + + if (!thread_create(handle, start_routine, this)) + { + std::cerr << "Failed to create thread number " << threadID << std::endl; + ::exit(EXIT_FAILURE); + } } -// 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 d'tor waits for thread termination before to return. -void ThreadsManager::read_uci_options() { +Thread::~Thread() { - 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(); -} + assert(do_sleep); + + do_exit = true; // Search must be already finished + wake_up(); -// init_threads() is called during startup. Initializes locks and condition -// variables and launches all threads sending them immediately to sleep. + thread_join(handle); // Wait for thread termination -void ThreadsManager::init_threads() { + lock_destroy(sleepLock); + cond_destroy(sleepCond); - int i, arg[MAX_THREADS]; - bool ok; + for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++) + lock_destroy(splitPoints[j].lock); +} - // 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; +// Thread::timer_loop() is where the timer thread waits maxPly milliseconds and +// then calls check_time(). If maxPly is 0 thread sleeps until is woken up. +extern void check_time(); - lock_init(&mpLock); +void Thread::timer_loop() { - for (i = 0; i < MAX_THREADS; i++) + while (!do_exit) { - // Initialize thread and split point locks - lock_init(&threads[i].sleepLock); - cond_init(&threads[i].sleepCond); + lock_grab(sleepLock); + timed_wait(sleepCond, sleepLock, maxPly ? maxPly : INT_MAX); + lock_release(sleepLock); + check_time(); + } +} - for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) - lock_init(&(threads[i].splitPoints[j].lock)); - // All threads but first should be set to THREAD_INITIALIZING - threads[i].state = (i == 0 ? THREAD_SEARCHING : THREAD_INITIALIZING); +// 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. - // Not in Threads c'tor to avoid global initialization order issues - threads[i].pawnTable.init(); - threads[i].materialTable.init(); - } +void Thread::main_loop() { - // Create and startup the threads - for (i = 1; i < MAX_THREADS; i++) + while (true) { - arg[i] = i; - -#if !defined(_MSC_VER) - pthread_t pthread[1]; - ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0); - pthread_detach(pthread[0]); -#else - ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL); -#endif - if (!ok) + lock_grab(sleepLock); + + do_sleep = true; // Always return to sleep after a search + is_searching = false; + + while (do_sleep && !do_exit) { - std::cout << "Failed to create thread number " << i << std::endl; - exit(EXIT_FAILURE); + cond_signal(Threads.sleepCond); // Wake up UI thread if needed + cond_wait(sleepCond, sleepLock); } - // Wait until the thread has finished launching and is gone to sleep - while (threads[i].state == THREAD_INITIALIZING) {} + lock_release(sleepLock); + + if (do_exit) + return; + + is_searching = true; + + Search::think(); } } -// exit_threads() is called when the program exits. It makes all the -// helper threads exit cleanly. +// Thread::wake_up() wakes up the thread, normally at the beginning of the search +// or, if "sleeping threads" is used at split time. -void ThreadsManager::exit_threads() { +void Thread::wake_up() { - // Force the woken up threads to exit idle_loop() and hence terminate - allThreadsShouldExit = true; + lock_grab(sleepLock); + cond_signal(sleepCond); + lock_release(sleepLock); +} - 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) {} - } - // Now we can safely destroy the locks and wait conditions - lock_destroy(&threads[i].sleepLock); - cond_destroy(&threads[i].sleepCond); +// 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. - for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++) - lock_destroy(&(threads[i].splitPoints[j].lock)); - } +void Thread::wait_for_stop_or_ponderhit() { + + Signals.stopOnPonderhit = true; - lock_destroy(&mpLock); + lock_grab(sleepLock); + + while (!Signals.stop) + cond_wait(sleepCond, sleepLock); + + lock_release(sleepLock); +} + + +// Thread::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; } -// 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. +// Thread::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 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). -bool ThreadsManager::cutoff_at_splitpoint(int threadID) const { +bool Thread::is_available_to(int master) const { - assert(threadID >= 0 && threadID < activeThreads); + if (is_searching) + return false; - SplitPoint* sp = threads[threadID].splitPoint; + // 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; - for ( ; sp && !sp->betaCutoff; sp = sp->parent) {} - return sp != NULL; + // 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)); } -// 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). +// init() is called at startup. Initializes lock and condition variable and +// launches requested threads sending them immediately to sleep. We cannot use +// a c'tor becuase Threads is a static object and we need a fully initialized +// engine at this point due to allocation of endgames in Thread c'tor. -bool ThreadsManager::thread_is_available(int slave, int master) const { +void ThreadsManager::init() { - assert(slave >= 0 && slave < activeThreads); - assert(master >= 0 && master < activeThreads); - assert(activeThreads > 1); + cond_init(sleepCond); + lock_init(splitLock); + timer = new Thread(&Thread::timer_loop); + threads.push_back(new Thread(&Thread::main_loop)); + read_uci_options(); +} - if (threads[slave].state != THREAD_AVAILABLE || slave == master) - return false; - // Make a local copy to be sure doesn't change under our feet - int localActiveSplitPoints = threads[slave].activeSplitPoints; +// d'tor cleanly terminates the threads when the program exits. - // No active split points means that the thread is available as - // a slave for any other thread. - if (localActiveSplitPoints == 0 || activeThreads == 2) - return true; +ThreadsManager::~ThreadsManager() { - // 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 i = 0; i < size(); i++) + delete threads[i]; - return false; + delete timer; + 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". +// read_uci_options() updates internal threads parameters from the corresponding +// UCI options and creates/destroys threads to match the requested number. Thread +// objects are dynamically allocated to avoid creating in advance all possible +// threads, with included pawns and material tables, if only few are used. + +void ThreadsManager::read_uci_options() { + + maxThreadsPerSplitPoint = Options["Max Threads per Split Point"]; + minimumSplitDepth = Options["Min Split Depth"] * ONE_PLY; + useSleepingThreads = Options["Use Sleeping Threads"]; + int requested = Options["Threads"]; + + assert(requested > 0); + + while (size() < requested) + threads.push_back(new Thread(&Thread::idle_loop)); + + while (size() > requested) + { + delete threads.back(); + threads.pop_back(); + } +} + -bool ThreadsManager::available_thread_exists(int master) const { +// wake_up() is called before a new search to start the threads that are waiting +// on the sleep condition and to reset maxPly. When useSleepingThreads is set +// threads will be woken up at split time. - assert(master >= 0 && master < activeThreads); - assert(activeThreads > 1); +void ThreadsManager::wake_up() const { - for (int i = 0; i < activeThreads; i++) - if (thread_is_available(i, master)) + for (int i = 0; i < size(); i++) + { + threads[i]->do_sleep = false; + threads[i]->maxPly = 0; + + if (!useSleepingThreads) + threads[i]->wake_up(); + } +} + + +// sleep() is called after the search finishes to ask all the threads but the +// main one to go waiting on a sleep condition. + +void ThreadsManager::sleep() const { + + for (int i = 1; i < size(); i++) // Main thread will go to sleep by itself + threads[i]->do_sleep = true; // to avoid a race with start_thinking() +} + + +// available_slave_exists() tries to find an idle thread which is available as +// a slave for the thread with threadID 'master'. + +bool ThreadsManager::available_slave_exists(int master) const { + + assert(master >= 0 && master < size()); + + for (int i = 0; i < size(); i++) + if (threads[i]->is_available_to(master)) return true; return false; @@ -217,117 +293,180 @@ 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, Move* bestMove, 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(); - Thread& masterThread = threads[master]; + int master = pos.thread(); + Thread& masterThread = *threads[master]; + + 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->bestMove = *bestMove; + 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); + + masterThread.curSplitPoint = sp; + 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 < size() && !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 (useSleepingThreads) + threads[i]->wake_up(); + + if (++slavesCnt + 1 >= maxThreadsPerSplitPoint) // Master is always included + break; + } - lock_grab(&mpLock); + lock_release(splitLock); + lock_release(sp->lock); - // 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) + // 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) { - lock_release(&mpLock); - return; + masterThread.idle_loop(sp); + + // In helpful master concept a master can help only a sub-tree of its split + // point, and because here is all finished is not possible master is booked. + assert(!masterThread.is_searching); } - // 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++; - } + // We have returned from the idle loop, which means that all threads are + // finished. Note that setting is_searching and decreasing splitPointsCnt 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); - assert(Fake || workersCnt > 1); + masterThread.is_searching = true; + masterThread.splitPointsCnt--; + masterThread.curSplitPoint = sp->parent; + pos.set_nodes_searched(pos.nodes_searched() + sp->nodes); + *bestMove = sp->bestMove; - // 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); + return sp->bestValue; +} - threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop() +// Explicit template instantiations +template Value ThreadsManager::split(Position&, Stack*, Value, Value, Value, Move*, Depth, Move, int, MovePicker*, int); +template Value ThreadsManager::split(Position&, Stack*, Value, Value, Value, Move*, Depth, Move, int, MovePicker*, int); - if (useSleepingThreads && i != master) - threads[i].wake_up(); - } - // 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); +// ThreadsManager::set_timer() is used to set the timer to trigger after msec +// milliseconds. If msec is 0 then timer is stopped. - // We have returned from the idle loop, which means that all threads are - // finished. Update alpha and bestValue, and return. - lock_grab(&mpLock); +void ThreadsManager::set_timer(int msec) { + + lock_grab(timer->sleepLock); + timer->maxPly = msec; + cond_signal(timer->sleepCond); // Wake up and restart the timer + lock_release(timer->sleepLock); +} + + +// ThreadsManager::start_thinking() is used by UI thread to wake up the main +// thread parked in main_loop() and starting a new search. If async 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.front(); + + lock_grab(main.sleepLock); + + while (!main.do_sleep) + cond_wait(sleepCond, main.sleepLock); // Wait main thread has finished + + Signals.stopOnPonderhit = Signals.firstRootMove = false; + Signals.stop = Signals.failedLowAtRoot = false; + + RootPosition.copy(pos, 0); + Limits = limits; + RootMoves.clear(); - *alpha = splitPoint.alpha; - *bestValue = splitPoint.bestValue; - masterThread.activeSplitPoints--; - masterThread.splitPoint = splitPoint.parent; - pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes); + for (MoveList ml(pos); !ml.end(); ++ml) + if (searchMoves.empty() || searchMoves.count(ml.move())) + RootMoves.push_back(RootMove(ml.move())); - lock_release(&mpLock); + 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); } -// 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::stop_thinking() is used by UI thread to raise a stop request +// and to wait for the main thread finishing the search. We cannot return before +// main has finished to avoid a crash in case of a 'quit' command. + +void ThreadsManager::stop_thinking() { + + Thread& main = *threads.front(); + + 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); +}