Difference between revisions of "Lazy SMP"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 125: | Line 125: | ||
* [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=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=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]] | ||
=External Links= | =External Links= |
Revision as of 00:54, 31 December 2020
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
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