back to the Komodo SMP issue

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Henk
Posts: 5718
Joined: Mon May 27, 2013 8:31 am

Re: back to the Komodo SMP issue

Post by Henk » Fri Jul 05, 2013 7:54 am

Henk wrote:It may easily happen that while searching N times faster the perhaps small error in the value of the best move in the root is still too big.

This causes the better moves in the root to be rejected.

The player that makes the smallest errors in important positions wins the game.

All parameters that have any effect on basic evaluation or pruning should be 're-tuned'. Or basic evaluation should be rewritten. Or more accurate pruning methods should be invented and implemented.

Of course if it is only one parameter that causes the error bottleneck only that parameter needs to be changed.
If the algorithm is optimal, it might also be that not N times more nodes need the searched, but 100 times N times to overcome the error bottleneck. But this is perhaps theoretic non sense.

duncan
Posts: 9971
Joined: Mon Jul 07, 2008 8:50 pm

Re: back to the Komodo SMP issue

Post by duncan » Fri Jul 05, 2013 9:50 am

bob wrote: If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

duncan

Jesse Gersenson
Posts: 575
Joined: Sat Aug 20, 2011 7:43 am
Contact:

Re: back to the Komodo SMP issue

Post by Jesse Gersenson » Fri Jul 05, 2013 11:28 am

As a teenager my father gave me a summer-job on a house-building project he was orchestrating. There were three of us building the house. After a few days my old man asked me how it was going. "It's hard on my body and boring. A lot of times I don't know what I'm supposed to be doing," i told him.

He explained my job to me, "Well, I've got two guys who I'm paying $25/hr and you who I'm paying $10/hr. Your job is to do anything you can to make the $25/hr guys work faster."

FlavusSnow
Posts: 89
Joined: Thu Apr 01, 2010 3:28 am
Location: Omaha, NE

Re: back to the Komodo SMP issue

Post by FlavusSnow » Fri Jul 05, 2013 1:33 pm

It's a good question. I don't have the answer. In my pea-brain I conceptualize it as the engine being tuned to be too aggressive at pruning/reducing. For a single thread this means it needs higher depths before it exposes incorrect prunes/reductions, but on SMP some of the "search inefficiency" can fill the gaps sooner, and at lower depths.

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

Re: back to the Komodo SMP issue

Post by syzygy » Fri Jul 05, 2013 2:30 pm

duncan wrote:
bob wrote: If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.
Bob's argument is logically flawed in more than one way.

duncan
Posts: 9971
Joined: Mon Jul 07, 2008 8:50 pm

Re: back to the Komodo SMP issue

Post by duncan » Fri Jul 05, 2013 2:42 pm

syzygy wrote: Bob's argument is logically flawed in more than one way.
to avoid what bob will call handwaving perhaps you could spell it out or reference it if you have already done so, so bob can respond.

duncan

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

Re: back to the Komodo SMP issue

Post by bob » Fri Jul 05, 2013 3:45 pm

FlavusSnow wrote:It's a good question. I don't have the answer. In my pea-brain I conceptualize it as the engine being tuned to be too aggressive at pruning/reducing. For a single thread this means it needs higher depths before it exposes incorrect prunes/reductions, but on SMP some of the "search inefficiency" can fill the gaps sooner, and at lower depths.
It is not quite that easy. You can't redirect the "effort" within a parallel search. There are two distinct components of a parallel chess engine:

(1) the basic alpha/beta search, along with all the usual selectivity stuff like null-move, reductions, forward-pruning and such. You generally tune these so that they provide the max Elo on a single CPU box.

(2) the parallel search, which simply traverses the tree above, but in parallel to complete it faster (to the same depth). This introduces some overhead since move ordering is not perfect, yet alpha/beta depends on it being good. Unfortunately, a parallel search has to split the search at various points, and that DOES require perfect ordering, else you introduce search overhead in the form of extra nodes searched when you split at a CUT node.

To increase width, you just tighten up the reductions and pruning rules so that they are activated less frequently. This penalizes depth. Then you use a parallel search to hopefully gain that speed back through search efficiency.

I don't see the gain at the present, given a reasonable parallel search implementation that can produce a speedup > 3x for 4 cpus, unless the pruning rules are too liberal to begin with, and tightened up to increase the size of the tree. At the cost of search depth. And that would seem to be something that should work on the single cpu version equally well.

All this chatter about 128 cores and such is irrelevant when we are specifically talking about 4 cpu examples. Diminishing returns doesn't become a serious problem with just 4 cores.

At the moment, I seem to be missing the point...

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

Re: back to the Komodo SMP issue

Post by bob » Fri Jul 05, 2013 3:46 pm

duncan wrote:
bob wrote: If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.

duncan
How do you go for extra width at 100% efficiency? You STILL have to search that extra width in parallel, and the parallel search overhead doesn't go away. That is EXACTLY the issue I have been addressing.

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

Re: back to the Komodo SMP issue

Post by bob » Fri Jul 05, 2013 3:48 pm

syzygy wrote:
duncan wrote:
bob wrote: If it does scale well, additional depth almost certainly pays off more than increased width, else the serial search would go for the increased width as well...

there is something basic I do not understand.

if twice the time used searching additional depth in a single core gives 70 extra elo, but searching extra width gives 80% of that ie 56 elo.

then when using 2 cores which scales at 80% efficiency, you could either go for additional depth to get the 56 elo or extra width at 100% efficiency to get the 56 elo, which is why serial search does not go for the increased width but a parallel can without losing elo.
Bob's argument is logically flawed in more than one way.
And you have yet to point out a single one. Just hand-waving and such. Not one scintilla of technical discussion to address this issue. And yet you keep posting.

Whatever you do to the shape of the tree, you STILL have to run it through the parallel search and lose the overhead cost..

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

Re: back to the Komodo SMP issue

Post by bob » Fri Jul 05, 2013 3:48 pm

duncan wrote:
syzygy wrote: Bob's argument is logically flawed in more than one way.
to avoid what bob will call handwaving perhaps you could spell it out or reference it if you have already done so, so bob can respond.

duncan
Do NOT hold your breath...

Post Reply