]> git.sesse.net Git - stockfish/blob - src/thread.cpp
031ee848e6343ea44c33835198a9411320b10a32
[stockfish] / src / thread.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4   Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad
5
6   Stockfish is free software: you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation, either version 3 of the License, or
9   (at your option) any later version.
10
11   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <cassert>
21 #include <iostream>
22
23 #include "movegen.h"
24 #include "search.h"
25 #include "thread.h"
26 #include "ucioption.h"
27
28 using namespace Search;
29
30 ThreadsManager Threads; // Global object
31
32 namespace { extern "C" {
33
34  // start_routine() is the C function which is called when a new thread
35  // is launched. It simply calls idle_loop() of the supplied thread. The first
36  // and last thread are special. First one is the main search thread while the
37  // last one mimics a timer, they run in main_loop() and timer_loop().
38
39   long start_routine(Thread* th) {
40
41     if (th->threadID == 0)
42         th->main_loop();
43
44     else if (th->threadID == MAX_THREADS)
45         th->timer_loop();
46
47     else
48         th->idle_loop(NULL);
49
50     return 0;
51   }
52
53 } }
54
55
56 // Thread c'tor creates and launches the OS thread, that will go immediately to
57 // sleep.
58
59 Thread::Thread(int id) {
60
61   is_searching = do_exit = false;
62   maxPly = splitPointsCnt = 0;
63   curSplitPoint = NULL;
64   threadID = id;
65   do_sleep = (id != 0); // Avoid a race with start_thinking()
66
67   lock_init(sleepLock);
68   cond_init(sleepCond);
69
70   for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++)
71       lock_init(splitPoints[j].lock);
72
73   if (!thread_create(handle, start_routine, this))
74   {
75       std::cerr << "Failed to create thread number " << id << std::endl;
76       ::exit(EXIT_FAILURE);
77   }
78 }
79
80
81 // Thread d'tor will wait for thread termination before to return.
82
83 Thread::~Thread() {
84
85   assert(do_sleep);
86
87   do_exit = true; // Search must be already finished
88   wake_up();
89
90   thread_join(handle); // Wait for thread termination
91
92   lock_destroy(sleepLock);
93   cond_destroy(sleepCond);
94
95   for (int j = 0; j < MAX_SPLITPOINTS_PER_THREAD; j++)
96       lock_destroy(splitPoints[j].lock);
97 }
98
99
100 // Thread::timer_loop() is where the timer thread waits maxPly milliseconds and
101 // then calls do_timer_event(). If maxPly is 0 thread sleeps until is woken up.
102 extern void check_time();
103
104 void Thread::timer_loop() {
105
106   while (!do_exit)
107   {
108       lock_grab(sleepLock);
109       timed_wait(sleepCond, sleepLock, maxPly ? maxPly : INT_MAX);
110       lock_release(sleepLock);
111       check_time();
112   }
113 }
114
115
116 // Thread::main_loop() is where the main thread is parked waiting to be started
117 // when there is a new search. Main thread will launch all the slave threads.
118
119 void Thread::main_loop() {
120
121   while (true)
122   {
123       lock_grab(sleepLock);
124
125       do_sleep = true; // Always return to sleep after a search
126       is_searching = false;
127
128       while (do_sleep && !do_exit)
129       {
130           cond_signal(Threads.sleepCond); // Wake up UI thread if needed
131           cond_wait(sleepCond, sleepLock);
132       }
133
134       lock_release(sleepLock);
135
136       if (do_exit)
137           return;
138
139       is_searching = true;
140
141       Search::think();
142   }
143 }
144
145
146 // Thread::wake_up() wakes up the thread, normally at the beginning of the search
147 // or, if "sleeping threads" is used, when there is some work to do.
148
149 void Thread::wake_up() {
150
151   lock_grab(sleepLock);
152   cond_signal(sleepCond);
153   lock_release(sleepLock);
154 }
155
156
157 // Thread::wait_for_stop_or_ponderhit() is called when the maximum depth is
158 // reached while the program is pondering. The point is to work around a wrinkle
159 // in the UCI protocol: When pondering, the engine is not allowed to give a
160 // "bestmove" before the GUI sends it a "stop" or "ponderhit" command. We simply
161 // wait here until one of these commands (that raise StopRequest) is sent and
162 // then return, after which the bestmove and pondermove will be printed.
163
164 void Thread::wait_for_stop_or_ponderhit() {
165
166   Signals.stopOnPonderhit = true;
167
168   lock_grab(sleepLock);
169
170   while (!Signals.stop)
171       cond_wait(sleepCond, sleepLock);
172
173   lock_release(sleepLock);
174 }
175
176
177 // cutoff_occurred() checks whether a beta cutoff has occurred in the current
178 // active split point, or in some ancestor of the split point.
179
180 bool Thread::cutoff_occurred() const {
181
182   for (SplitPoint* sp = curSplitPoint; sp; sp = sp->parent)
183       if (sp->cutoff)
184           return true;
185
186   return false;
187 }
188
189
190 // is_available_to() checks whether the thread is available to help the thread with
191 // threadID "master" at a split point. An obvious requirement is that thread must be
192 // idle. With more than two threads, this is not by itself sufficient: If the thread
193 // is the master of some active split point, it is only available as a slave to the
194 // threads which are busy searching the split point at the top of "slave"'s split
195 // point stack (the "helpful master concept" in YBWC terminology).
196
197 bool Thread::is_available_to(int master) const {
198
199   if (is_searching)
200       return false;
201
202   // Make a local copy to be sure doesn't become zero under our feet while
203   // testing next condition and so leading to an out of bound access.
204   int spCnt = splitPointsCnt;
205
206   // No active split points means that the thread is available as a slave for any
207   // other thread otherwise apply the "helpful master" concept if possible.
208   return !spCnt || (splitPoints[spCnt - 1].slavesMask & (1ULL << master));
209 }
210
211
212 // read_uci_options() updates internal threads parameters from the corresponding
213 // UCI options and creates/destroys threads to match the requested number. Thread
214 // objects are dynamically allocated to avoid creating in advance all possible
215 // threads, with included pawns and material tables, if only few are used.
216
217 void ThreadsManager::read_uci_options() {
218
219   maxThreadsPerSplitPoint = Options["Max Threads per Split Point"];
220   minimumSplitDepth       = Options["Min Split Depth"] * ONE_PLY;
221   useSleepingThreads      = Options["Use Sleeping Threads"];
222   int requested           = Options["Threads"];
223
224   while (size() < requested)
225       threads.push_back(new Thread(size()));
226
227   while (size() > requested)
228   {
229       delete threads.back();
230       threads.pop_back();
231   }
232 }
233
234
235 // wake_up() is called before a new search to start the threads that are waiting
236 // on the sleep condition. If useSleepingThreads is set threads will be woken up
237 // at split time.
238
239 void ThreadsManager::wake_up() {
240
241   for (int i = 0; i < size(); i++)
242   {
243       threads[i]->do_sleep = false;
244
245       if (!useSleepingThreads)
246           threads[i]->wake_up();
247   }
248 }
249
250
251 // sleep() is called after the search to ask threads to wait on sleep condition
252
253 void ThreadsManager::sleep() {
254
255   for (int i = 0; i < size(); i++)
256       threads[i]->do_sleep = true;
257 }
258
259
260 // init() is called during startup. Initializes locks and condition variables
261 // and launches all threads sending them immediately to sleep.
262
263 void ThreadsManager::init() {
264
265     cond_init(sleepCond);
266     lock_init(splitLock);
267     timer = new Thread(MAX_THREADS);
268     read_uci_options(); // Creates at least the main thread
269 }
270
271
272 // exit() is called to cleanly terminate the threads before the program finishes
273
274 void ThreadsManager::exit() {
275
276   for (int i = 0; i < size(); i++)
277       delete threads[i];
278
279   delete timer;
280   lock_destroy(splitLock);
281   cond_destroy(sleepCond);
282 }
283
284
285 // available_slave_exists() tries to find an idle thread which is available as
286 // a slave for the thread with threadID 'master'.
287
288 bool ThreadsManager::available_slave_exists(int master) const {
289
290   assert(master >= 0 && master < size());
291
292   for (int i = 0; i < size(); i++)
293       if (threads[i]->is_available_to(master))
294           return true;
295
296   return false;
297 }
298
299
300 // split() does the actual work of distributing the work at a node between
301 // several available threads. If it does not succeed in splitting the node
302 // (because no idle threads are available, or because we have no unused split
303 // point objects), the function immediately returns. If splitting is possible, a
304 // SplitPoint object is initialized with all the data that must be copied to the
305 // helper threads and then helper threads are told that they have been assigned
306 // work. This will cause them to instantly leave their idle loops and call
307 // search(). When all threads have returned from search() then split() returns.
308
309 template <bool Fake>
310 Value ThreadsManager::split(Position& pos, Stack* ss, Value alpha, Value beta,
311                             Value bestValue, Move* bestMove, Depth depth,
312                             Move threatMove, int moveCount, MovePicker* mp, int nodeType) {
313   assert(pos.pos_is_ok());
314   assert(bestValue > -VALUE_INFINITE);
315   assert(bestValue <= alpha);
316   assert(alpha < beta);
317   assert(beta <= VALUE_INFINITE);
318   assert(depth > DEPTH_ZERO);
319
320   int master = pos.thread();
321   Thread& masterThread = *threads[master];
322
323   if (masterThread.splitPointsCnt >= MAX_SPLITPOINTS_PER_THREAD)
324       return bestValue;
325
326   // Pick the next available split point from the split point stack
327   SplitPoint* sp = &masterThread.splitPoints[masterThread.splitPointsCnt++];
328
329   sp->parent = masterThread.curSplitPoint;
330   sp->master = master;
331   sp->cutoff = false;
332   sp->slavesMask = 1ULL << master;
333   sp->depth = depth;
334   sp->bestMove = *bestMove;
335   sp->threatMove = threatMove;
336   sp->alpha = alpha;
337   sp->beta = beta;
338   sp->nodeType = nodeType;
339   sp->bestValue = bestValue;
340   sp->mp = mp;
341   sp->moveCount = moveCount;
342   sp->pos = &pos;
343   sp->nodes = 0;
344   sp->ss = ss;
345
346   assert(masterThread.is_searching);
347
348   masterThread.curSplitPoint = sp;
349   int slavesCnt = 0;
350
351   // Try to allocate available threads and ask them to start searching setting
352   // is_searching flag. This must be done under lock protection to avoid concurrent
353   // allocation of the same slave by another master.
354   lock_grab(sp->lock);
355   lock_grab(splitLock);
356
357   for (int i = 0; i < size() && !Fake; ++i)
358       if (threads[i]->is_available_to(master))
359       {
360           sp->slavesMask |= 1ULL << i;
361           threads[i]->curSplitPoint = sp;
362           threads[i]->is_searching = true; // Slave leaves idle_loop()
363
364           if (useSleepingThreads)
365               threads[i]->wake_up();
366
367           if (++slavesCnt + 1 >= maxThreadsPerSplitPoint) // Master is always included
368               break;
369       }
370
371   lock_release(splitLock);
372   lock_release(sp->lock);
373
374   // Everything is set up. The master thread enters the idle loop, from which
375   // it will instantly launch a search, because its is_searching flag is set.
376   // We pass the split point as a parameter to the idle loop, which means that
377   // the thread will return from the idle loop when all slaves have finished
378   // their work at this split point.
379   if (slavesCnt || Fake)
380   {
381       masterThread.idle_loop(sp);
382
383       // In helpful master concept a master can help only a sub-tree of its split
384       // point, and because here is all finished is not possible master is booked.
385       assert(!masterThread.is_searching);
386   }
387
388   // We have returned from the idle loop, which means that all threads are
389   // finished. Note that setting is_searching and decreasing splitPointsCnt is
390   // done under lock protection to avoid a race with Thread::is_available_to().
391   lock_grab(sp->lock); // To protect sp->nodes
392   lock_grab(splitLock);
393
394   masterThread.is_searching = true;
395   masterThread.splitPointsCnt--;
396   masterThread.curSplitPoint = sp->parent;
397   pos.set_nodes_searched(pos.nodes_searched() + sp->nodes);
398   *bestMove = sp->bestMove;
399
400   lock_release(splitLock);
401   lock_release(sp->lock);
402
403   return sp->bestValue;
404 }
405
406 // Explicit template instantiations
407 template Value ThreadsManager::split<false>(Position&, Stack*, Value, Value, Value, Move*, Depth, Move, int, MovePicker*, int);
408 template Value ThreadsManager::split<true>(Position&, Stack*, Value, Value, Value, Move*, Depth, Move, int, MovePicker*, int);
409
410
411 // ThreadsManager::set_timer() is used to set the timer to trigger after msec
412 // milliseconds. If msec is 0 then timer is stopped.
413
414 void ThreadsManager::set_timer(int msec) {
415
416   lock_grab(timer->sleepLock);
417   timer->maxPly = msec;
418   cond_signal(timer->sleepCond); // Wake up and restart the timer
419   lock_release(timer->sleepLock);
420 }
421
422
423 // ThreadsManager::start_thinking() is used by UI thread to wake up the main
424 // thread parked in main_loop() and starting a new search. If asyncMode is true
425 // then function returns immediately, otherwise caller is blocked waiting for
426 // the search to finish.
427
428 void ThreadsManager::start_thinking(const Position& pos, const LimitsType& limits,
429                                     const std::set<Move>& searchMoves, bool async) {
430   Thread& main = *threads.front();
431
432   lock_grab(main.sleepLock);
433
434   // Wait main thread has finished before to launch a new search
435   while (!main.do_sleep)
436       cond_wait(sleepCond, main.sleepLock);
437
438   // Copy input arguments to initialize the search
439   RootPosition.copy(pos, 0);
440   Limits = limits;
441   RootMoves.clear();
442
443   // Populate RootMoves with all the legal moves (default) or, if a searchMoves
444   // set is given, with the subset of legal moves to search.
445   for (MoveList<MV_LEGAL> ml(pos); !ml.end(); ++ml)
446       if (searchMoves.empty() || searchMoves.count(ml.move()))
447           RootMoves.push_back(RootMove(ml.move()));
448
449   // Reset signals before to start the new search
450   Signals.stopOnPonderhit = Signals.firstRootMove = false;
451   Signals.stop = Signals.failedLowAtRoot = false;
452
453   main.do_sleep = false;
454   cond_signal(main.sleepCond); // Wake up main thread and start searching
455
456   if (!async)
457       while (!main.do_sleep)
458           cond_wait(sleepCond, main.sleepLock);
459
460   lock_release(main.sleepLock);
461 }
462
463
464 // ThreadsManager::stop_thinking() is used by UI thread to raise a stop request
465 // and to wait for the main thread finishing the search. Needed to wait exiting
466 // and terminate the threads after a 'quit' command.
467
468 void ThreadsManager::stop_thinking() {
469
470   Thread& main = *threads.front();
471
472   Search::Signals.stop = true;
473
474   lock_grab(main.sleepLock);
475
476   cond_signal(main.sleepCond); // In case is waiting for stop or ponderhit
477
478   while (!main.do_sleep)
479       cond_wait(sleepCond, main.sleepLock);
480
481   lock_release(main.sleepLock);
482 }