Lazy SMP,
based on the shared hash table approach of a parallel search to profit from probing hash entries written by other instances of the search, as already used by Vincent David's αβ* [1]. Multiple processes or threads search the same root position, but are launched with different depths, and/or varying move ordering at the root node, to statistically improve the gains from the effect of nondeterminism, otherwise depending on random timing fluctuations [2]. The term Lazy SMP was coined by Julien Marcel end of 2012 [3] with further elaborations by Daniel Homan[4][5], Martin Sedlak and others. Today, many chess programs use this easy to implement parallel search approach, which scales surprisingly well up to 8 cores and beyond [6], not only in nodes per second (as expected), but in playing strength, while it seems worse than YBW in speedup concerning time to depth[7]. Notably Stockfish 7, released in January 2016, switched from YBW to lazy SMP [8][9][10].
IterativeDeepening:
synchronize smp threads (copy age, board, history, repetition list, multipv => helpers)
depth 1 with full width window on 1 thread
loop (depth=2 .. max)
AspirationLoop:
(as usual)
start helper threads( depth, alpha, beta )
root( depth, alpha, beta)
stop helper threads
(rest as usual)
end aspiration loop
end depth loop
starting helper threads:
clear smp abort flag
for each helper thread:
copy rootmoves and minimum qs depth => helper
signal helper to start root search at current depth (add 1 for each even helper
assuming 0-based indexing) with aspiration alpha, beta bounds and wait until
helper starts searching
aborting helper threads:
set abort flag for each helper and wait for each to stop searching
based on the shared hash table approach of a parallel search to profit from probing hash entries written by other instances of the search, as already used by Vincent David's αβ* [1]. Multiple processes or threads search the same root position, but are launched with different depths, and/or varying move ordering at the root node, to statistically improve the gains from the effect of nondeterminism, otherwise depending on random timing fluctuations [2]. The term Lazy SMP was coined by Julien Marcel end of 2012 [3] with further elaborations by Daniel Homan [4] [5], Martin Sedlak and others. Today, many chess programs use this easy to implement parallel search approach, which scales surprisingly well up to 8 cores and beyond [6], not only in nodes per second (as expected), but in playing strength, while it seems worse than YBW in speedup concerning time to depth [7]. Notably Stockfish 7, released in January 2016, switched from YBW to lazy SMP [8] [9] [10].
Table of Contents
Cheng's Pseudo Code
Pseudo Code of Lazy SMP in Cheng as given by its author Martin Sedlak [12]:IterativeDeepening: synchronize smp threads (copy age, board, history, repetition list, multipv => helpers) depth 1 with full width window on 1 thread loop (depth=2 .. max) AspirationLoop: (as usual) start helper threads( depth, alpha, beta ) root( depth, alpha, beta) stop helper threads (rest as usual) end aspiration loop end depth loop starting helper threads: clear smp abort flag for each helper thread: copy rootmoves and minimum qs depth => helper signal helper to start root search at current depth (add 1 for each even helper assuming 0-based indexing) with aspiration alpha, beta bounds and wait until helper starts searching aborting helper threads: set abort flag for each helper and wait for each to stop searchingSee also
Selected Publications
Abstract: The method of parallelization is based on a suppression of control between the search processes, in favor of a speculative parallelism and full sharing of information achieved through a physically distributed but virtually shared memory. The contribution of our approach for real-time distributed systems and fault-tolerant is evaluated through experimental results.
Forum Posts
2010 ...
2015
Re: A new chess engine : m8 (comming not so soon) by Martin Sedlak, CCC, February 01, 2015
Re: A new chess engine : m8 (comming not so soon) by Peter Österlund, CCC, February 01, 2015
2016
Re: stockfish threading model by Dann Corbit, CCC, May 13, 2016
Re: parallel search speed measurement by Kai Laskos, CCC, May 26, 2016
Re: Crazy SMP by Stan Arts, CCC, June 20, 2016
2017
Lazy SMP and lazy cluster algorithm by Peter Österlund, CCC, August 06, 2017
SMP NPS measurements by Peter Österlund, CCC, August 06, 2017 » Nodes per second
ELO measurements by Peter Österlund, CCC, August 06, 2017 » Playing Strength
Possible improvements by Peter Österlund, CCC, August 06, 2017
Approximate ABDADA by Peter Österlund, CCC, August 23, 2017 » ABDADA
Re: Lazy SMP >4 Thread Slowdown by Ronald de Man, CCC, November 29, 2017
External Links
References
What links here?
Up one level