Difference between revisions of "Lazy SMP"

From Chessprogramming wiki
Jump to: navigation, search
(7 intermediate revisions by the same user not shown)
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 [[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>.   
+
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 37: Line 37:
 
* [[ABDADA]]
 
* [[ABDADA]]
 
* [[Dynamic Tree Splitting]]
 
* [[Dynamic Tree Splitting]]
* [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
+
* [[EXchess#LazySMP|Lazy SMP]] in [[EXchess]]
 
* [[Lazy Evaluation]]
 
* [[Lazy Evaluation]]
 
* [[Shared Hash Table]]
 
* [[Shared Hash Table]]
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 [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013
+
* [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 [[Dan Homan|Daniel Homan]], [[CCC]], March 09, 2013
+
* [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 [[Dan Homan|Daniel Homan]], [[CCC]], July 03, 2013 » [[EXchess#LazySMP|Lazy SMP]] in [[EXChess]]
+
* [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]]
Line 79: Line 79:
 
* [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 116: Line 116:
 
* [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]], [[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]]
  
 
=External Links=
 
=External Links=

Revision as of 22:40, 6 January 2020

Home * Search * Parallel Search * Lazy SMP

Sloths traversing a tree [1]

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].

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

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

2018

Re: Lazy SMP and 44 cores by John Stanback, CCC, August 08, 2018 » Wasp
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

2020

External Links

References

Up one level