Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
99 | pmbaty | 1 | /* |
2 | Texel - A UCI chess engine. |
||
3 | Copyright (C) 2013-2014 Peter Ă–sterlund, peterosterlund2@gmail.com |
||
4 | |||
5 | This program is free software: you can redistribute it and/or modify |
||
6 | it under the terms of the GNU General Public License as published by |
||
7 | the Free Software Foundation, either version 3 of the License, or |
||
8 | (at your option) any later version. |
||
9 | |||
10 | This program is distributed in the hope that it will be useful, |
||
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
13 | GNU General Public License for more details. |
||
14 | |||
15 | You should have received a copy of the GNU General Public License |
||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
||
17 | */ |
||
18 | |||
19 | /* |
||
20 | * parallel.hpp |
||
21 | * |
||
22 | * Created on: Jul 9, 2013 |
||
23 | * Author: petero |
||
24 | */ |
||
25 | |||
26 | #ifndef PARALLEL_HPP_ |
||
27 | #define PARALLEL_HPP_ |
||
28 | |||
29 | #include "killerTable.hpp" |
||
30 | #include "history.hpp" |
||
31 | #include "transpositionTable.hpp" |
||
32 | #include "evaluate.hpp" |
||
33 | #include "searchUtil.hpp" |
||
34 | #include "constants.hpp" |
||
35 | #include "util/timeUtil.hpp" |
||
36 | #include "util/heap.hpp" |
||
37 | |||
38 | #include <memory> |
||
39 | #include <vector> |
||
40 | #include <set> |
||
41 | #include <thread> |
||
42 | #include <mutex> |
||
43 | #include <condition_variable> |
||
44 | #include <atomic> |
||
45 | |||
46 | |||
47 | class Search; |
||
48 | class SearchTreeInfo; |
||
49 | |||
50 | class ParallelData; |
||
51 | class SplitPoint; |
||
52 | class SplitPointMove; |
||
53 | class FailHighInfo; |
||
54 | class DepthNpsInfo; |
||
55 | |||
56 | |||
57 | class WorkerThread { |
||
58 | public: |
||
59 | /** Constructor. Does not start new thread. */ |
||
60 | WorkerThread(int threadNo, ParallelData& pd, TranspositionTable& tt); |
||
61 | |||
62 | /** Destructor. Waits for thread to terminate. */ |
||
63 | ~WorkerThread(); |
||
64 | |||
65 | WorkerThread(const WorkerThread&) = delete; |
||
66 | WorkerThread& operator=(const WorkerThread&) = delete; |
||
67 | |||
68 | /** Start thread. */ |
||
69 | void start(); |
||
70 | |||
71 | /** Wait for thread to stop. */ |
||
72 | void join(); |
||
73 | |||
74 | /** Return true if thread is running. */ |
||
75 | bool threadRunning() const; |
||
76 | |||
77 | /** Return thread number. The first worker thread is number 1. */ |
||
78 | int getThreadNo() const; |
||
79 | |||
80 | /** For debugging. */ |
||
81 | double getPUseful() const; |
||
82 | |||
83 | private: |
||
84 | /** Thread main loop. */ |
||
85 | void mainLoop(int minProbeDepth); |
||
86 | |||
87 | int threadNo; |
||
88 | ParallelData& pd; |
||
89 | std::shared_ptr<std::thread> thread; |
||
90 | |||
91 | std::shared_ptr<Evaluate::EvalHashTables> et; |
||
92 | std::shared_ptr<KillerTable> kt; |
||
93 | std::shared_ptr<History> ht; |
||
94 | TranspositionTable& tt; |
||
95 | |||
96 | double pUseful; // Probability that thread is currently doing something useful, for debugging |
||
97 | }; |
||
98 | |||
99 | |||
100 | /** Priority queue of pending search tasks. Handles thread safety. */ |
||
101 | class WorkQueue { |
||
102 | friend class ParallelTest; |
||
103 | public: |
||
104 | /** Constructor. */ |
||
105 | WorkQueue(const FailHighInfo& fhInfo, const DepthNpsInfo& npsInfo); |
||
106 | |||
107 | /** Set/get stopped flag. */ |
||
108 | void setStopped(bool stop); |
||
109 | bool isStopped() const; |
||
110 | |||
111 | /** Reset dynamic minimum split depth to default value. */ |
||
112 | void resetSplitDepth(); |
||
113 | |||
114 | /** Add SplitPoint to work queue. */ |
||
115 | void addWork(const std::shared_ptr<SplitPoint>& sp); |
||
116 | |||
117 | /** Try to add SplitPoint to work queue. If queue is contended add SplitPoint |
||
118 | * to pending instead. */ |
||
119 | void tryAddWork(const std::shared_ptr<SplitPoint>& sp, |
||
120 | std::vector<std::shared_ptr<SplitPoint>>& pending); |
||
121 | |||
122 | /** Get best move for helper thread to work on. */ |
||
123 | std::shared_ptr<SplitPoint> getWork(int& moveNo, ParallelData& pd, int threadNo); |
||
124 | std::shared_ptr<SplitPoint> getWork(int& moveNo, ParallelData& pd, int threadNo, |
||
125 | int& prio, double& pUseful); |
||
126 | |||
127 | /** A helper thread stopped working on a move before it was finished. */ |
||
128 | void returnMove(const std::shared_ptr<SplitPoint>& sp, int moveNo); |
||
129 | |||
130 | /** Set which move number the SplitPoint owner is currently searching. |
||
131 | * @return Score from helper search thread. UNKNOWN_SCORE if no helper has |
||
132 | * searched the move. */ |
||
133 | int setOwnerCurrMove(const std::shared_ptr<SplitPoint>& sp, int moveNo, int alpha); |
||
134 | |||
135 | /** Cancel this SplitPoint and all children. */ |
||
136 | void cancel(const std::shared_ptr<SplitPoint>& sp); |
||
137 | |||
138 | /** Set move to canceled after helper thread finished searching it. */ |
||
139 | void moveFinished(const std::shared_ptr<SplitPoint>& sp, int moveNo, |
||
140 | bool cancelRemaining, int score); |
||
141 | |||
142 | /** Return probability that the best unstarted move needs to be searched. |
||
143 | * Also return the corresponding SplitPoint. */ |
||
144 | double getBestProbability(std::shared_ptr<SplitPoint>& bestSp) const; |
||
145 | double getBestProbability() const; |
||
146 | int getBestPrio() const; |
||
147 | |||
148 | /** Return current dynamic minimum split depth. */ |
||
149 | int getMinSplitDepth() const; |
||
150 | |||
151 | /** For performance measurements on queue operations. */ |
||
152 | void resetStat(); |
||
153 | TimeSampleStatistics& getAddWorkStat(int th); |
||
154 | TimeSampleStatistics& getGetWorkStat(int th); |
||
155 | void printStats(std::ostream& os, int nThreads); |
||
156 | |||
157 | private: |
||
158 | /** Insert sp in queue. Notify condition variable if queue becomes non-empty. */ |
||
159 | void insertInQueue(const std::shared_ptr<SplitPoint>& sp); |
||
160 | |||
161 | /** Recompute probabilities for "sp" and all children. Update "queue" and "waiting". */ |
||
162 | void updateProbabilities(const std::shared_ptr<SplitPoint>& sp); |
||
163 | |||
164 | /** Cancel "sp" and all children. Assumes mutex already locked. */ |
||
165 | void cancelInternal(const std::shared_ptr<SplitPoint>& sp); |
||
166 | |||
167 | void printSpTree(std::ostream& os, const ParallelData& pd, |
||
168 | int threadNo, const std::shared_ptr<SplitPoint> selectedSp, |
||
169 | int selectedMove); |
||
170 | void findLeaves(const std::shared_ptr<SplitPoint>& sp, std::vector<int>& parentThreads, |
||
171 | std::vector<std::shared_ptr<SplitPoint>>& leaves); |
||
172 | |||
173 | /** Helper for addWork() and tryAddWork(). */ |
||
174 | void addWorkInternal(const std::shared_ptr<SplitPoint>& sp); |
||
175 | |||
176 | /** Scoped lock that measures lock contention and adjusts minSplitDepth accordingly. */ |
||
177 | class Lock { |
||
178 | public: |
||
179 | Lock(const WorkQueue* wq0); |
||
180 | void wait(std::condition_variable& cv); |
||
181 | private: |
||
182 | const WorkQueue& wq; |
||
183 | std::unique_lock<std::mutex> lock; |
||
184 | }; |
||
185 | friend class Lock; |
||
186 | std::atomic<bool> stopped; |
||
187 | |||
188 | mutable int minSplitDepth; // Dynamic minimum split depth |
||
189 | mutable U64 nContended; // Number of times mutex has been contended |
||
190 | mutable U64 nNonContended; // Number of times mutex has not been contended |
||
191 | |||
192 | std::condition_variable cv; // Notified when wq becomes non-empty and when search should stop |
||
193 | const FailHighInfo& fhInfo; |
||
194 | const DepthNpsInfo& npsInfo; |
||
195 | mutable std::mutex mutex; |
||
196 | |||
197 | // SplitPoints with unstarted SplitPointMoves |
||
198 | // SplitPoints with no unstarted moves have negative priority. |
||
199 | Heap<SplitPoint> queue; |
||
200 | |||
201 | // For performance debugging |
||
202 | static const int maxStatThreads = 64; |
||
203 | TimeSampleStatisticsVector<maxStatThreads*2> wqStat; |
||
204 | }; |
||
205 | |||
206 | |||
207 | /** Fail high statistics, for estimating SplitPoint usefulness probabilities. */ |
||
208 | class FailHighInfo { |
||
209 | public: |
||
210 | /** Constructor. */ |
||
211 | FailHighInfo(); |
||
212 | |||
213 | /** Return probability that move moveNo needs to be searched. |
||
214 | * @param parentMoveNo Move number of move leading to this position. |
||
215 | * @param currMoveNo Move currently being searched. |
||
216 | * @param moveNo Move number to get probability for. |
||
217 | * @param allNode True if this is an expected ALL node. */ |
||
218 | double getMoveNeededProbability(int parentMoveNo, int currMoveNo, int moveNo, bool allNode) const; |
||
219 | |||
220 | /** Return probability that move moveNo needs to be searched in a PV node. |
||
221 | * @param currMoveNo Move currently being searched. |
||
222 | * @param moveNo Move number to get probability for. |
||
223 | * @param allNode True if this is an expected ALL node. */ |
||
224 | double getMoveNeededProbabilityPv(int currMoveNo, int moveNo) const; |
||
225 | |||
226 | /** Add fail high information. |
||
227 | * @param parentMoveNo Move number of move leading to this position. |
||
228 | * @param nSearched Number of moves searched at this node. |
||
229 | * @param failHigh True if the node failed high. |
||
230 | * @param allNode True if this is an expected ALL node. */ |
||
231 | void addData(int parentMoveNo, int nSearched, bool failHigh, bool allNode); |
||
232 | |||
233 | /** Add "alpha increased" information for PV nodes. |
||
234 | * @param nSearched Number of moves searched at this node. |
||
235 | * @param alphaChanged True if alpha increased after searching move. */ |
||
236 | void addPvData(int nSearched, bool alphaChanged); |
||
237 | |||
238 | /** Rescale the counters so that future updates have more weight. */ |
||
239 | void reScale(); |
||
240 | |||
241 | /** Print object state to "os", for debugging. */ |
||
242 | void print(std::ostream& os) const; |
||
243 | |||
244 | private: |
||
245 | void reScaleInternal(int factor); |
||
246 | void reScalePv(int factor); |
||
247 | |||
248 | int getNodeType(int moveNo, bool allNode) const; |
||
249 | |||
250 | mutable std::mutex mutex; |
||
251 | |||
252 | static const int NUM_NODE_TYPES = 4; |
||
253 | static const int NUM_STAT_MOVES = 15; |
||
254 | |||
255 | RangeSumArray<NUM_STAT_MOVES> failHiCount[NUM_NODE_TYPES]; // [parentMoveNo>0?1:0][moveNo] |
||
256 | std::atomic<int> failLoCount[NUM_NODE_TYPES]; // [parentMoveNo>0?1:0] |
||
257 | std::atomic<int> totCount; // Sum of all counts |
||
258 | |||
259 | std::atomic<int> newAlpha[NUM_STAT_MOVES]; |
||
260 | std::atomic<int> totPvCount; |
||
261 | }; |
||
262 | |||
263 | class DepthNpsInfo { |
||
264 | public: |
||
265 | /** Constructor. */ |
||
266 | DepthNpsInfo(); |
||
267 | |||
268 | /** Reset */ |
||
269 | void reset(); |
||
270 | |||
271 | /** Set thread 0 estimated nps. Used to scale efficiency calculations |
||
272 | * to [0,1] interval. */ |
||
273 | void setBaseNps(double nps); |
||
274 | |||
275 | /** Add one data point. */ |
||
276 | void addData(int depth, U64 nodes, double waitTime, double searchTime); |
||
277 | |||
278 | /** Return estimate search efficiency when searching to a given depth. */ |
||
279 | double efficiency(int depth) const; |
||
280 | |||
281 | /** Print object state to "os", for debugging. */ |
||
282 | void print(std::ostream& os, int iterDepth); |
||
283 | |||
284 | /** Maximum depth statistics is kept for. */ |
||
285 | static const int maxDepth = 48; |
||
286 | |||
287 | private: |
||
288 | /** Helper method for efficiency() and print(). */ |
||
289 | double efficiencyInternal(int depth) const; |
||
290 | |||
291 | mutable std::mutex mutex; |
||
292 | |||
293 | struct NpsData { |
||
294 | NpsData(); |
||
295 | U32 nSearches; |
||
296 | U64 nodes; |
||
297 | double time; |
||
298 | }; |
||
299 | NpsData npsData[maxDepth]; |
||
300 | double nps0; |
||
301 | U32 nSearches; // Total number of searches |
||
302 | double waitTime; // Total waiting time |
||
303 | }; |
||
304 | |||
305 | /** Top-level parallel search data structure. */ |
||
306 | class ParallelData { |
||
307 | public: |
||
308 | /** Constructor. */ |
||
309 | ParallelData(TranspositionTable& tt); |
||
310 | |||
311 | /** Create/delete worker threads so that there are numWorkers in total. */ |
||
312 | void addRemoveWorkers(int numWorkers); |
||
313 | |||
314 | /** Start all worker threads. */ |
||
315 | void startAll(); |
||
316 | |||
317 | /** Stop all worker threads. */ |
||
318 | void stopAll(); |
||
319 | |||
320 | |||
321 | /** Return number of helper threads in use. */ |
||
322 | int numHelperThreads() const; |
||
323 | |||
324 | /** Get number of nodes searched by all helper threads. */ |
||
325 | S64 getNumSearchedNodes() const; |
||
326 | |||
327 | /** Get number of TB hits for all helper threads. */ |
||
328 | S64 getTbHits() const; |
||
329 | |||
330 | /** Add nNodes to total number of searched nodes. */ |
||
331 | void addSearchedNodes(S64 nNodes); |
||
332 | |||
333 | /** Add nTbHits to number of TB hits. */ |
||
334 | void addTbHits(S64 nTbHits); |
||
335 | |||
336 | |||
337 | /** For debugging. */ |
||
338 | const WorkerThread& getHelperThread(int i) const; |
||
339 | |||
340 | FailHighInfo fhInfo; |
||
341 | DepthNpsInfo npsInfo; |
||
342 | |||
343 | WorkQueue wq; |
||
344 | |||
345 | /** Move played in Search::iterativeDeepening before calling negaScout. For debugging. */ |
||
346 | Move topMove; |
||
347 | |||
348 | /** Current node index in thread 0. Used by tree logging code. */ |
||
349 | std::atomic<U32> t0Index; |
||
350 | |||
351 | private: |
||
352 | /** Vector of helper threads. Master thread not included. */ |
||
353 | std::vector<std::shared_ptr<WorkerThread>> threads; |
||
354 | |||
355 | TranspositionTable& tt; |
||
356 | |||
357 | std::atomic<S64> totalHelperNodes; // Number of nodes searched by all helper threads |
||
358 | std::atomic<S64> helperTbHits; // Number of TB hits for all helper threads |
||
359 | }; |
||
360 | |||
361 | |||
362 | /** SplitPoint does not handle thread safety, WorkQueue must do that. */ |
||
363 | class SplitPoint : public Heap<SplitPoint>::HeapObject { |
||
364 | friend class ParallelTest; |
||
365 | public: |
||
366 | /** Constructor. */ |
||
367 | SplitPoint(int threadNo, |
||
368 | const std::shared_ptr<SplitPoint>& parentSp, int parentMoveNo, |
||
369 | const Position& pos, const std::vector<U64>& posHashList, |
||
370 | int posHashListSize, const SearchTreeInfo& sti, |
||
371 | const KillerTable& kt, const History& ht, |
||
372 | int alpha, int beta, int ply, int depth); |
||
373 | |||
374 | SplitPoint(const SplitPoint&) = delete; |
||
375 | SplitPoint& operator=(const SplitPoint&) = delete; |
||
376 | |||
377 | /** Add a child SplitPoint */ |
||
378 | void addChild(const std::weak_ptr<SplitPoint>& child); |
||
379 | |||
380 | /** Add a move to the SplitPoint. */ |
||
381 | void addMove(int moveNo, const SplitPointMove& spMove); |
||
382 | |||
383 | /** Assign sequence number. */ |
||
384 | void setSeqNo(); |
||
385 | |||
386 | /** compute pSpUseful and pnextMoveUseful. */ |
||
387 | void computeProbabilities(const FailHighInfo& fhInfo, const DepthNpsInfo& npsInfo); |
||
388 | |||
389 | /** Get parent SplitPoint, or null for root SplitPoint. */ |
||
390 | std::shared_ptr<SplitPoint> getParent() const; |
||
391 | |||
392 | /** Get children SplitPoints. */ |
||
393 | const std::vector<std::weak_ptr<SplitPoint>>& getChildren() const; |
||
394 | |||
395 | |||
396 | U64 getSeqNo() const; |
||
397 | double getPSpUseful() const; |
||
398 | double getPNextMoveUseful() const; |
||
399 | const History& getHistory() const; |
||
400 | const KillerTable& getKillerTable() const; |
||
401 | const SplitPointMove& getSpMove(int moveNo) const; |
||
402 | |||
403 | /** Return probability that moveNo needs to be searched. */ |
||
404 | double getPMoveUseful(const FailHighInfo& fhInfo, int moveNo) const; |
||
405 | |||
406 | void getPos(Position& pos, const Move& move) const; |
||
407 | void getPosHashList(const Position& pos, std::vector<U64>& posHashList, |
||
408 | int& posHashListSize) const; |
||
409 | const SearchTreeInfo& getSearchTreeInfo() const; |
||
410 | int getAlpha() const; |
||
411 | int getBeta() const; |
||
412 | int getPly() const; |
||
413 | int getDepth() const; |
||
414 | |||
415 | |||
416 | /** Get index of first unstarted move. Mark move as being searched. |
||
417 | * Return -1 if there are no unstarted moves. */ |
||
418 | int getNextMove(const FailHighInfo& fhInfo); |
||
419 | |||
420 | /** A helper thread stopped working on a move before it was finished. */ |
||
421 | void returnMove(int moveNo); |
||
422 | |||
423 | /** Set which move number the SplitPoint owner is currently searching. |
||
424 | * @return Score from helper search thread. UNKNOWN_SCORE if no helper has |
||
425 | * searched the move. */ |
||
426 | int setOwnerCurrMove(int moveNo, int alpha); |
||
427 | |||
428 | /** Cancel this SplitPoint and all children. */ |
||
429 | void cancel(); |
||
430 | |||
431 | /** Return true if this SplitPoint has been canceled. */ |
||
432 | bool isCanceled() const; |
||
433 | |||
434 | /** Set move to canceled after helper thread finished searching it. */ |
||
435 | void moveFinished(int moveNo, bool cancelRemaining, int score); |
||
436 | |||
437 | /** Return true if there are moves that have not been started to be searched. */ |
||
438 | bool hasUnStartedMove() const; |
||
439 | |||
440 | /** Return true if there are moves that have not been finished (canceled) yet. */ |
||
441 | bool hasUnFinishedMove() const; |
||
442 | |||
443 | /** Return true if this SplitPoint is an ancestor to "sp". */ |
||
444 | bool isAncestorTo(const SplitPoint& sp) const; |
||
445 | |||
446 | /** Return true if some other thread is helping the SplitPoint owner. */ |
||
447 | bool hasHelperThread() const; |
||
448 | |||
449 | /** Return true if the held SplitPoint is an estimated ALL node. */ |
||
450 | bool isAllNode() const; |
||
451 | |||
452 | /** Return true if beta > alpha + 1. */ |
||
453 | bool isPvNode() const; |
||
454 | |||
455 | /** Compute SplitPoint priority. The SplitPoint with highest |
||
456 | * priority will be selected first by the next available thread. */ |
||
457 | int getSpPrio(const DepthNpsInfo& npsInfo) const; |
||
458 | |||
459 | /** Thread that created this SplitPoint. */ |
||
460 | int owningThread() const; |
||
461 | |||
462 | /** Return true if object is or has been inserted in WorkQueue. */ |
||
463 | bool wasInserted() const; |
||
464 | |||
465 | /** Mark SplitPoint as inserted in WorkQueue. */ |
||
466 | void setInserted(); |
||
467 | |||
468 | /** Print object state to "os", for debugging. */ |
||
469 | void print(std::ostream& os, int level, const FailHighInfo& fhInfo) const; |
||
470 | |||
471 | /** For debugging. */ |
||
472 | int getParentMoveNo() const; |
||
473 | |||
474 | /** For debugging. */ |
||
475 | int getCurrMoveNo() const; |
||
476 | |||
477 | /** Get index of first unstarted move, or -1 if there is no unstarted move. */ |
||
478 | int findNextMove(const FailHighInfo& fhInfo) const; |
||
479 | |||
480 | private: |
||
481 | /** Return probability that moveNo needs to be searched, by calling corresponding |
||
482 | * function in fhInfo. */ |
||
483 | double getMoveNeededProbability(const FailHighInfo& fhInfo, int moveNo) const; |
||
484 | |||
485 | /** Remove null entries from children vector. */ |
||
486 | void cleanUpChildren(); |
||
487 | |||
488 | const Position pos; |
||
489 | const std::vector<U64> posHashList; // List of hashes for previous positions up to the last "zeroing" move. |
||
490 | const int posHashListSize; |
||
491 | const SearchTreeInfo searchTreeInfo; // For ply-1 |
||
492 | const KillerTable& kt; |
||
493 | const History& ht; |
||
494 | |||
495 | RelaxedShared<int> alpha; |
||
496 | const int beta; |
||
497 | const int ply; |
||
498 | const int depth; |
||
499 | const bool isPV; |
||
500 | |||
501 | double pSpUseful; // Probability that this SplitPoint is needed. 100% if parent is null. |
||
502 | double pNextMoveUseful; // Probability that next unstarted move needs to be searched. |
||
503 | |||
504 | const int threadNo; // Owning thread |
||
505 | const std::shared_ptr<SplitPoint> parent; |
||
506 | const int parentMoveNo; // Move number in parent SplitPoint that generated this SplitPoint |
||
507 | std::vector<std::weak_ptr<SplitPoint>> children; |
||
508 | |||
509 | static U64 nextSeqNo; |
||
510 | U64 seqNo; // To break ties when two objects have same priority. Set by addWork() under lock |
||
511 | int currMoveNo; |
||
512 | std::vector<SplitPointMove> spMoves; |
||
513 | |||
514 | bool inserted; // True if sp has been inserted in WorkQueue. Remains true after deletion. |
||
515 | bool canceled; |
||
516 | }; |
||
517 | |||
518 | |||
519 | /** Represents one move at a SplitPoint. */ |
||
520 | class SplitPointMove { |
||
521 | public: |
||
522 | /** Constructor */ |
||
523 | SplitPointMove(const Move& move, int lmr, int depth, |
||
524 | int captSquare, bool inCheck); |
||
525 | |||
526 | const Move& getMove() const; |
||
527 | int getLMR() const; |
||
528 | int getDepth() const; |
||
529 | int getRecaptureSquare() const; |
||
530 | bool getInCheck() const; |
||
531 | |||
532 | bool isCanceled() const; |
||
533 | void setCanceled(bool value); |
||
534 | |||
535 | bool isSearching() const; |
||
536 | void setSearching(bool value); |
||
537 | |||
538 | void setScore(int s); |
||
539 | int getScore() const; |
||
540 | |||
541 | private: |
||
542 | Move move; // Position defined by sp->pos + move |
||
543 | int lmr; // Amount of LMR reduction |
||
544 | int depth; |
||
545 | int captSquare; // Recapture square, or -1 if no recapture |
||
546 | bool inCheck; // True if side to move is in check |
||
547 | |||
548 | RelaxedShared<bool> canceled; // Result is no longer needed |
||
549 | bool searching; // True if currently searched by a helper thread |
||
550 | int score; |
||
551 | }; |
||
552 | |||
553 | |||
554 | /** Handle a SplitPoint object using RAII. */ |
||
555 | class SplitPointHolder { |
||
556 | public: |
||
557 | /** Constructor. */ |
||
558 | SplitPointHolder(ParallelData& pd, std::vector<std::shared_ptr<SplitPoint>>& spVec, |
||
559 | std::vector<std::shared_ptr<SplitPoint>>& pending); |
||
560 | |||
561 | /** Destructor. Cancel SplitPoint. */ |
||
562 | ~SplitPointHolder(); |
||
563 | |||
564 | SplitPointHolder(const SplitPointHolder&) = delete; |
||
565 | SplitPointHolder& operator=(const SplitPointHolder&) = delete; |
||
566 | |||
567 | /** Set the SplitPoint object. */ |
||
568 | void setSp(const std::shared_ptr<SplitPoint>& sp); |
||
569 | |||
570 | /** Add a move to the SplitPoint. */ |
||
571 | void addMove(int moveNo, const SplitPointMove& spMove); |
||
572 | |||
573 | /** Add SplitPoint to work queue. If the queue is contended, store SplitPoint |
||
574 | * in pending vector instead. If queue is not contended, also insert all |
||
575 | * objects from the pending vector and clear the pending vector. */ |
||
576 | void addToQueue(); |
||
577 | |||
578 | /** Set which move number the SplitPoint owner is currently searching. |
||
579 | * @return Score from helper search thread. UNKNOWN_SCORE if no helper has |
||
580 | * searched the move. */ |
||
581 | int setOwnerCurrMove(int moveNo, int alpha); |
||
582 | |||
583 | /** For debugging. */ |
||
584 | U64 getSeqNo() const; |
||
585 | |||
586 | /** Return true if the held SplitPoint is an estimated ALL node. */ |
||
587 | bool isAllNode() const; |
||
588 | |||
589 | /** Return true if some other thread is helping the help SplitPoint. */ |
||
590 | bool hasHelperThread() const; |
||
591 | |||
592 | private: |
||
593 | ParallelData& pd; |
||
594 | std::vector<std::shared_ptr<SplitPoint>>& spVec; |
||
595 | std::vector<std::shared_ptr<SplitPoint>>& pending; |
||
596 | std::shared_ptr<SplitPoint> sp; |
||
597 | enum class State { EMPTY, CREATED, QUEUED } state; |
||
598 | }; |
||
599 | |||
600 | /** Dummy version of SplitPointHolder class. */ |
||
601 | struct DummySplitPointHolder { |
||
602 | DummySplitPointHolder(ParallelData& pd, std::vector<std::shared_ptr<SplitPoint>>& spVec, |
||
603 | std::vector<std::shared_ptr<SplitPoint>>& pending) {} |
||
604 | void setSp(const std::shared_ptr<SplitPoint>& sp) {} |
||
605 | void addMove(int moveNo, const SplitPointMove& spMove) {} |
||
606 | void addToQueue() {} |
||
607 | int setOwnerCurrMove(int moveNo, int alpha) { return SearchConst::UNKNOWN_SCORE; } |
||
608 | bool isAllNode() const { return false; } |
||
609 | }; |
||
610 | |||
611 | template <bool smp> struct SplitPointTraits { |
||
612 | }; |
||
613 | template<> struct SplitPointTraits<true> { |
||
614 | using SpHolder = SplitPointHolder; |
||
615 | }; |
||
616 | template<> struct SplitPointTraits<false> { |
||
617 | using SpHolder = DummySplitPointHolder; |
||
618 | }; |
||
619 | |||
620 | |||
621 | inline bool |
||
622 | WorkerThread::threadRunning() const { |
||
623 | return thread != nullptr; |
||
624 | } |
||
625 | |||
626 | inline int |
||
627 | WorkerThread::getThreadNo() const { |
||
628 | return threadNo; |
||
629 | } |
||
630 | |||
631 | inline double |
||
632 | WorkerThread::getPUseful() const { |
||
633 | return pUseful; |
||
634 | } |
||
635 | |||
636 | inline |
||
637 | WorkQueue::WorkQueue(const FailHighInfo& fhInfo0, const DepthNpsInfo& npsInfo0) |
||
638 | : stopped(false), fhInfo(fhInfo0), npsInfo(npsInfo0) { |
||
639 | resetSplitDepth(); |
||
640 | } |
||
641 | |||
642 | inline bool |
||
643 | WorkQueue::isStopped() const { |
||
644 | return stopped; |
||
645 | } |
||
646 | |||
647 | inline void |
||
648 | WorkQueue::resetSplitDepth() { |
||
649 | minSplitDepth = SearchConst::MIN_SMP_DEPTH; |
||
650 | nContended = 0; |
||
651 | nNonContended = 0; |
||
652 | } |
||
653 | |||
654 | inline int |
||
655 | WorkQueue::getMinSplitDepth() const { |
||
656 | return minSplitDepth; |
||
657 | } |
||
658 | |||
659 | inline void |
||
660 | WorkQueue::insertInQueue(const std::shared_ptr<SplitPoint>& sp) { |
||
661 | bool wasEmpty = queue.empty() || (queue.front()->getPrio() < 0); |
||
662 | queue.insert(sp, sp->getSpPrio(npsInfo)); |
||
663 | sp->setInserted(); |
||
664 | if (wasEmpty) |
||
665 | cv.notify_all(); |
||
666 | } |
||
667 | |||
668 | inline void |
||
669 | WorkQueue::resetStat() { |
||
670 | for (auto& s : wqStat) |
||
671 | s.reset(); |
||
672 | } |
||
673 | |||
674 | inline TimeSampleStatistics& |
||
675 | WorkQueue::getAddWorkStat(int th) { |
||
676 | assert(th < maxStatThreads); |
||
677 | return wqStat[th]; |
||
678 | } |
||
679 | |||
680 | inline TimeSampleStatistics& |
||
681 | WorkQueue::getGetWorkStat(int th) { |
||
682 | assert(th < maxStatThreads); |
||
683 | return wqStat[maxStatThreads+th]; |
||
684 | } |
||
685 | |||
686 | inline void |
||
687 | WorkQueue::printStats(std::ostream& os, int nThreads) { |
||
688 | for (int i = 0; i < nThreads; i++) { |
||
689 | os << "th:" << i << " add: "; |
||
690 | getAddWorkStat(i).printNs(os); |
||
691 | os << " get: "; |
||
692 | getGetWorkStat(i).printNs(os); |
||
693 | os << std::endl; |
||
694 | } |
||
695 | } |
||
696 | |||
697 | |||
698 | inline int |
||
699 | FailHighInfo::getNodeType(int moveNo, bool allNode) const { |
||
700 | if (moveNo == 0) |
||
701 | return allNode ? 0 : 3; |
||
702 | else if (moveNo > 0) |
||
703 | return 1; |
||
704 | else |
||
705 | return 2; |
||
706 | } |
||
707 | |||
708 | inline |
||
709 | DepthNpsInfo::DepthNpsInfo() { |
||
710 | reset(); |
||
711 | } |
||
712 | |||
713 | inline |
||
714 | DepthNpsInfo::NpsData::NpsData() |
||
715 | : nSearches(0), nodes(0), time(0) { |
||
716 | } |
||
717 | |||
718 | inline void |
||
719 | DepthNpsInfo::reset() { |
||
720 | std::lock_guard<std::mutex> L(mutex); |
||
721 | for (int i = 0; i < maxDepth; i++) { |
||
722 | npsData[i].nSearches = 0; |
||
723 | npsData[i].nodes = 0; |
||
724 | npsData[i].time = 0; |
||
725 | } |
||
726 | nps0 = 0; |
||
727 | nSearches = 0; |
||
728 | waitTime = 0; |
||
729 | } |
||
730 | |||
731 | inline void |
||
732 | DepthNpsInfo::setBaseNps(double nps) { |
||
733 | std::lock_guard<std::mutex> L(mutex); |
||
734 | nps0 = nps; |
||
735 | } |
||
736 | |||
737 | inline void |
||
738 | DepthNpsInfo::addData(int depth, U64 nodes, double wTime, double searchTime) { |
||
739 | if (depth >= maxDepth) |
||
740 | depth = maxDepth - 1; |
||
741 | std::lock_guard<std::mutex> L(mutex); |
||
742 | npsData[depth].nSearches++; |
||
743 | npsData[depth].nodes += nodes; |
||
744 | npsData[depth].time += searchTime; |
||
745 | nSearches++; |
||
746 | waitTime += wTime; |
||
747 | } |
||
748 | |||
749 | inline double |
||
750 | DepthNpsInfo::efficiency(int depth) const { |
||
751 | if (depth >= maxDepth) |
||
752 | depth = maxDepth - 1; |
||
753 | std::lock_guard<std::mutex> L(mutex); |
||
754 | return efficiencyInternal(depth); |
||
755 | } |
||
756 | |||
757 | inline double |
||
758 | DepthNpsInfo::efficiencyInternal(int depth) const { |
||
759 | if ((npsData[depth].time > 0) && (nps0 > 0)) { |
||
760 | U64 nodes = npsData[depth].nodes; |
||
761 | double time = npsData[depth].time; |
||
762 | const U32 ns = npsData[depth].nSearches; |
||
763 | if (nSearches > 0) |
||
764 | time += waitTime / nSearches * ns; |
||
765 | double nps = nodes / time; |
||
766 | double eff = nps / nps0; |
||
767 | if (eff > 1.0) |
||
768 | eff = 1.0; |
||
769 | return (eff * ns + 1 * 500) / (ns + 500); |
||
770 | } else |
||
771 | return 1.0; |
||
772 | } |
||
773 | |||
774 | inline void |
||
775 | WorkQueue::Lock::wait(std::condition_variable& cv) { |
||
776 | cv.wait(lock); |
||
777 | } |
||
778 | |||
779 | |||
780 | inline ParallelData::ParallelData(TranspositionTable& tt0) |
||
781 | : wq(fhInfo, npsInfo), t0Index(0), tt(tt0), |
||
782 | totalHelperNodes(0), helperTbHits(0) { |
||
783 | } |
||
784 | |||
785 | inline int |
||
786 | ParallelData::numHelperThreads() const { |
||
787 | return (int)threads.size(); |
||
788 | } |
||
789 | |||
790 | inline S64 |
||
791 | ParallelData::getNumSearchedNodes() const { |
||
792 | return totalHelperNodes; |
||
793 | } |
||
794 | |||
795 | inline S64 |
||
796 | ParallelData::getTbHits() const { |
||
797 | return helperTbHits; |
||
798 | } |
||
799 | |||
800 | inline void |
||
801 | ParallelData::addSearchedNodes(S64 nNodes) { |
||
802 | totalHelperNodes += nNodes; |
||
803 | } |
||
804 | |||
805 | inline void |
||
806 | ParallelData::addTbHits(S64 nTbHits) { |
||
807 | helperTbHits += nTbHits; |
||
808 | } |
||
809 | |||
810 | inline const WorkerThread& |
||
811 | ParallelData::getHelperThread(int i) const { |
||
812 | return *threads[i]; |
||
813 | } |
||
814 | |||
815 | |||
816 | inline bool |
||
817 | SplitPoint::isCanceled() const { |
||
818 | return canceled; |
||
819 | } |
||
820 | |||
821 | inline void |
||
822 | SplitPoint::setSeqNo() { |
||
823 | seqNo = nextSeqNo++; |
||
824 | } |
||
825 | |||
826 | inline std::shared_ptr<SplitPoint> |
||
827 | SplitPoint::getParent() const { |
||
828 | return parent; |
||
829 | } |
||
830 | |||
831 | inline const std::vector<std::weak_ptr<SplitPoint>>& |
||
832 | SplitPoint::getChildren() const { |
||
833 | return children; |
||
834 | } |
||
835 | |||
836 | inline U64 |
||
837 | SplitPoint::getSeqNo() const { |
||
838 | return seqNo; |
||
839 | } |
||
840 | |||
841 | inline double |
||
842 | SplitPoint::getPSpUseful() const { |
||
843 | return pSpUseful; |
||
844 | } |
||
845 | |||
846 | inline double |
||
847 | SplitPoint::getPNextMoveUseful() const { |
||
848 | return pNextMoveUseful; |
||
849 | } |
||
850 | |||
851 | inline const History& |
||
852 | SplitPoint::getHistory() const { |
||
853 | return ht; |
||
854 | } |
||
855 | |||
856 | inline const KillerTable& |
||
857 | SplitPoint::getKillerTable() const { |
||
858 | return kt; |
||
859 | } |
||
860 | |||
861 | inline const SplitPointMove& |
||
862 | SplitPoint::getSpMove(int moveNo) const { |
||
863 | return spMoves[moveNo]; |
||
864 | } |
||
865 | |||
866 | inline const SearchTreeInfo& |
||
867 | SplitPoint::getSearchTreeInfo() const { |
||
868 | return searchTreeInfo; |
||
869 | } |
||
870 | |||
871 | inline int |
||
872 | SplitPoint::getAlpha() const { |
||
873 | return alpha; |
||
874 | } |
||
875 | |||
876 | inline int |
||
877 | SplitPoint::getBeta() const { |
||
878 | return beta; |
||
879 | } |
||
880 | |||
881 | inline int |
||
882 | SplitPoint::getPly() const { |
||
883 | return ply; |
||
884 | } |
||
885 | |||
886 | inline int |
||
887 | SplitPoint::getDepth() const { |
||
888 | return depth; |
||
889 | } |
||
890 | |||
891 | inline void |
||
892 | SplitPoint::returnMove(int moveNo) { |
||
893 | assert((moveNo >= 0) && (moveNo < (int)spMoves.size())); |
||
894 | SplitPointMove& spm = spMoves[moveNo]; |
||
895 | spm.setSearching(false); |
||
896 | } |
||
897 | |||
898 | inline int |
||
899 | SplitPoint::setOwnerCurrMove(int moveNo, int newAlpha) { |
||
900 | assert((moveNo >= 0) && (moveNo < (int)spMoves.size())); |
||
901 | int score = spMoves[moveNo].getScore(); |
||
902 | spMoves[moveNo].setCanceled(true); |
||
903 | currMoveNo = moveNo; |
||
904 | if (newAlpha > alpha) |
||
905 | alpha = newAlpha; |
||
906 | return score; |
||
907 | } |
||
908 | |||
909 | inline void |
||
910 | SplitPoint::cancel() { |
||
911 | canceled = true; |
||
912 | for (SplitPointMove& spMove : spMoves) |
||
913 | spMove.setCanceled(true); |
||
914 | } |
||
915 | |||
916 | inline void |
||
917 | SplitPoint::addChild(const std::weak_ptr<SplitPoint>& child) { |
||
918 | children.push_back(child); |
||
919 | } |
||
920 | |||
921 | inline bool |
||
922 | SplitPoint::isPvNode() const { |
||
923 | return isPV; |
||
924 | } |
||
925 | |||
926 | inline int |
||
927 | SplitPoint::getSpPrio(const DepthNpsInfo& npsInfo) const { |
||
928 | if (!hasUnStartedMove()) |
||
929 | return -1; |
||
930 | return (int)(getPNextMoveUseful() * npsInfo.efficiency(getDepth()) * 1000); |
||
931 | } |
||
932 | |||
933 | inline int |
||
934 | SplitPoint::owningThread() const { |
||
935 | return threadNo; |
||
936 | } |
||
937 | |||
938 | inline bool |
||
939 | SplitPoint::wasInserted() const { |
||
940 | return inserted; |
||
941 | } |
||
942 | |||
943 | inline void |
||
944 | SplitPoint::setInserted() { |
||
945 | inserted = true; |
||
946 | } |
||
947 | |||
948 | inline int |
||
949 | SplitPoint::getParentMoveNo() const { |
||
950 | return parentMoveNo; |
||
951 | } |
||
952 | |||
953 | inline int |
||
954 | SplitPoint::getCurrMoveNo() const { |
||
955 | return currMoveNo; |
||
956 | } |
||
957 | |||
958 | |||
959 | inline |
||
960 | SplitPointMove::SplitPointMove(const Move& move0, int lmr0, int depth0, |
||
961 | int captSquare0, bool inCheck0) |
||
962 | : move(move0), lmr(lmr0), depth(depth0), captSquare(captSquare0), |
||
963 | inCheck(inCheck0), canceled(false), searching(false), |
||
964 | score(SearchConst::UNKNOWN_SCORE) { |
||
965 | } |
||
966 | |||
967 | inline const Move& |
||
968 | SplitPointMove::getMove() const { |
||
969 | return move; |
||
970 | } |
||
971 | |||
972 | inline int |
||
973 | SplitPointMove::getLMR() const { |
||
974 | return lmr; |
||
975 | } |
||
976 | |||
977 | inline int |
||
978 | SplitPointMove::getDepth() const { |
||
979 | return depth; |
||
980 | } |
||
981 | |||
982 | inline int |
||
983 | SplitPointMove::getRecaptureSquare() const { |
||
984 | return captSquare; |
||
985 | } |
||
986 | |||
987 | inline bool |
||
988 | SplitPointMove::getInCheck() const { |
||
989 | return inCheck; |
||
990 | } |
||
991 | |||
992 | inline bool |
||
993 | SplitPointMove::isCanceled() const { |
||
994 | return canceled; |
||
995 | } |
||
996 | |||
997 | inline void |
||
998 | SplitPointMove::setCanceled(bool value) { |
||
999 | canceled = value; |
||
1000 | } |
||
1001 | |||
1002 | inline bool |
||
1003 | SplitPointMove::isSearching() const { |
||
1004 | return searching; |
||
1005 | } |
||
1006 | |||
1007 | inline void |
||
1008 | SplitPointMove::setSearching(bool value) { |
||
1009 | searching = value; |
||
1010 | } |
||
1011 | |||
1012 | inline void |
||
1013 | SplitPointMove::setScore(int s) { |
||
1014 | score = s; |
||
1015 | } |
||
1016 | |||
1017 | inline int |
||
1018 | SplitPointMove::getScore() const { |
||
1019 | return score; |
||
1020 | } |
||
1021 | |||
1022 | |||
1023 | inline |
||
1024 | SplitPointHolder::SplitPointHolder(ParallelData& pd0, |
||
1025 | std::vector<std::shared_ptr<SplitPoint>>& spVec0, |
||
1026 | std::vector<std::shared_ptr<SplitPoint>>& pending0) |
||
1027 | : pd(pd0), spVec(spVec0), pending(pending0), |
||
1028 | state(State::EMPTY) { |
||
1029 | } |
||
1030 | |||
1031 | inline |
||
1032 | SplitPointHolder::~SplitPointHolder() { |
||
1033 | if (state == State::QUEUED) { |
||
1034 | // log([&](std::ostream& os){os << "cancel seqNo:" << sp->getSeqNo();}); |
||
1035 | if (sp->wasInserted()) |
||
1036 | pd.wq.cancel(sp); |
||
1037 | else { |
||
1038 | if (pending.size() > 0) { |
||
1039 | assert(pending[pending.size()-1] == sp); |
||
1040 | pending.pop_back(); |
||
1041 | } |
||
1042 | } |
||
1043 | assert(!spVec.empty()); |
||
1044 | spVec.pop_back(); |
||
1045 | } |
||
1046 | } |
||
1047 | |||
1048 | inline void |
||
1049 | SplitPointHolder::addMove(int moveNo, const SplitPointMove& spMove) { |
||
1050 | assert(state == State::CREATED); |
||
1051 | sp->addMove(moveNo, spMove); |
||
1052 | } |
||
1053 | |||
1054 | inline int |
||
1055 | SplitPointHolder::setOwnerCurrMove(int moveNo, int alpha) { |
||
1056 | // if (sp->hasHelperThread()) |
||
1057 | // log([&](std::ostream& os){os << "seqNo:" << sp->getSeqNo() << " currMove:" << moveNo |
||
1058 | // << " a:" << alpha;}); |
||
1059 | if (sp->wasInserted()) |
||
1060 | return pd.wq.setOwnerCurrMove(sp, moveNo, alpha); |
||
1061 | else |
||
1062 | return sp->setOwnerCurrMove(moveNo, alpha); |
||
1063 | } |
||
1064 | |||
1065 | inline U64 |
||
1066 | SplitPointHolder::getSeqNo() const { |
||
1067 | return sp->getSeqNo(); |
||
1068 | } |
||
1069 | |||
1070 | inline bool |
||
1071 | SplitPointHolder::isAllNode() const { |
||
1072 | return sp->isAllNode(); |
||
1073 | } |
||
1074 | |||
1075 | inline bool |
||
1076 | SplitPointHolder::hasHelperThread() const { |
||
1077 | return sp->hasHelperThread(); |
||
1078 | } |
||
1079 | |||
1080 | #endif /* PARALLEL_HPP_ */ |