bob wrote: Yes the original "owner" has to be the one to back up at that node once it has been completed by either itself or "slaves". But that master can go off and work at other points in the tree also, and not sit around holding things up...
And when helpful master concept is used, the time master thread ends up being idle is so small that it is almost irrelevant. The real problem is the fact that sometimes split happens at node which fails high and then a lot of work is simply wasted. This is the only area where DTS can _possibly_ outperform YBW. Anyway the expected gain is so small that I'm not going to try this in Stockfish until most people have at least 16 core systems
This is not quite true. With current "crafty-like" YBW algorithms (and it seems everyone doing a real parallel search uses the same idea) a thread that notices idle threads stops and does some work to "invite them in." In DTS the opposite was done, at least in my implementation. The _idle_ threads simply collected state from everyone else and chose which to "join". And it could do the "join" without the "joinee" even realizing this had happened. That is an efficiency improvement since working threads don't do the splitting, the idle threads do.
1) "everyone doing a real parallel search"
I realized today that we are not doing a real parallel search
2) No, at least in SF. Joona made that post because we have just finishing testing a modification in how SMP code works. Namely when a thread finished its work instead of sitting idle waiting for some else thread to pick it up, does a look up across currenlty active split points and picks the best (the highest depth one) , then joins the group without other threads do stop the search. So it is very efficient. But after a deep test on a QUAD machine we got no ELO gain from this patch that we discarded because it was simply adding complexity for no gain.
In the amazing case you would like to _read_ the patch and not just comment on that we can post it.
A) You take yourselves way too seriously. Not _every_ comment someone makes is directed toward you.
B) as for the "amazing case" just keep your snotty attitude to yourself, I know enough about how to do an efficient parallel search without looking at other code...
bob wrote:
This is not a YBW issue, it is an implementation issue.
Ah, I see. I didn't know that there are implementations without this.
I use pure YBW in Crafty, And I don't have the issue you mentioned above at all. Yes the original "owner" has to be the one to back up at that node once it has been completed by either itself or "slaves". But that master can go off and work at other points in the tree also, and not sit around holding things up...
What happens when all slaves of split S are ready (all children searched) but the master is still busy with something else? Will it continue its task before it returns the result of S to its parent?
Simple. The search can split anywhere _below_ the lowest active split point. When the master is busy, any idle threads will join in to help it complete whatever it is working on, always at a deeper ply.
bob wrote:
B) as for the "amazing case" just keep your snotty attitude to yourself, I know enough about how to do an efficient parallel search without looking at other code...
Joona made a comment, you said he was wrong, I replied that we have tested some code that verify what Joona said, you are saying that you don't care because you already know everything.....who's the snotty one here ?
P.S: I already knew you had answered in that way (I don't know if this is snotty or not), you missed an occasion to surprise me. Please don't reply that you don't care to surprise me....otherwise you'd miss a second one
bob wrote:
B) as for the "amazing case" just keep your snotty attitude to yourself, I know enough about how to do an efficient parallel search without looking at other code...
Joona made a comment, you said he was wrong, I replied that we have tested some code that verify what Joona said, you are saying that you don't care because you already know everything.....who's the snotty one here ?
P.S: I already knew you had answered in that way (I don't know if this is snotty or not), you missed an occasion to surprise me. Please don't reply that you don't care to surprise me....otherwise you'd miss a second one
If you will simply reread what he wrote, and my follow up, I clearly said "this is not quite true" and explained _exactly_ why this is the case. As far as what you tested, I have no idea. I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.
BTW, when you say "know everything" let me ask you a couple of questions:
(1) Do you know who coined the term "Dynamic Tree Splitting"?
(2) Do you know who developed the algorithm?
(3) Do you know who used this algorithm first?
(4) Do you know who coined the acronym "DTS"?
(5) Do you know who designed and implemented this algorithm as their Ph.D. dissertation?
(6) Do you know who then wrote this up and published it in a short-form in the JICCA?
Hint: They all have the _same_ answer.
For the record, I _do_ know what DTS is all about. And YBW. And PVS (not the null-window search used by everyone but "Principle Variation Split" first used in the early 80's.) Etc.
I had my first parallel search working in 1978, for reference. One does learn by experience.
[quote="bob" I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.[/quote]
I have not been following the details closely, but I suspect this is the primary issue. Concluding something like this does not help in long games is so very hard without dedicating a lot of time and resources.
BubbaTough wrote:[quote="bob" I have tested my code, but it does require long games to test parallel search, as it gets better as the depth increases. How you tested this I don't know. It _does_ work. It might be 10%. It might be less. Depending on how effective your implementation is. 10% _does_ make a difference. Not a big one, and one that takes many games to measure. But it does help.
I have not been following the details closely, but I suspect this is the primary issue. Concluding something like this does not help in long games is so very hard without dedicating a lot of time and resources.
-Sam[/quote]
This has been documented previously, by more than one person doing this kind of research. The deeper you go, the better your parallel search can do, since that gives you more potential split points to choose from. More choices -> better decisions, done correctly.
As long as the discussion includes 1,000 game tests, this is not going anywhere positive. It takes more games than that to find a parallel search improvement, unless you compare non-parallel to parallel where the speedup can be a factor of 3+ for 4 cpus which will show up in fewer games. Tweaking parallel search often produces nothing in most cases, but helps in the endgame, or vice-versa. It is not always easy to measure.
