What's the best Lazy SMP logic?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: What's the best Lazy SMP logic?

Post by Sven » Sun Jan 06, 2019 9:44 pm

dannyb wrote:
Sun Jan 06, 2019 12:39 pm
By the way, can anyone describe how Stockfish's parallel search works? It's not very clear to me.
The basic approach is LazySMP. I'll try to explain what I understand (and as always, explaining also helps a bit in understanding more). Certainly a SF developer can do this much better, though.

"Threads" is a global instance of type "ThreadPool" that contains as many "Thread" objects as configured. In "uci.cpp", go() calls Threads.start_thinking() which wakes up the main thread (thread no. 0 in the pool), which in turn wakes up all other (helper) threads. The latter is done in MainThread::search(). Each thread, including the main thread, now runs its main function Thread::search() which contains the main iterative deepening loop.

After setting up all necessary data structures the iterative deepening loop runs until there is a request to stop or the target search depth (if given) is reached. For each iteration the desired search depth is determined in order to distribute different search depths among all threads. Main thread simply increments depth by 1 each time, helper threads skip some depths based on a clever formula (see SkipSize and SkipPhase in "search.cpp").

When the main thread has completed its search it waits for all helper threads to terminate, too (MainThread::search()). Afterwards the final PV is determined by "voting" for the best thread based on score and depth.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
flok
Posts: 196
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: What's the best Lazy SMP logic?

Post by flok » Fri Sep 06, 2019 8:06 pm

Sven wrote:
Sun Jan 06, 2019 9:44 pm
When the main thread has completed its search it waits for all helper threads to terminate, too (MainThread::search()). Afterwards the final PV is determined by "voting" for the best thread based on score and depth.
What is the algorithm for this voting?

Is it:

Code: Select all

 if cur_depth > prev_best_depth:
    # pick move
 else if cur_depth == prev_best_depth && cur_score > prev_best_score
    # pick move
?
www.vanheusden.com: Micah / Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: What's the best Lazy SMP logic?

Post by Sven » Sat Sep 07, 2019 12:43 pm

The implementation has changed after SF10. Look into search.cpp (search for "votes").
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Post Reply