Peculiarity of Komodo 5.1MP

[syzygy]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

[Daniel Shawul]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

Like I said in my post, "The question of difficulty of implementation is irrelevant."

[syzygy]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

Like I said in my post, "The question of difficulty of implementation is irrelevant."

I said "prove that you can". This should be understood as "prove that it is possible". This is not evident, so there is a gap in your proof.

Btw, even if you could prove it, it would only show that Komodo's single-core search is suboptimal. It does not prove that Komodo's SMP implementation is suboptimal.

[Daniel Shawul]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

Like I said in my post, "The question of difficulty of implementation is irrelevant."

I said "prove that you can". This should be understood as "prove that it is possible".

I don't need to because my point is you can't have an optimal sequential search and a wide and optimal parallel search at the same time! You choose to go wider when you can't correctly implement going deeper with parallel search. You can't construct same argument for the deeper parallel search, try it.

[syzygy]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

Like I said in my post, "The question of difficulty of implementation is irrelevant."

I said "prove that you can". This should be understood as "prove that it is possible".

I don't need to because my point is you can't have an optimal sequential search and a wide and optimal parallel search at the same time! You choose to go wider when you can't correctly implement going deeper with parallel search. You can't construct same argument for the deeper parallel search, try it.

You were trying to construct a "proof", but there is big gap in it that apparently you don't care to repair. So there is no proof.

[Daniel Shawul]

Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does.

Prove that you can "change the algorithm" without loss of speed...

Like I said in my post, "The question of difficulty of implementation is irrelevant."

I said "prove that you can". This should be understood as "prove that it is possible".

I don't need to because my point is you can't have an optimal sequential search and a wide and optimal parallel search at the same time! You choose to go wider when you can't correctly implement going deeper with parallel search. You can't construct same argument for the deeper parallel search, try it.

You were trying to construct a "proof", but there is big gap in it that apparently you don't care to repair. So there is no proof.

I did you missed it. It assumes no implmentation difficulties.

[Daniel Shawul]

Btw, even if you could prove it, it would only show that Komodo's single-core search is suboptimal. It does not prove that Komodo's SMP implementation is suboptimal.

I missed this part of your post. Yes so Komodo should first improve its sequential sub-optimal search if that is the case. But I prefer the other explanation that its parallel search is less efficiently done than its sequential search , and that seems to be the case from Don's and other people's explanations.

[lkaufman]

I am quite sure that neither our parallel nor singe-core search is even close to optimal, just as I am sure this is true for every other engine now in existence. But you haven't convinced me that given an optimal single-core engine, the parallel search must just be faster, not wider. Why can't a wider search get a bigger speedup from parallelism?

[Daniel Shawul]

I am quite sure that neither our parallel nor singe-core search is even close to optimal, just as I am sure this is true for every other engine now in existence. But you haven't convinced me that given an optimal single-core engine, the parallel search must just be faster, not wider. Why can't a wider search get a bigger speedup from parallelism?

When I say optimal it doesn't mean searching the minimal tree but the best sequential search that you have now i.e. un-improvable with the current knowledge that you have (not absolutely un-improvable). Now if you get better search i.e. ELO by searching wider when doing parallel search, it means you can do the same for the sequential search as well. Parallel search is not much different from giving the engine more time. So that means for the sequential search, you can decide ,say to widen with time or something like that, for the same effect. I don't know how that can be implemented in a real engine but that is not my point. Better results with wide SMP=>Better results with wide SEQUENTIAL search given more time=> Sequential search improved if we know how to do it exactly like the parallel search does.
Don acknowledges that but he was arguing that 4 threads is not same as as 4x search, but i don't see how it would be different even if you use 3.6x time.

[Don]

Some have implied that we search wider because we don't get quite the same increase in depth and that this is a horrible thing. The intuition is that if that if it works you could do it on 1 thread too. However I do not think that follows. The problem is that 4 threads is just not 4x better than 1 thread no matter how good your MP implementation, so it always comes down to how to best utilize what you have. Anything goes in my opinion if it gets more out of extra cores in terms of ELO.

It doesn't matter if 4 threads is not as efficient as as 4x time search. The following statement is provable.
"If your sequential search is as good as it can be, then your parallel implementation that searches wider than sequential search is poorly done".
I will give it a shot as follows:
Assume sequential search is at its best. Give it 3.6x more time (say same as 4 threads search) but change the algorithm so that it can widen its search exactly the same way as the parallel search does. If indeed searching wider is better for parallel search as claimed, then the wide sequential search should show similar improvement over its deeper search counterpart. So we improved the sequential search that we assumed un-improvable, contradiction! The question of difficulty of implementation is irrelevant.

That was a good try but your proof logic is flawed. What is not considered is utilization of resources.

We know that that when when multiple cores try to cooperate to search a position you lose in 3 primary ways with chess programs: synchronization overhead, communication overhead and redundant calculations. If you can reduce 1 or more of those things and apply it to something else instead, you can get a gain that you would not have had otherwise - even if the gain itself would not ordinarily be the best way to utilize resources in a single core program. Your proof assumes that it's impossible for that to be the case.

In other words if you run out of constructive things to do with the extra cores - then you need to start exploiting things that may be less beneficial in ordinary circumstances but now we have new circumstances. In my "doctor" illustration you just wouldn't waste a doctors time in a hospital making phone calls or being a gopher, but in a specialized situation where there were more doctors than you could fully utilize you would start putting them to work on more mundane tasks.