Difference between revisions of "Lazy SMP"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(11 intermediate revisions by the same user not shown) | |||
Line 73: | Line 73: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=56019 Empirical results with Lazy SMP, YBWC, DTS] by [[Kai Laskos]], [[CCC]], April 16, 2015 » [[Lazy SMP]], [[Young Brothers Wait Concept|YBWC]], [[Dynamic Tree Splitting|DTS]] | * [http://www.talkchess.com/forum/viewtopic.php?t=56019 Empirical results with Lazy SMP, YBWC, DTS] by [[Kai Laskos]], [[CCC]], April 16, 2015 » [[Lazy SMP]], [[Young Brothers Wait Concept|YBWC]], [[Dynamic Tree Splitting|DTS]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=57572 lazy smp questions] by Lucas Braesch, [[CCC]], September 09, 2015 | * [http://www.talkchess.com/forum/viewtopic.php?t=57572 lazy smp questions] by Lucas Braesch, [[CCC]], September 09, 2015 | ||
− | * [https://groups.google.com/d/msg/fishcooking/GVdyWSWEpQY/bZbeaJAbBgAJ Lazy SMP] by Mikael, [[Computer Chess Forums|FishCooking]], September 26, 2015 » [[Stockfish]] | + | * [https://groups.google.com/d/msg/fishcooking/GVdyWSWEpQY/bZbeaJAbBgAJ Lazy SMP] by [[Mikael Bäckman|Mikael]], [[Computer Chess Forums|FishCooking]], September 26, 2015 » [[Stockfish]] |
+ | * [https://groups.google.com/d/msg/fishcooking/vGgxv_W_LOI/SAQOxpFsBwAJ Komodo, Lazy SMP, and the like :-)] by [[Stephane Nicolet]], [[Computer Chess Forums|FishCooking]], September 30, 2015 » [[Komodo]], [[Stockfish]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=58031 Lazy SMP Better than YBWC?] by [[Steve Maughan]], [[CCC]], October 23, 2015 » [[Young Brothers Wait Concept]] | * [http://www.talkchess.com/forum/viewtopic.php?t=58031 Lazy SMP Better than YBWC?] by [[Steve Maughan]], [[CCC]], October 23, 2015 » [[Young Brothers Wait Concept]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=58056 New Stockfish with Lazy_SMP, but what about the TC bug ?] by [[Ernest Bonnem]], [[CCC]], October 26, 2015 » [[Stockfish]], [[TCEC Season 8]] | * [http://www.talkchess.com/forum/viewtopic.php?t=58056 New Stockfish with Lazy_SMP, but what about the TC bug ?] by [[Ernest Bonnem]], [[CCC]], October 26, 2015 » [[Stockfish]], [[TCEC Season 8]] | ||
Line 79: | Line 80: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015 | * [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015 | ||
==2016== | ==2016== | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by Kalyankumar Ramaseshan, [[CCC]], February 29, 2016 | + | * [http://www.talkchess.com/forum/viewtopic.php?t=59389 Lazy SMP - how it works] by [[Kalyankumar Ramaseshan]], [[CCC]], February 29, 2016 |
* [http://www.talkchess.com/forum/viewtopic.php?t=59732 Pedone 1.4] by [[Fabio Gobbato]], [[CCC]], April 03, 2016 » [[Pedone]] | * [http://www.talkchess.com/forum/viewtopic.php?t=59732 Pedone 1.4] by [[Fabio Gobbato]], [[CCC]], April 03, 2016 » [[Pedone]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=60155 stockfish threading model] by [[Folkert van Heusden]], [[CCC]], May 13, 2016 | * [http://www.talkchess.com/forum/viewtopic.php?t=60155 stockfish threading model] by [[Folkert van Heusden]], [[CCC]], May 13, 2016 | ||
Line 94: | Line 95: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=63454 How to find SMP bugs ?] by Lucas Braesch, [[CCC]], March 15, 2017 | * [http://www.talkchess.com/forum/viewtopic.php?t=63454 How to find SMP bugs ?] by Lucas Braesch, [[CCC]], March 15, 2017 | ||
* [http://www.open-chess.org/viewtopic.php?f=5&t=3097 Ideas to improve SMP scaling] by lucasart, [[Computer Chess Forums|OpenChess Forum]], April 03, 2017 | * [http://www.open-chess.org/viewtopic.php?f=5&t=3097 Ideas to improve SMP scaling] by lucasart, [[Computer Chess Forums|OpenChess Forum]], April 03, 2017 | ||
+ | * [https://groups.google.com/d/msg/fishcooking/Cbm5y4dpeEE/wYmQokNfAAAJ Some data about LazySMP] by [[Stephane Nicolet]], [[Computer Chess Forums|FishCooking]], April 08, 2017 » [[Stockfish]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=63903 Symmetric multiprocessing (SMP) scaling - SF8 and K10.4] by [[Andreas Strangmüller]], [[CCC]], May 05, 2017 » [[Komodo]], [[Stockfish]] | * [http://www.talkchess.com/forum/viewtopic.php?t=63903 Symmetric multiprocessing (SMP) scaling - SF8 and K10.4] by [[Andreas Strangmüller]], [[CCC]], May 05, 2017 » [[Komodo]], [[Stockfish]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=63955 Symmetric multiprocessing (SMP) scaling - K10.4 Contempt=0] by [[Andreas Strangmüller]], [[CCC]], May 11, 2017 » [[SMP]], [[Komodo]], [[Contempt Factor]] | * [http://www.talkchess.com/forum/viewtopic.php?t=63955 Symmetric multiprocessing (SMP) scaling - K10.4 Contempt=0] by [[Andreas Strangmüller]], [[CCC]], May 11, 2017 » [[SMP]], [[Komodo]], [[Contempt Factor]] | ||
Line 116: | Line 118: | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69481 Simplest way to implement quick and dirty lazy smp] by [[Tom King]], [[CCC]], January 04, 2019 | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69481 Simplest way to implement quick and dirty lazy smp] by [[Tom King]], [[CCC]], January 04, 2019 | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69507 What's the best Lazy SMP logic?] by Daniel Bennett, [[CCC]], January 06, 2019 » [[Stockfish]] | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69507 What's the best Lazy SMP logic?] by Daniel Bennett, [[CCC]], January 06, 2019 » [[Stockfish]] | ||
− | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70919 strategies for finding slowdows in lazy smp] by [[Folkert van Heusden]], [[CCC]], June 04, 2019 » [[Nodes per Second]] | + | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70919 strategies for finding slowdows in lazy smp] by [[Folkert van Heusden]], [[CCC]], June 04, 2019 » [[Nodes per Second]], [[Thread]] |
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72684 RMO - Randomized Move Order - yet another Lazy SMP derivate] by [[Srdja Matovic]], [[CCC]], December 30, 2019 | ||
+ | ==2020== | ||
+ | * [https://groups.google.com/d/msg/fishcooking/9X3lDH83tlk/DtRtuFMOCAAJ lazy smp behaviour of stockfish] by [[Daniel Shawul]], [[Computer Chess Forums|FishCooking]], January 05, 2020 » [[Stockfish]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74793 Laziest Lazy SMP] by Ian Mitchell, [[CCC]], August 15, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75088 SMP, first shot at implementation] by [[Chris Whittington]], [[CCC]], September 12, 2020 » [[Thread]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75151 Very Lazy SMP and worker threads] by [[Chris Whittington]], [[CCC]], September 18, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=76190 Dispelling the Myth of NNUE with LazySMP: An Analysis] by [[Andrew Grant]], [[CCC]], December 30, 2020 » [[NNUE]] | ||
+ | ==2021 ...== | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79588 Stockfish search] by Werewolf, [[CCC]], March 26, 2022 » [[Stockfish]] | ||
=External Links= | =External Links= | ||
Line 125: | Line 136: | ||
* [https://en.wikipedia.org/wiki/Symmetric_multiprocessing Symmetric multiprocessing (SMP) from Wikipedia] | * [https://en.wikipedia.org/wiki/Symmetric_multiprocessing Symmetric multiprocessing (SMP) from Wikipedia] | ||
* [https://en.wikipedia.org/wiki/Lazy_evaluation Lazy evaluation from Wikipedia] | * [https://en.wikipedia.org/wiki/Lazy_evaluation Lazy evaluation from Wikipedia] | ||
− | * [[:Category:Small Faces|Small Faces]] - [https://en.wikipedia.org/wiki/Lazy_Sunday_(Small_Faces_song) Lazy Sunday | + | * [[:Category:Small Faces|Small Faces]] - [https://en.wikipedia.org/wiki/Lazy_Sunday_(Small_Faces_song) Lazy Sunday], [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
− | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=zXeRB-3nDR8|alignment=left|valignment=top}} |
=References= | =References= |
Latest revision as of 21:16, 28 March 2022
Home * Search * Parallel Search * Lazy SMP
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 αβ* [2]. 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 [3]. The term Lazy SMP was coined by Julien Marcel end of 2012 [4] with further elaborations by Daniel Homan [5] [6], 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 [7], not only in nodes per second (as expected), but in playing strength, while it seems worse than YBW in speedup concerning time to depth [8]. Notably Stockfish 7, released in January 2016, switched from YBW to lazy SMP [9] [10] [11].
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 searching
See also
- ABDADA
- Dynamic Tree Splitting
- Lazy SMP in EXchess
- Lazy Evaluation
- Shared Hash Table
- SMP
- NUMA
- Young Brothers Wait Concept
Selected Publications
- Vincent David (1993). Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, École nationale supérieure de l'aéronautique et de l'espace, Toulouse, France
- 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.
- Emil Fredrik Østensen (2016). A Complete Chess Engine Parallelized Using Lazy SMP. M.Sc. thesis, University of Oslo, pdf » Kholin
Forum Posts
2010 ...
- SMP speed up by Miguel A. Ballicora, CCC, September 14, 2010
- Lazy SMP by Julien Marcel, CCC, December 27, 2012
- Lazy SMP, part 2 by Daniel Homan, CCC, January 12, 2013
- Lazy SMP, part 3 by Daniel Homan, CCC, March 09, 2013
- Shared hash table smp result by Daniel Shawul, CCC, March 21, 2013
- ABDADA speedup results by Daniel Shawul, May 01, 2013 » ABDADA
- Measure of SMP scalability by Edsel Apostol, CCC, July 03, 2013
- Lazy SMP and Work Sharing by Daniel Homan, CCC, July 03, 2013 » Lazy SMP in EXchess
- cheng4 0.35 by Martin Sedlak, CCC, September 24, 2013 » Cheng
- SMP and pondering by John Merlino, CCC, February 08, 2014 » Myrddin, Pondering
- Nirvanachess 2.0 Release by Thomas Kolarik, CCC, December 17, 2014 » Nirvanachess
2015
- SMP: on same branch instead splitting? by Frank Ludwig, CCC, January 23, 2015
- Myrddin 0.87 release by John Merlino, CCC, January 25, 2015 » Myrddin
- A new chess engine : m8 (comming not so soon) by Mathieu Pagé, CCC, February 01, 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
- Lazy SMP in Cheng by Martin Sedlak, CCC, February 02, 2015 » Cheng
- Lazy SMP scaling Cheng0.38 by Bertil, FishCooking, February 24, 2015
- Trying to improve lazy smp by Daniel José Queraltó, CCC, April 11, 2015 » Andscacs
- Empirical results with Lazy SMP, YBWC, DTS by Kai Laskos, CCC, April 16, 2015 » Lazy SMP, YBWC, DTS
- lazy smp questions by Lucas Braesch, CCC, September 09, 2015
- Lazy SMP by Mikael, FishCooking, September 26, 2015 » Stockfish
- Komodo, Lazy SMP, and the like :-) by Stephane Nicolet, FishCooking, September 30, 2015 » Komodo, Stockfish
- Lazy SMP Better than YBWC? by Steve Maughan, CCC, October 23, 2015 » Young Brothers Wait Concept
- New Stockfish with Lazy_SMP, but what about the TC bug ? by Ernest Bonnem, CCC, October 26, 2015 » Stockfish, TCEC Season 8
- Helper Thread Depths in the Lazy SMP algorithm by Rohan Ryan, FishCooking, November 14, 2015 » Stockfish
- lazy smp questions by Marco Belli, CCC, December 21, 2015
2016
- Lazy SMP - how it works by Kalyankumar Ramaseshan, CCC, February 29, 2016
- Pedone 1.4 by Fabio Gobbato, CCC, April 03, 2016 » Pedone
- stockfish threading model by Folkert van Heusden, CCC, May 13, 2016
- Re: stockfish threading model by Dann Corbit, CCC, May 13, 2016
- parallel search speed measurement by Robert Hyatt, CCC, May 24, 2016
- Re: parallel search speed measurement by Kai Laskos, CCC, May 26, 2016
- Crazy SMP by Harm Geert Muller, CCC, June 19, 2016
- Re: Crazy SMP by Stan Arts, CCC, June 20, 2016
- lazy smp using ms vs2015 c++11 std::async by Edward Yu, CCC, July 29, 2016 » Thread [13]
- Time to depth concerns by Carl Bicknell, CCC, August 15, 2016
- Some hyperthreading results by Kai Laskos, CCC, September 12, 2016 » Thread, YBW
- Stockfish 8 - Double time control vs. 2 threads by Andreas Strangmüller, CCC, November 15, 2016 » Doubling TC, Diminishing Returns, Playing Strength, Stockfish
2017
- How to find SMP bugs ? by Lucas Braesch, CCC, March 15, 2017
- Ideas to improve SMP scaling by lucasart, OpenChess Forum, April 03, 2017
- Some data about LazySMP by Stephane Nicolet, FishCooking, April 08, 2017 » Stockfish
- Symmetric multiprocessing (SMP) scaling - SF8 and K10.4 by Andreas Strangmüller, CCC, May 05, 2017 » Komodo, Stockfish
- Symmetric multiprocessing (SMP) scaling - K10.4 Contempt=0 by Andreas Strangmüller, CCC, May 11, 2017 » SMP, Komodo, Contempt Factor
- Symmetric multiprocessing (SMP) scaling - SF8 Contempt=10 by Andreas Strangmüller, CCC, May 13, 2017 » SMP, Stockfish, Contempt Factor
- Lazy SMP and "lazy cluster" experiments by Peter Österlund, CCC, August 06, 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
- lazysmp (again) by Folkert van Heusden, CCC, August 09, 2017
- Lazy SMP >4 Thread Slowdown by Can Cetin, CCC, November 29, 2017 » Thread
- Re: Lazy SMP >4 Thread Slowdown by Ronald de Man, CCC, November 29, 2017
- Parallel search/LazySMP question by Jon Dart, CCC, December 17, 2017
2018
- Lazy SMP and 44 cores by Sander Maassen vd Brink, CCC, August 07, 2018
- Re: Lazy SMP and 44 cores by John Stanback, CCC, August 08, 2018 » Wasp
- Lazy SMP ideas by Edsel Apostol, CCC, August 22, 2018
- Lazy SMP ideas by Pawel Koziol, CCC, August 23, 2018
- Re: Lazy SMP ideas by Folkert van Heusden, CCC, October 03, 2018 » Aspiration Windows
2019
- Simplest way to implement quick and dirty lazy smp by Tom King, CCC, January 04, 2019
- What's the best Lazy SMP logic? by Daniel Bennett, CCC, January 06, 2019 » Stockfish
- strategies for finding slowdows in lazy smp by Folkert van Heusden, CCC, June 04, 2019 » Nodes per Second, Thread
- RMO - Randomized Move Order - yet another Lazy SMP derivate by Srdja Matovic, CCC, December 30, 2019
2020
- lazy smp behaviour of stockfish by Daniel Shawul, FishCooking, January 05, 2020 » Stockfish
- Laziest Lazy SMP by Ian Mitchell, CCC, August 15, 2020
- SMP, first shot at implementation by Chris Whittington, CCC, September 12, 2020 » Thread
- Very Lazy SMP and worker threads by Chris Whittington, CCC, September 18, 2020
- Dispelling the Myth of NNUE with LazySMP: An Analysis by Andrew Grant, CCC, December 30, 2020 » NNUE
2021 ...
- Stockfish search by Werewolf, CCC, March 26, 2022 » Stockfish
External Links
- lazy - Wiktionary
- Lazy from Wikipedia
- Laziness from Wikipedia
- Sloth (deadly sin) from Wikipedia
- Symmetric multiprocessing (SMP) from Wikipedia
- Lazy evaluation from Wikipedia
- Small Faces - Lazy Sunday, YouTube Video
References
- ↑ Three-toed sloth, Image by Friedrich Specht in Joseph Bassett Holder, John George Wood (1885). Our living world; an artistic edition of the Rev. J. G. Wood's Natural history of animate creation. New York : Selmar Hess, Wikimedia Commons
- ↑ Vincent David (1993). Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint. Etude et application au Minimax = Parallel algorithm for heuristic tree searching and real-time reasoning. Study and application to the Minimax, Ph.D. Thesis, École nationale supérieure de l'aéronautique et de l'espace, Toulouse, France
- ↑ Re: Lazy SMP - how it works by Evert Glebbeek, CCC, October 19, 2016
- ↑ Lazy SMP by Julien Marcel, CCC, December 27, 2012
- ↑ Lazy SMP, part 2 by Daniel Homan, CCC, January 12, 2013
- ↑ Lazy SMP and Work Sharing by Daniel Homan, CCC, July 03, 2013
- ↑ Re: A new chess engine : m8 (comming not so soon) by Peter Österlund, CCC, February 01, 2015
- ↑ Time to depth concerns by Carl Bicknell, CCC, August 15, 2016
- ↑ Stockfish 7 by Joona Kiiski, CCC, January 02, 2016
- ↑ Threads test incl. Stockfish 7 by Andreas Strangmüller, CCC, January 11, 2016
- ↑ Stockfish 7 progress by Carl Lumma, CCC, January 16, 2016
- ↑ Lazy SMP in Cheng by Martin Sedlak, CCC, February 02, 2015 » Cheng
- ↑ std::async - cppreference.com