What's the best Lazy SMP logic?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
dannyb
Posts: 26
Joined: Mon Jul 09, 2018 4:08 pm
Full name: Daniel Bennett

What's the best Lazy SMP logic?

Post by dannyb » Sun Jan 06, 2019 12:39 pm

There are several approaches regarding parallel search with lazy smp: you can start every other thread with depth+1, increase the depth when the 50% of the threads are already searching at the same depth, skip some depths, randomize the move order, etc.

I would like to know whether there is a general consensus on what's the best way to do it. I know it's not easy to test because you need many games and you can play only few games at the same time.

By the way, can anyone describe how Stockfish's parallel search works? It's not very clear to me.

Sven
Posts: 3822
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: 169
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: 3822
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