Difference between revisions of "Lazy SMP"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 4: | Line 4: | ||
'''Lazy SMP''',<br/> | '''Lazy SMP''',<br/> | ||
− | based on the [[Shared Hash Table|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|Vincent David's]] αβ* <ref> [[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 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, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]</ref>. Multiple [[Process|processes]] or [[Thread|threads]] search the same [[Root|root position]], but are launched with different [[Depth|depths]], and/or varying [[Move Ordering|move ordering]] at the root node, to statistically improve the gains from the effect of nondeterminism, otherwise depending on random timing fluctuations <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59389&start=5 Re: Lazy SMP - how it works] by [[Evert Glebbeek]], [[CCC]], October 19, 2016</ref>. The term '''Lazy SMP''' was coined by [[Julien Marcel]] end of 2012 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012</ref> with further elaborations by [[ | + | based on the [[Shared Hash Table|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|Vincent David's]] αβ* <ref> [[Vincent David]] ('''1993'''). ''[http://cat.inist.fr/?aModele=afficheN&cpsidt=161774 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, [https://en.wikipedia.org/wiki/%C3%89cole_nationale_sup%C3%A9rieure_de_l%27a%C3%A9ronautique_et_de_l%27espace École nationale supérieure de l'aéronautique et de l'espace], [https://en.wikipedia.org/wiki/Toulouse Toulouse], [https://en.wikipedia.org/wiki/France France]</ref>. Multiple [[Process|processes]] or [[Thread|threads]] search the same [[Root|root position]], but are launched with different [[Depth|depths]], and/or varying [[Move Ordering|move ordering]] at the root node, to statistically improve the gains from the effect of nondeterminism, otherwise depending on random timing fluctuations <ref>[http://www.talkchess.com/forum/viewtopic.php?t=59389&start=5 Re: Lazy SMP - how it works] by [[Evert Glebbeek]], [[CCC]], October 19, 2016</ref>. The term '''Lazy SMP''' was coined by [[Julien Marcel]] end of 2012 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012</ref> with further elaborations by [[Daniel Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Daniel Homan]], [[CCC]], January 12, 2013</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Daniel Homan]], [[CCC]], July 03, 2013</ref>, [[Martin Sedlak]] and others. Today, many chess programs use this easy to implement parallel search approach, which [https://en.wikipedia.org/wiki/Scalability scales] surprisingly well up to 8 cores and beyond <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55170&start=11 Re: A new chess engine : m8 (comming not so soon)] by [[Peter Österlund]], [[CCC]], February 01, 2015</ref>, not only in [[Nodes per Second|nodes per second]] (as expected), but in [[Playing Strength|playing strength]], while it seems worse than [[Young Brothers Wait Concept|YBW]] in [https://en.wikipedia.org/wiki/Speedup speedup] concerning time to [[Depth|depth]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=61131 Time to depth concerns] by [[Carl Bicknell]], [[CCC]], August 15, 2016</ref>. Notably [[Stockfish|Stockfish 7]], released in January 2016, switched from YBW to lazy SMP <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58779 Stockfish 7] by [[Joona Kiiski]], [[CCC]], January 02, 2016</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58887 Threads test incl. Stockfish 7] by [[Andreas Strangmüller]], [[CCC]], January 11, 2016</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58935 Stockfish 7 progress] by Carl Lumma, [[CCC]], January 16, 2016</ref>. |
=Cheng's Pseudo Code= | =Cheng's Pseudo Code= | ||
Line 53: | Line 53: | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=36082 SMP speed up] by [[Miguel A. Ballicora]], [[CCC]], September 14, 2010 | * [http://www.talkchess.com/forum/viewtopic.php?t=36082 SMP speed up] by [[Miguel A. Ballicora]], [[CCC]], September 14, 2010 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012 | * [http://www.talkchess.com/forum/viewtopic.php?t=46597 Lazy SMP] by [[Julien Marcel]], [[CCC]], December 27, 2012 | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[ | + | * [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Daniel Homan]], [[CCC]], January 12, 2013 |
− | * [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[ | + | * [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[Daniel Homan]], [[CCC]], March 09, 2013 |
* [http://www.talkchess.com/forum/viewtopic.php?t=47568 Shared hash table smp result] by [[Daniel Shawul]], [[CCC]], March 21, 2013 | * [http://www.talkchess.com/forum/viewtopic.php?t=47568 Shared hash table smp result] by [[Daniel Shawul]], [[CCC]], March 21, 2013 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], May 01, 2013 » [[ABDADA]] | * [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], May 01, 2013 » [[ABDADA]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=48524 Measure of SMP scalability] by [[Edsel Apostol]], [[CCC]], July 03, 2013 | * [http://www.talkchess.com/forum/viewtopic.php?t=48524 Measure of SMP scalability] by [[Edsel Apostol]], [[CCC]], July 03, 2013 | ||
− | * [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[ | + | * [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Daniel Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]] |
* [http://www.talkchess.com/forum/viewtopic.php?t=49443 cheng4 0.35] by [[Martin Sedlak]], [[CCC]], September 24, 2013 » [[Cheng]] | * [http://www.talkchess.com/forum/viewtopic.php?t=49443 cheng4 0.35] by [[Martin Sedlak]], [[CCC]], September 24, 2013 » [[Cheng]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=51198 SMP and pondering] by [[John Merlino]], [[CCC]], February 08, 2014 » [[Myrddin]], [[Pondering]] | * [http://www.talkchess.com/forum/viewtopic.php?t=51198 SMP and pondering] by [[John Merlino]], [[CCC]], February 08, 2014 » [[Myrddin]], [[Pondering]] |
Revision as of 15:04, 22 January 2019
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
- 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
- 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
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, Beat-Club, June 22, 1968, 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