Lazy SMP

Home * Search * Parallel Search * Lazy SMP

Sloths traversing a tree

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 αβ* . 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 . The term Lazy SMP was coined by Julien Marcel end of 2012 with further elaborations by Daniel Homan , 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 , not only in nodes per second (as expected), but in playing strength, while it seems worse than YBW in speedup concerning time to depth . Notably Stockfish 7, released in January 2016, switched from YBW to lazy SMP .

Cheng's Pseudo Code

Pseudo Code of Lazy SMP in Cheng as given by its author Martin Sedlak :

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
• 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

2021 ...

• Stockfish search by Werewolf, CCC, March 26, 2022 » 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, YouTube Video

References

Up one level