25,161
edits
Changes
Created page with "'''Home * Search * Parallel Search * Lazy SMP''' FILE:Our living world (Full Page Illustration) (6076989366).jpg|border|right|thumb|Sloths traversing..."
'''[[Main Page|Home]] * [[Search]] * [[Parallel Search]] * Lazy SMP'''
[[FILE:Our living world (Full Page Illustration) (6076989366).jpg|border|right|thumb|Sloths traversing a tree <ref>[https://en.wikipedia.org/wiki/Three-toed_sloth Three-toed sloth], [https://commons.wikimedia.org/wiki/File:Our_living_world_(Full_Page_Illustration)_(6076989366).jpg?uselang=en Image] by [https://en.wikipedia.org/wiki/Friedrich_Specht Friedrich Specht] in [https://en.wikipedia.org/wiki/Joseph_Bassett_Holder Joseph Bassett Holder], [https://en.wikipedia.org/wiki/John_George_Wood John George Wood] ('''1885'''). ''[http://www.biodiversitylibrary.org/bibliography/49480#/summary Our living world; an artistic edition of the Rev. J. G. Wood's Natural history of animate creation]''. New York : Selmar Hess, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''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 [[Dan Homan|Daniel Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|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=
<span id="Cheng"></span>Pseudo Code of Lazy SMP in [[Cheng]] as given by its author [[Martin Sedlak]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]</ref>:
<pre>
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
</pre>
=See also=
* [[ABDADA]]
* [[Dynamic Tree Splitting]]
* [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
* [[Lazy Evaluation]]
* [[Shared Hash Table]]
* [[SMP]]
* [[NUMA]]
* [[Young Brothers Wait Concept]]
=Selected Publications=
* [[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]
: '''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, [https://en.wikipedia.org/wiki/University_of_Oslo University of Oslo], [https://www.duo.uio.no/bitstream/handle/10852/53769/master.pdf?sequence=1 pdf] » [[Kholin]]
=Forum Posts=
==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=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[Dan Homan|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=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=48536 Lazy SMP and Work Sharing] by [[Dan Homan|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=51198 SMP and pondering] by [[John Merlino]], [[CCC]], February 08, 2014 » [[Myrddin]], [[Pondering]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54671 Nirvanachess 2.0 Release] by [[Thomas Kolarik]], [[CCC]], December 17, 2014 » [[Nirvanachess]]
==2015==
* [http://www.talkchess.com/forum/viewtopic.php?t=55047 SMP: on same branch instead splitting?] by Frank Ludwig, [[CCC]], January 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55093 Myrddin 0.87 release] by [[John Merlino]], [[CCC]], January 25, 2015 » [[Myrddin]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55170 A new chess engine : m8 (comming not so soon)] by [[Mathieu Pagé]], [[CCC]], February 01, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=55170&start=3 Re: A new chess engine : m8 (comming not so soon)] by [[Martin Sedlak]], [[CCC]], February 01, 2015
: [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
* [http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]
* [https://groups.google.com/d/msg/fishcooking/VL4pEYZXuuM/wJSehP7SQlYJ Lazy SMP scaling Cheng0.38] by Bertil, [[Computer Chess Forums|FishCooking]], February 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55970 Trying to improve lazy smp] by [[Daniel José Queraltó]], [[CCC]], April 11, 2015 » [[Andscacs]]
* [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
* [https://groups.google.com/d/msg/fishcooking/GVdyWSWEpQY/bZbeaJAbBgAJ Lazy SMP] by Mikael, [[Computer Chess Forums|FishCooking]], September 26, 2015 » [[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=58056 New Stockfish with Lazy_SMP, but what about the TC bug ?] by [[Ernest Bonnem]], [[CCC]], October 26, 2015 » [[Stockfish]], [[TCEC Season 8]]
* [https://groups.google.com/d/msg/fishcooking/Sq8HJ7Xq0Ww/rKbWeHASBQAJ Helper Thread Depths in the Lazy SMP algorithm] by Rohan Ryan, [[Computer Chess Forums|FishCooking]], November 14, 2015 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015
==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=60155 stockfish threading model] by [[Folkert van Heusden]], [[CCC]], May 13, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60155&start=1 Re: stockfish threading model] by [[Dann Corbit]], [[CCC]], May 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60271 parallel search speed measurement] by [[Robert Hyatt]], [[CCC]], May 24, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60271&start=9 Re: parallel search speed measurement] by [[Kai Laskos]], [[CCC]], May 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60537 Crazy SMP] by [[Harm Geert Muller]], [[CCC]], June 19, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60537&start=2 Re: Crazy SMP] by [[Stan Arts]], [[CCC]], June 20, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60979 lazy smp using ms vs2015 c++11 std::async] by [[Edward Yu]], [[CCC]], July 29, 2016 » [[Thread]] <ref>[http://en.cppreference.com/w/cpp/thread/async std::async - cppreference.com]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=61131 Time to depth concerns] by [[Carl Bicknell]], [[CCC]], August 15, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61408 Some hyperthreading results] by [[Kai Laskos]], [[CCC]], September 12, 2016 » [[Thread]], [[Young Brothers Wait Concept|YBW]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62146 Stockfish 8 - Double time control vs. 2 threads] by [[Andreas Strangmüller]], [[CCC]], November 15, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Stockfish]]
==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.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=63967 Symmetric multiprocessing (SMP) scaling - SF8 Contempt=10] by [[Andreas Strangmüller]], [[CCC]], May 13, 2017 » [[SMP]], [[Stockfish]], [[Contempt Factor]]
* <span id="LazyCluster"></span>[http://www.talkchess.com/forum/viewtopic.php?t=64824 Lazy SMP and "lazy cluster" experiments] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=1 Lazy SMP and lazy cluster algorithm] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=2 SMP NPS measurements] by [[Peter Österlund]], [[CCC]], August 06, 2017 » [[Nodes per second]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=3 ELO measurements] by [[Peter Österlund]], [[CCC]], August 06, 2017 » [[Playing Strength]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=4 Possible improvements] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=43 Approximate ABDADA] by [[Peter Österlund]], [[CCC]], August 23, 2017 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64850 lazysmp (again)] by [[Folkert van Heusden]], [[CCC]], August 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65844 Lazy SMP >4 Thread Slowdown] by [[Can Cetin]], [[CCC]], November 29, 2017 » [[Thread]]
: [http://www.talkchess.com/forum/viewtopic.php?t=65844&start=4 Re: Lazy SMP >4 Thread Slowdown] by [[Ronald de Man]], [[CCC]], November 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66044 Parallel search/LazySMP question] by [[Jon Dart]], [[CCC]], December 17, 2017
=External Links=
* [https://en.wiktionary.org/wiki/lazy lazy - Wiktionary]
* [https://en.wikipedia.org/wiki/Lazy Lazy from Wikipedia]
* [https://en.wikipedia.org/wiki/Laziness Laziness from Wikipedia]
* [https://en.wikipedia.org/wiki/Sloth_(deadly_sin) Sloth (deadly sin) 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]
* [[Videos#SmallFaces|Small Faces]] - [https://en.wikipedia.org/wiki/Lazy_Sunday_(Small_Faces_song) Lazy Sunday], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club], [http://www.tv.com/shows/beat-club/show-32-june-22-1968-196634/ June 22, 1968], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=wpqjE7Qvpvs|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
[[FILE:Our living world (Full Page Illustration) (6076989366).jpg|border|right|thumb|Sloths traversing a tree <ref>[https://en.wikipedia.org/wiki/Three-toed_sloth Three-toed sloth], [https://commons.wikimedia.org/wiki/File:Our_living_world_(Full_Page_Illustration)_(6076989366).jpg?uselang=en Image] by [https://en.wikipedia.org/wiki/Friedrich_Specht Friedrich Specht] in [https://en.wikipedia.org/wiki/Joseph_Bassett_Holder Joseph Bassett Holder], [https://en.wikipedia.org/wiki/John_George_Wood John George Wood] ('''1885'''). ''[http://www.biodiversitylibrary.org/bibliography/49480#/summary Our living world; an artistic edition of the Rev. J. G. Wood's Natural history of animate creation]''. New York : Selmar Hess, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''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 [[Dan Homan|Daniel Homan]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|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=
<span id="Cheng"></span>Pseudo Code of Lazy SMP in [[Cheng]] as given by its author [[Martin Sedlak]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]</ref>:
<pre>
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
</pre>
=See also=
* [[ABDADA]]
* [[Dynamic Tree Splitting]]
* [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
* [[Lazy Evaluation]]
* [[Shared Hash Table]]
* [[SMP]]
* [[NUMA]]
* [[Young Brothers Wait Concept]]
=Selected Publications=
* [[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]
: '''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, [https://en.wikipedia.org/wiki/University_of_Oslo University of Oslo], [https://www.duo.uio.no/bitstream/handle/10852/53769/master.pdf?sequence=1 pdf] » [[Kholin]]
=Forum Posts=
==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=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47455 Lazy SMP, part 3] by [[Dan Homan|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=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=48536 Lazy SMP and Work Sharing] by [[Dan Homan|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=51198 SMP and pondering] by [[John Merlino]], [[CCC]], February 08, 2014 » [[Myrddin]], [[Pondering]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54671 Nirvanachess 2.0 Release] by [[Thomas Kolarik]], [[CCC]], December 17, 2014 » [[Nirvanachess]]
==2015==
* [http://www.talkchess.com/forum/viewtopic.php?t=55047 SMP: on same branch instead splitting?] by Frank Ludwig, [[CCC]], January 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55093 Myrddin 0.87 release] by [[John Merlino]], [[CCC]], January 25, 2015 » [[Myrddin]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55170 A new chess engine : m8 (comming not so soon)] by [[Mathieu Pagé]], [[CCC]], February 01, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=55170&start=3 Re: A new chess engine : m8 (comming not so soon)] by [[Martin Sedlak]], [[CCC]], February 01, 2015
: [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
* [http://www.talkchess.com/forum/viewtopic.php?t=55188 Lazy SMP in Cheng] by [[Martin Sedlak]], [[CCC]], February 02, 2015 » [[Cheng]]
* [https://groups.google.com/d/msg/fishcooking/VL4pEYZXuuM/wJSehP7SQlYJ Lazy SMP scaling Cheng0.38] by Bertil, [[Computer Chess Forums|FishCooking]], February 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55970 Trying to improve lazy smp] by [[Daniel José Queraltó]], [[CCC]], April 11, 2015 » [[Andscacs]]
* [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
* [https://groups.google.com/d/msg/fishcooking/GVdyWSWEpQY/bZbeaJAbBgAJ Lazy SMP] by Mikael, [[Computer Chess Forums|FishCooking]], September 26, 2015 » [[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=58056 New Stockfish with Lazy_SMP, but what about the TC bug ?] by [[Ernest Bonnem]], [[CCC]], October 26, 2015 » [[Stockfish]], [[TCEC Season 8]]
* [https://groups.google.com/d/msg/fishcooking/Sq8HJ7Xq0Ww/rKbWeHASBQAJ Helper Thread Depths in the Lazy SMP algorithm] by Rohan Ryan, [[Computer Chess Forums|FishCooking]], November 14, 2015 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58645 lazy smp questions] by [[Marco Belli]], [[CCC]], December 21, 2015
==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=60155 stockfish threading model] by [[Folkert van Heusden]], [[CCC]], May 13, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60155&start=1 Re: stockfish threading model] by [[Dann Corbit]], [[CCC]], May 13, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60271 parallel search speed measurement] by [[Robert Hyatt]], [[CCC]], May 24, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60271&start=9 Re: parallel search speed measurement] by [[Kai Laskos]], [[CCC]], May 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60537 Crazy SMP] by [[Harm Geert Muller]], [[CCC]], June 19, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60537&start=2 Re: Crazy SMP] by [[Stan Arts]], [[CCC]], June 20, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60979 lazy smp using ms vs2015 c++11 std::async] by [[Edward Yu]], [[CCC]], July 29, 2016 » [[Thread]] <ref>[http://en.cppreference.com/w/cpp/thread/async std::async - cppreference.com]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=61131 Time to depth concerns] by [[Carl Bicknell]], [[CCC]], August 15, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61408 Some hyperthreading results] by [[Kai Laskos]], [[CCC]], September 12, 2016 » [[Thread]], [[Young Brothers Wait Concept|YBW]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62146 Stockfish 8 - Double time control vs. 2 threads] by [[Andreas Strangmüller]], [[CCC]], November 15, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Stockfish]]
==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.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=63967 Symmetric multiprocessing (SMP) scaling - SF8 Contempt=10] by [[Andreas Strangmüller]], [[CCC]], May 13, 2017 » [[SMP]], [[Stockfish]], [[Contempt Factor]]
* <span id="LazyCluster"></span>[http://www.talkchess.com/forum/viewtopic.php?t=64824 Lazy SMP and "lazy cluster" experiments] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=1 Lazy SMP and lazy cluster algorithm] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=2 SMP NPS measurements] by [[Peter Österlund]], [[CCC]], August 06, 2017 » [[Nodes per second]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=3 ELO measurements] by [[Peter Österlund]], [[CCC]], August 06, 2017 » [[Playing Strength]]
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=4 Possible improvements] by [[Peter Österlund]], [[CCC]], August 06, 2017
: [http://www.talkchess.com/forum/viewtopic.php?t=64824&start=43 Approximate ABDADA] by [[Peter Österlund]], [[CCC]], August 23, 2017 » [[ABDADA]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64850 lazysmp (again)] by [[Folkert van Heusden]], [[CCC]], August 09, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65844 Lazy SMP >4 Thread Slowdown] by [[Can Cetin]], [[CCC]], November 29, 2017 » [[Thread]]
: [http://www.talkchess.com/forum/viewtopic.php?t=65844&start=4 Re: Lazy SMP >4 Thread Slowdown] by [[Ronald de Man]], [[CCC]], November 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66044 Parallel search/LazySMP question] by [[Jon Dart]], [[CCC]], December 17, 2017
=External Links=
* [https://en.wiktionary.org/wiki/lazy lazy - Wiktionary]
* [https://en.wikipedia.org/wiki/Lazy Lazy from Wikipedia]
* [https://en.wikipedia.org/wiki/Laziness Laziness from Wikipedia]
* [https://en.wikipedia.org/wiki/Sloth_(deadly_sin) Sloth (deadly sin) 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]
* [[Videos#SmallFaces|Small Faces]] - [https://en.wikipedia.org/wiki/Lazy_Sunday_(Small_Faces_song) Lazy Sunday], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club], [http://www.tv.com/shows/beat-club/show-32-june-22-1968-196634/ June 22, 1968], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=wpqjE7Qvpvs|alignment=left|valignment=top}}
=References=
<references />
'''[[Parallel Search|Up one level]]'''
