Lazy SMP - how it works

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
krismchess
Posts: 24
Joined: Tue Oct 13, 2015 12:52 am

Lazy SMP - how it works

Post by krismchess » Mon Feb 29, 2016 1:15 am

I have searched internet on how this works, but there is no proper documentation available - not even on the chess wiki. Is there a paper/documentation where Lazy SMP is explained?

Thanks in advance.
--
Thanks,
Kalyan
Never Give UP!

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Lazy SMP - how it works

Post by kbhearn » Mon Feb 29, 2016 1:32 am

it's really really simple. exact implementation details vary. essentially all threads search on their own, only communicating via the hash table. some effort is usually done to get them out of sync earlier so they're doing different work like setting them to a variety of different depths to start.

And that's really all there is to it. What will or won't work in terms of details has to be tested, there is nothing to reason about because the search is so chaotic.

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Lazy SMP - how it works

Post by jdart » Mon Feb 29, 2016 2:11 am

It is similar to ABDADA, which was published a long time ago.

See https://chessprogramming.wikispaces.com ... Lazy%20SMP.

--Jon

krismchess
Posts: 24
Joined: Tue Oct 13, 2015 12:52 am

Re: Lazy SMP - how it works

Post by krismchess » Tue Oct 18, 2016 10:12 pm

jdart wrote:It is similar to ABDADA, which was published a long time ago.

See https://chessprogramming.wikispaces.com ... Lazy%20SMP.

--Jon
Then what could be the specific differences between ABDADA vs. Lazy SMP.

It's frustrating why CPW doesn't have a page explaining Lazy SMP yet.
--
Thanks,
Kalyan
Never Give UP!

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Lazy SMP - how it works

Post by Gerd Isenberg » Wed Oct 19, 2016 8:30 am

krismchess wrote:
jdart wrote:It is similar to ABDADA, which was published a long time ago.

See https://chessprogramming.wikispaces.com ... Lazy%20SMP.

--Jon
Then what could be the specific differences between ABDADA vs. Lazy SMP.

It's frustrating why CPW doesn't have a page explaining Lazy SMP yet.
I was too lazy so far to set up an own page ...

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Lazy SMP - how it works

Post by Evert » Wed Oct 19, 2016 8:39 am

krismchess wrote:
jdart wrote:It is similar to ABDADA, which was published a long time ago.

See https://chessprogramming.wikispaces.com ... Lazy%20SMP.

--Jon
Then what could be the specific differences between ABDADA vs. Lazy SMP.
I don't think there is any specific difference. Shared hash table SMP pretty much describes what it is. The main "new" idea that I suppose could be mentioned is that you launch threads on different iteration depths (instead of at the same depth). Statistically, that leads to less overhead than depending on random timing fluctuations to desynchronise the threads.
It's frustrating why CPW doesn't have a page explaining Lazy SMP yet.
Well, it's a wiki. Anyone who feels that there's more that needs to be said about it is free to add it...

flok

Re: Lazy SMP - how it works

Post by flok » Wed Oct 19, 2016 1:27 pm

Evert wrote:Shared hash table SMP pretty much describes what it is. The main "new" idea that I suppose could be mentioned is that you launch threads on different iteration depths (instead of at the same depth). Statistically, that leads to less overhead than depending on random timing fluctuations to desynchronise the threads.
I tried:
- each thread with different max-depth (it. deep. depth)
- each thread starting with a different move at the root
but sofar after, say 9 plies the threads start to run in lock-step.

So I think there's something else that must be done, right? Maybe this only works with non-locking TTs?

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Lazy SMP - how it works

Post by mar » Wed Oct 19, 2016 5:53 pm

flok wrote:Maybe this only works with non-locking TTs?
Locks are cheap unless there's contention :)
If you have x threads constantly fighting for a single lock then performance-wise can be order of magnitude slower than serial.

What you can try to remedy this is to use n locks (say 256) and index them via 8 lsbits of entry/bucket index.

You can also try to avoid locks completely, I use Bob's xor-trick but AFAIK some engines don't bother at all,
all you need is robust validation of TT move.

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Lazy SMP - how it works

Post by AlvaroBegue » Wed Oct 19, 2016 8:24 pm

One difference between ABDADA and lazy SMP is that in ABDADA the hash entry keeps track of how many threads are working on it. I forgot exactly how that information was used (I read the paper many years ago), but it somehow discourages other threads from going down the same path.

Post Reply