Lazy SMP

From Chessprogramming wiki
Jump to: navigation, search

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

2021 ...

External Links

References

Up one level