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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
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.
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.
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/>.
23 #include "ucioption.h"
25 ThreadsManager ThreadsMgr; // Global object definition
29 // init_thread() is the function which is called when a new thread is
30 // launched. It simply calls the idle_loop() function with the supplied
31 // threadID. There are two versions of this function; one for POSIX
32 // threads and one for Windows threads.
34 #if !defined(_MSC_VER)
36 void* init_thread(void* threadID) {
38 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
44 DWORD WINAPI init_thread(LPVOID threadID) {
46 ThreadsMgr.idle_loop(*(int*)threadID, NULL);
55 // read_uci_options() updates number of active threads and other internal
56 // parameters according to the UCI options values. It is called before
57 // to start a new search.
59 void ThreadsManager::read_uci_options() {
61 maxThreadsPerSplitPoint = Options["Maximum Number of Threads per Split Point"].value<int>();
62 minimumSplitDepth = Options["Minimum Split Depth"].value<int>() * ONE_PLY;
63 useSleepingThreads = Options["Use Sleeping Threads"].value<bool>();
64 activeThreads = Options["Threads"].value<int>();
68 // init_threads() is called during startup. Initializes locks and condition
69 // variables and launches all threads sending them immediately to sleep.
71 void ThreadsManager::init_threads() {
75 // This flag is needed to properly end the threads when program exits
76 allThreadsShouldExit = false;
78 // Threads will sent to sleep as soon as created, only main thread is kept alive
80 threads[0].state = THREAD_SEARCHING;
82 // Allocate pawn and material hash tables for main thread
87 // Initialize thread and split point locks
88 for (int i = 0; i < MAX_THREADS; i++)
90 lock_init(&threads[i].sleepLock);
91 cond_init(&threads[i].sleepCond);
93 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
94 lock_init(&(threads[i].splitPoints[j].lock));
97 // Create and startup all the threads but the main that is already running
98 for (int i = 1; i < MAX_THREADS; i++)
100 threads[i].state = THREAD_INITIALIZING;
103 #if !defined(_MSC_VER)
104 pthread_t pthread[1];
105 bool ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
106 pthread_detach(pthread[0]);
108 bool ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
112 std::cout << "Failed to create thread number " << i << std::endl;
116 // Wait until the thread has finished launching and is gone to sleep
117 while (threads[i].state == THREAD_INITIALIZING) {}
122 // exit_threads() is called when the program exits. It makes all the
123 // helper threads exit cleanly.
125 void ThreadsManager::exit_threads() {
127 // Force the woken up threads to exit idle_loop() and hence terminate
128 allThreadsShouldExit = true;
130 for (int i = 0; i < MAX_THREADS; i++)
132 // Wake up all the threads and waits for termination
135 threads[i].wake_up();
136 while (threads[i].state != THREAD_TERMINATED) {}
139 // Now we can safely destroy the locks and wait conditions
140 lock_destroy(&threads[i].sleepLock);
141 cond_destroy(&threads[i].sleepCond);
143 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
144 lock_destroy(&(threads[i].splitPoints[j].lock));
147 lock_destroy(&mpLock);
151 // init_hash_tables() dynamically allocates pawn and material hash tables
152 // according to the number of active threads. This avoids preallocating
153 // memory for all possible threads if only few are used as, for instance,
154 // on mobile devices where memory is scarce and allocating for MAX_THREADS
155 // threads could even result in a crash.
157 void ThreadsManager::init_hash_tables() {
159 for (int i = 0; i < activeThreads; i++)
161 threads[i].pawnTable.init();
162 threads[i].materialTable.init();
167 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
168 // the thread's currently active split point, or in some ancestor of
169 // the current split point.
171 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
173 assert(threadID >= 0 && threadID < activeThreads);
175 SplitPoint* sp = threads[threadID].splitPoint;
177 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
182 // thread_is_available() checks whether the thread with threadID "slave" is
183 // available to help the thread with threadID "master" at a split point. An
184 // obvious requirement is that "slave" must be idle. With more than two
185 // threads, this is not by itself sufficient: If "slave" is the master of
186 // some active split point, it is only available as a slave to the other
187 // threads which are busy searching the split point at the top of "slave"'s
188 // split point stack (the "helpful master concept" in YBWC terminology).
190 bool ThreadsManager::thread_is_available(int slave, int master) const {
192 assert(slave >= 0 && slave < activeThreads);
193 assert(master >= 0 && master < activeThreads);
194 assert(activeThreads > 1);
196 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
199 // Make a local copy to be sure doesn't change under our feet
200 int localActiveSplitPoints = threads[slave].activeSplitPoints;
202 // No active split points means that the thread is available as
203 // a slave for any other thread.
204 if (localActiveSplitPoints == 0 || activeThreads == 2)
207 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
208 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
209 // could have been set to 0 by another thread leading to an out of bound access.
210 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
217 // available_thread_exists() tries to find an idle thread which is available as
218 // a slave for the thread with threadID "master".
220 bool ThreadsManager::available_thread_exists(int master) const {
222 assert(master >= 0 && master < activeThreads);
223 assert(activeThreads > 1);
225 for (int i = 0; i < activeThreads; i++)
226 if (thread_is_available(i, master))
233 // split() does the actual work of distributing the work at a node between
234 // several available threads. If it does not succeed in splitting the
235 // node (because no idle threads are available, or because we have no unused
236 // split point objects), the function immediately returns. If splitting is
237 // possible, a SplitPoint object is initialized with all the data that must be
238 // copied to the helper threads and we tell our helper threads that they have
239 // been assigned work. This will cause them to instantly leave their idle loops and
240 // call search().When all threads have returned from search() then split() returns.
243 void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta,
244 Value* bestValue, Depth depth, Move threatMove,
245 int moveCount, MovePicker* mp, bool pvNode) {
247 assert(*bestValue >= -VALUE_INFINITE);
248 assert(*bestValue <= *alpha);
249 assert(*alpha < beta);
250 assert(beta <= VALUE_INFINITE);
251 assert(depth > DEPTH_ZERO);
252 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
253 assert(activeThreads > 1);
255 int i, master = pos.thread();
256 Thread& masterThread = threads[master];
260 // If no other thread is available to help us, or if we have too many
261 // active split points, don't split.
262 if ( !available_thread_exists(master)
263 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
265 lock_release(&mpLock);
269 // Pick the next available split point object from the split point stack
270 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
272 // Initialize the split point object
273 splitPoint.parent = masterThread.splitPoint;
274 splitPoint.master = master;
275 splitPoint.betaCutoff = false;
276 splitPoint.depth = depth;
277 splitPoint.threatMove = threatMove;
278 splitPoint.alpha = *alpha;
279 splitPoint.beta = beta;
280 splitPoint.pvNode = pvNode;
281 splitPoint.bestValue = *bestValue;
283 splitPoint.moveCount = moveCount;
284 splitPoint.pos = &pos;
285 splitPoint.nodes = 0;
287 for (i = 0; i < activeThreads; i++)
288 splitPoint.slaves[i] = 0;
290 masterThread.splitPoint = &splitPoint;
292 // If we are here it means we are not available
293 assert(masterThread.state != THREAD_AVAILABLE);
295 int workersCnt = 1; // At least the master is included
297 // Allocate available threads setting state to THREAD_BOOKED
298 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
299 if (thread_is_available(i, master))
301 threads[i].state = THREAD_BOOKED;
302 threads[i].splitPoint = &splitPoint;
303 splitPoint.slaves[i] = 1;
307 assert(Fake || workersCnt > 1);
309 // We can release the lock because slave threads are already booked and master is not available
310 lock_release(&mpLock);
312 // Tell the threads that they have work to do. This will make them leave
314 for (i = 0; i < activeThreads; i++)
315 if (i == master || splitPoint.slaves[i])
317 assert(i == master || threads[i].state == THREAD_BOOKED);
319 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
321 if (useSleepingThreads && i != master)
322 threads[i].wake_up();
325 // Everything is set up. The master thread enters the idle loop, from
326 // which it will instantly launch a search, because its state is
327 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
328 // idle loop, which means that the main thread will return from the idle
329 // loop when all threads have finished their work at this split point.
330 idle_loop(master, &splitPoint);
332 // We have returned from the idle loop, which means that all threads are
333 // finished. Update alpha and bestValue, and return.
336 *alpha = splitPoint.alpha;
337 *bestValue = splitPoint.bestValue;
338 masterThread.activeSplitPoints--;
339 masterThread.splitPoint = splitPoint.parent;
340 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
342 lock_release(&mpLock);
345 // Explicit template instantiations
346 template void ThreadsManager::split<0>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool);
347 template void ThreadsManager::split<1>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool);