An interesting parallel search non-bug
Posted: Thu Nov 05, 2015 3:10 am
The current rewrite of Crafty's parallel search is performing amazingly well. But as I tweak and tune, I inserted a test in the "Join()" code to sanity-test things, and one of the tests was "am I joining with myself?" Thought it should never happen, but I was wrong, majorly wrong.
An explanation:
Assume a 30 ply search and ignore extensions and reductions. At ply=10 thread 0 decides to do a "gratuitous split". That is a split that is done preemptively so that when other threads become idle, they can join here without me doing any additional work. Now we have a split point at ply=10 (owned by thread 0) that is flagged as joinable.
Assume we get to ply 20 and a thread becomes idle. First thing it does is try to join the best current joinable split point. The above split point is not the best so it isn't selected, another one is. But by the time we discover which one is best, it has evaporated because other threads have already completed it. Before setting the split flag, which tells other threads to do a split a.s.a.p., I loop back through the split blocks again, to try a second pass to find a good split point. I find it but again it evaporates before that thread can join. I try one more time, and the same thing happens again. So now, in thread 0, I do a real split at ply=20 and thread 1 joins with me there. We both search and I happen to finish first and have to wait for thread 1 to finish. So thread 0 goes to Join() and guess what it finds. Its own split point at ply 10. So it joins, searches, and all is well.
I have added a simple test to avoid this, because even though it works perfectly at the present time, it seems like a bad idea and a potential bug waiting to happen if I change something later that having the same thread at the same split point twice might break. But it certainly made my head spin for a bit. Finding it was an interesting issue. Then discovering that it is perfectly safe in the current code was a second surprise. I decided that I didn't want a third, which would not occur until some future change breaks this...
Does show the outstanding flexibility of the old DTS algorithm compared to what I am doing now, because with DTS there was no need for any gratuitous splits at all, a thread can split with another thread no matter where it currently is in the tree, and it can choose any ply to split at that it wants, because it has no recursive stack to preserve and unwind. The more I look, the more tempted I am to go back and write an iterated version to get the many advantages of DTS over the current YBW approach, even though the current code is certainly much easier to understand and modify.
An explanation:
Assume a 30 ply search and ignore extensions and reductions. At ply=10 thread 0 decides to do a "gratuitous split". That is a split that is done preemptively so that when other threads become idle, they can join here without me doing any additional work. Now we have a split point at ply=10 (owned by thread 0) that is flagged as joinable.
Assume we get to ply 20 and a thread becomes idle. First thing it does is try to join the best current joinable split point. The above split point is not the best so it isn't selected, another one is. But by the time we discover which one is best, it has evaporated because other threads have already completed it. Before setting the split flag, which tells other threads to do a split a.s.a.p., I loop back through the split blocks again, to try a second pass to find a good split point. I find it but again it evaporates before that thread can join. I try one more time, and the same thing happens again. So now, in thread 0, I do a real split at ply=20 and thread 1 joins with me there. We both search and I happen to finish first and have to wait for thread 1 to finish. So thread 0 goes to Join() and guess what it finds. Its own split point at ply 10. So it joins, searches, and all is well.
I have added a simple test to avoid this, because even though it works perfectly at the present time, it seems like a bad idea and a potential bug waiting to happen if I change something later that having the same thread at the same split point twice might break. But it certainly made my head spin for a bit. Finding it was an interesting issue. Then discovering that it is perfectly safe in the current code was a second surprise. I decided that I didn't want a third, which would not occur until some future change breaks this...
Does show the outstanding flexibility of the old DTS algorithm compared to what I am doing now, because with DTS there was no need for any gratuitous splits at all, a thread can split with another thread no matter where it currently is in the tree, and it can choose any ply to split at that it wants, because it has no recursive stack to preserve and unwind. The more I look, the more tempted I am to go back and write an iterated version to get the many advantages of DTS over the current YBW approach, even though the current code is certainly much easier to understand and modify.