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>();
67 // init_threads() is called during startup. Initializes locks and condition
68 // variables and launches all threads sending them immediately to sleep.
70 void ThreadsManager::init_threads() {
72 int i, arg[MAX_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
83 for (i = 0; i < MAX_THREADS; i++)
85 // Initialize thread and split point locks
86 lock_init(&threads[i].sleepLock);
87 cond_init(&threads[i].sleepCond);
89 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
90 lock_init(&(threads[i].splitPoints[j].lock));
92 // All threads but first should be set to THREAD_INITIALIZING
93 threads[i].state = (i == 0 ? THREAD_SEARCHING : THREAD_INITIALIZING);
95 // Not in Threads c'tor to avoid global initialization order issues
96 threads[i].pawnTable.init();
97 threads[i].materialTable.init();
100 // Create and startup the threads
101 for (i = 1; i < MAX_THREADS; i++)
105 #if !defined(_MSC_VER)
106 pthread_t pthread[1];
107 ok = (pthread_create(pthread, NULL, init_thread, (void*)(&arg[i])) == 0);
108 pthread_detach(pthread[0]);
110 ok = (CreateThread(NULL, 0, init_thread, (LPVOID)(&arg[i]), 0, NULL) != NULL);
114 std::cout << "Failed to create thread number " << i << std::endl;
118 // Wait until the thread has finished launching and is gone to sleep
119 while (threads[i].state == THREAD_INITIALIZING) {}
124 // exit_threads() is called when the program exits. It makes all the
125 // helper threads exit cleanly.
127 void ThreadsManager::exit_threads() {
129 // Force the woken up threads to exit idle_loop() and hence terminate
130 allThreadsShouldExit = true;
132 for (int i = 0; i < MAX_THREADS; i++)
134 // Wake up all the threads and waits for termination
137 threads[i].wake_up();
138 while (threads[i].state != THREAD_TERMINATED) {}
141 // Now we can safely destroy the locks and wait conditions
142 lock_destroy(&threads[i].sleepLock);
143 cond_destroy(&threads[i].sleepCond);
145 for (int j = 0; j < MAX_ACTIVE_SPLIT_POINTS; j++)
146 lock_destroy(&(threads[i].splitPoints[j].lock));
149 lock_destroy(&mpLock);
153 // cutoff_at_splitpoint() checks whether a beta cutoff has occurred in
154 // the thread's currently active split point, or in some ancestor of
155 // the current split point.
157 bool ThreadsManager::cutoff_at_splitpoint(int threadID) const {
159 assert(threadID >= 0 && threadID < activeThreads);
161 SplitPoint* sp = threads[threadID].splitPoint;
163 for ( ; sp && !sp->betaCutoff; sp = sp->parent) {}
168 // thread_is_available() checks whether the thread with threadID "slave" is
169 // available to help the thread with threadID "master" at a split point. An
170 // obvious requirement is that "slave" must be idle. With more than two
171 // threads, this is not by itself sufficient: If "slave" is the master of
172 // some active split point, it is only available as a slave to the other
173 // threads which are busy searching the split point at the top of "slave"'s
174 // split point stack (the "helpful master concept" in YBWC terminology).
176 bool ThreadsManager::thread_is_available(int slave, int master) const {
178 assert(slave >= 0 && slave < activeThreads);
179 assert(master >= 0 && master < activeThreads);
180 assert(activeThreads > 1);
182 if (threads[slave].state != THREAD_AVAILABLE || slave == master)
185 // Make a local copy to be sure doesn't change under our feet
186 int localActiveSplitPoints = threads[slave].activeSplitPoints;
188 // No active split points means that the thread is available as
189 // a slave for any other thread.
190 if (localActiveSplitPoints == 0 || activeThreads == 2)
193 // Apply the "helpful master" concept if possible. Use localActiveSplitPoints
194 // that is known to be > 0, instead of threads[slave].activeSplitPoints that
195 // could have been set to 0 by another thread leading to an out of bound access.
196 if (threads[slave].splitPoints[localActiveSplitPoints - 1].slaves[master])
203 // available_thread_exists() tries to find an idle thread which is available as
204 // a slave for the thread with threadID "master".
206 bool ThreadsManager::available_thread_exists(int master) const {
208 assert(master >= 0 && master < activeThreads);
209 assert(activeThreads > 1);
211 for (int i = 0; i < activeThreads; i++)
212 if (thread_is_available(i, master))
219 // split() does the actual work of distributing the work at a node between
220 // several available threads. If it does not succeed in splitting the
221 // node (because no idle threads are available, or because we have no unused
222 // split point objects), the function immediately returns. If splitting is
223 // possible, a SplitPoint object is initialized with all the data that must be
224 // copied to the helper threads and we tell our helper threads that they have
225 // been assigned work. This will cause them to instantly leave their idle loops and
226 // call search().When all threads have returned from search() then split() returns.
229 void ThreadsManager::split(Position& pos, SearchStack* ss, Value* alpha, const Value beta,
230 Value* bestValue, Depth depth, Move threatMove,
231 int moveCount, MovePicker* mp, bool pvNode) {
233 assert(*bestValue >= -VALUE_INFINITE);
234 assert(*bestValue <= *alpha);
235 assert(*alpha < beta);
236 assert(beta <= VALUE_INFINITE);
237 assert(depth > DEPTH_ZERO);
238 assert(pos.thread() >= 0 && pos.thread() < activeThreads);
239 assert(activeThreads > 1);
241 int i, master = pos.thread();
242 Thread& masterThread = threads[master];
246 // If no other thread is available to help us, or if we have too many
247 // active split points, don't split.
248 if ( !available_thread_exists(master)
249 || masterThread.activeSplitPoints >= MAX_ACTIVE_SPLIT_POINTS)
251 lock_release(&mpLock);
255 // Pick the next available split point object from the split point stack
256 SplitPoint& splitPoint = masterThread.splitPoints[masterThread.activeSplitPoints++];
258 // Initialize the split point object
259 splitPoint.parent = masterThread.splitPoint;
260 splitPoint.master = master;
261 splitPoint.betaCutoff = false;
262 splitPoint.depth = depth;
263 splitPoint.threatMove = threatMove;
264 splitPoint.alpha = *alpha;
265 splitPoint.beta = beta;
266 splitPoint.pvNode = pvNode;
267 splitPoint.bestValue = *bestValue;
269 splitPoint.moveCount = moveCount;
270 splitPoint.pos = &pos;
271 splitPoint.nodes = 0;
273 for (i = 0; i < activeThreads; i++)
274 splitPoint.slaves[i] = 0;
276 masterThread.splitPoint = &splitPoint;
278 // If we are here it means we are not available
279 assert(masterThread.state != THREAD_AVAILABLE);
281 int workersCnt = 1; // At least the master is included
283 // Allocate available threads setting state to THREAD_BOOKED
284 for (i = 0; !Fake && i < activeThreads && workersCnt < maxThreadsPerSplitPoint; i++)
285 if (thread_is_available(i, master))
287 threads[i].state = THREAD_BOOKED;
288 threads[i].splitPoint = &splitPoint;
289 splitPoint.slaves[i] = 1;
293 assert(Fake || workersCnt > 1);
295 // We can release the lock because slave threads are already booked and master is not available
296 lock_release(&mpLock);
298 // Tell the threads that they have work to do. This will make them leave
300 for (i = 0; i < activeThreads; i++)
301 if (i == master || splitPoint.slaves[i])
303 assert(i == master || threads[i].state == THREAD_BOOKED);
305 threads[i].state = THREAD_WORKISWAITING; // This makes the slave to exit from idle_loop()
307 if (useSleepingThreads && i != master)
308 threads[i].wake_up();
311 // Everything is set up. The master thread enters the idle loop, from
312 // which it will instantly launch a search, because its state is
313 // THREAD_WORKISWAITING. We send the split point as a second parameter to the
314 // idle loop, which means that the main thread will return from the idle
315 // loop when all threads have finished their work at this split point.
316 idle_loop(master, &splitPoint);
318 // We have returned from the idle loop, which means that all threads are
319 // finished. Update alpha and bestValue, and return.
322 *alpha = splitPoint.alpha;
323 *bestValue = splitPoint.bestValue;
324 masterThread.activeSplitPoints--;
325 masterThread.splitPoint = splitPoint.parent;
326 pos.set_nodes_searched(pos.nodes_searched() + splitPoint.nodes);
328 lock_release(&mpLock);
331 // Explicit template instantiations
332 template void ThreadsManager::split<0>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool);
333 template void ThreadsManager::split<1>(Position&, SearchStack*, Value*, const Value, Value*, Depth, Move, int, MovePicker*, bool);