Measure of SMP scalability (sub-thread)

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.
ernest
Posts: 1860
Joined: Wed Mar 08, 2006 7:30 pm

Measure of SMP scalability (sub-thread)

Post by ernest » Mon Jul 08, 2013 1:12 am

syzygy wrote:
bob wrote:The "widening" was caused by a bug, as reported by the author.
I do agree this discussion is surreal.
Not so sure...
If only "the author" Don (or Larry) could comment!

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Measure of SMP scalability

Post by syzygy » Mon Jul 08, 2013 1:18 am

ernest wrote:
syzygy wrote:
bob wrote:The "widening" was caused by a bug, as reported by the author.
I do agree this discussion is surreal.
Not so sure...
If only "the author" Don (or Larry) could comment!
This subthread is about Kai's (real) measurements on Hannibal's smp implementation. The smp implementation has a bug, but the measurements are real. (And my "surreal" was directed at something else than what you're quoting here.)

From Don's comments it seems that Komodo's "widening" is intentional. Whether that means that the widening could easily be avoided in return for better time-to-reported-depth, we do not know.

In my view there are 3 possibilties:
1. the "widening" is an artifact of the particular smp implementation of Komodo and cannot easily be avoided so just has to be accepted;
2. the "widening" is an intentional choice and the choice was made because it was measured to be better; or
3. this is just the state of Komodo's smp implementation at the time of release and a next release might "fix" the bug if that gives Elo improvement.

For Hannibal it is option 3. For Komodo I really do not know, but it might be 1.

I note again that whether it is 1, 2 or 3, there is nothing to "criticise". What counts is the engine's strength when using various numbers of cores, and this all seems fine for Komodo based on what I have read. Another question is whether there is something to "learn" for other engines. That is something I cannot answer, since I don't know what Komodo is doing and why.

Note that "widening" is defined here as "higher quality search when searching to the same depth using more cores".

ernest
Posts: 1860
Joined: Wed Mar 08, 2006 7:30 pm

Re: Measure of SMP scalability

Post by ernest » Mon Jul 08, 2013 2:01 am

syzygy wrote:This subthread is about Kai's (real) measurements on Hannibal's smp implementation.
Yes I know! 8-)
syzygy wrote:3. this is just the state of Komodo's smp implementation at the time of release and a next release might "fix" the bug if that gives Elo improvement.
So this has nothing to do with the corrected bug between 5.1 and 5.1r1 ?...

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Measure of SMP scalability

Post by syzygy » Mon Jul 08, 2013 8:09 am

ernest wrote:
syzygy wrote:This subthread is about Kai's (real) measurements on Hannibal's smp implementation.
Yes I know! 8-)
syzygy wrote:3. this is just the state of Komodo's smp implementation at the time of release and a next release might "fix" the bug if that gives Elo improvement.
So this has nothing to do with the corrected bug between 5.1 and 5.1r1 ?...
I don't know what was fixed, but I am pretty sure the bug fix did not bring significant changes.

User avatar
JuLieN
Posts: 2948
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Measure of SMP scalability

Post by JuLieN » Mon Jul 08, 2013 10:35 am

[moderation]
Branch of the discussion salvaged from the tree pruning.
"The only good bug is a dead bug." (Don Dailey)
Image [Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Measure of SMP scalability

Post by bob » Mon Jul 08, 2013 6:31 pm

syzygy wrote:
ernest wrote:
syzygy wrote:This subthread is about Kai's (real) measurements on Hannibal's smp implementation.
Yes I know! 8-)
syzygy wrote:3. this is just the state of Komodo's smp implementation at the time of release and a next release might "fix" the bug if that gives Elo improvement.
So this has nothing to do with the corrected bug between 5.1 and 5.1r1 ?...
I don't know what was fixed, but I am pretty sure the bug fix did not bring significant changes.
I am usually "Pretty sure" every new change I make is better. "pretty sure" turns out to be far from "reality" sometimes...

ernest
Posts: 1860
Joined: Wed Mar 08, 2006 7:30 pm

Re: Measure of SMP scalability

Post by ernest » Wed Jul 10, 2013 3:58 pm

syzygy wrote:Note that "widening" is defined here as "higher quality search when searching to the same depth using more cores".
Hi Ron,

Somebody (Fulcrum2000) in the Rybka Forum remembered a short 2009 discussion on the subject, which included Vasik Rajlich:
http://rybkaforum.net/cgi-bin/rybkaforu ... pid=158448

Adam Hair
Posts: 3201
Joined: Wed May 06, 2009 8:31 pm
Location: Fuquay-Varina, North Carolina

Re: Measure of SMP scalability

Post by Adam Hair » Wed Jul 10, 2013 5:18 pm

ernest wrote:
syzygy wrote:Note that "widening" is defined here as "higher quality search when searching to the same depth using more cores".
Hi Ron,

Somebody (Fulcrum2000) in the Rybka Forum remembered a short 2009 discussion on the subject, which included Vasik Rajlich:
http://rybkaforum.net/cgi-bin/rybkaforu ... pid=158448
There is also relevant content in this Rybka forum thread:

http://www.rybkaforum.net/cgi-bin/rybka ... l?tid=3836

User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Measure of SMP scalability

Post by Laskos » Wed Jul 10, 2013 6:02 pm

Adam Hair wrote:
ernest wrote:
syzygy wrote:Note that "widening" is defined here as "higher quality search when searching to the same depth using more cores".
Hi Ron,

Somebody (Fulcrum2000) in the Rybka Forum remembered a short 2009 discussion on the subject, which included Vasik Rajlich:
http://rybkaforum.net/cgi-bin/rybkaforu ... pid=158448
There is also relevant content in this Rybka forum thread:

http://www.rybkaforum.net/cgi-bin/rybka ... l?tid=3836
Thanks for the thread, it gives some real life numbers which agree remarkably well with Komodo numbers. I measured Komodo effective speedup, and it is as following
1->2 1.75
1->4 2.85
Then I measured widening at fixed depth from 32 to 64 threads (it's doable on 4 core machine), and found a factor of 1.14. If contribution from widening is comparable to that of deepening in the total speedup, as it happens in 4 threaded case, the total effective speedup from 32 to 64 cores is 1.3 for Komodo.

I fitted these data into the the formula for effective speedup a*log(b*n + c), where n is the number of cores (threads). This formula deviates from Amdahl's a*n/(b + c*n), and is a form of Gustafson's law, which is applicable to both Komodo and Rybka. The fitting for Komodo gave:

Effective speedup =3.61831*log(0.303485*n + 1.01489)

From 1 to 16 cores it looks like that:

Image

From 1 to 64 cores it is:

Image

Probably similar curves can be drawn for other engines, the main point being that the gain from number of threads is logarithmic.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Measure of SMP scalability

Post by syzygy » Wed Jul 10, 2013 6:56 pm

Adam Hair wrote:
ernest wrote:
syzygy wrote:Note that "widening" is defined here as "higher quality search when searching to the same depth using more cores".
Hi Ron,

Somebody (Fulcrum2000) in the Rybka Forum remembered a short 2009 discussion on the subject, which included Vasik Rajlich:
http://rybkaforum.net/cgi-bin/rybkaforu ... pid=158448
There is also relevant content in this Rybka forum thread:

http://www.rybkaforum.net/cgi-bin/rybka ... l?tid=3836
These are nice threads that confirm much of what was discussed before (but with less noise).

It seems the main reason Rybka thickens the tree is that it is difficult or impossible to take the same reduction / pruning decisions. This could refer to split nodes, but it might also have to do with branches being searched with somewhat worse bounds and the reductions being dependent on those bounds.
Vasik Rajlich on 2008-04-28 wrote:When I use the word "speedup", I mean "effective speedup". By itself, a time-to-depth speedup is pointless.

Post Reply