Lazy_SMP - peregrineshahin/ChessProgrammingWiki GitHub Wiki

title: Lazy SMP

Home * Search * Parallel Search * Lazy SMP

[_(6076989366).jpg) 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].

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

2021 ...

External Links

References

  1. ↑ 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
  2. ↑ 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
  3. ↑ Re: Lazy SMP - how it works by Evert Glebbeek, CCC, October 19, 2016
  4. ↑ Lazy SMP by Julien Marcel, CCC, December 27, 2012
  5. ↑ Lazy SMP, part 2 by Daniel Homan, CCC, January 12, 2013
  6. ↑ Lazy SMP and Work Sharing by Daniel Homan, CCC, July 03, 2013
  7. ↑ Re: A new chess engine : m8 (comming not so soon) by Peter Österlund, CCC, February 01, 2015
  8. ↑ Time to depth concerns by Carl Bicknell, CCC, August 15, 2016
  9. ↑ Stockfish 7 by Joona Kiiski, CCC, January 02, 2016
  10. ↑ Threads test incl. Stockfish 7 by Andreas Strangmüller, CCC, January 11, 2016
  11. ↑ Stockfish 7 progress by Carl Lumma, CCC, January 16, 2016
  12. ↑ Lazy SMP in Cheng by Martin Sedlak, CCC, February 02, 2015 » Cheng
  13. ↑ std::async - cppreference.com

Up one level