5 ms·

I know exactly how much divergence there is because I'm the author of a chess engine and I've spent weeks/months looking at traces of my engine's tree searches.

by mot524 7y ago

I know exactly how much divergence there is because I'm the author of a chess engine and I've spent weeks/months looking at traces of my engine's tree searches. I think what you're not getting is what a chess engine search tree looks like. You're thinking it has nice layers of nodes, but really, most of the time, the engine is in the quiescence search, searching sequences of captures. The branching factor is extremely low and each branch terminates at an unpredictable depth. Instead of nice layers of nodes, imagine a lightning bolt that's constantly changing. You can't predict what you're going to have to do next. GPUs would excel if you have to do the same thing to different boards all at the same time. But that's never what happens. Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time? Okay, a GPU can make two moves at the same time and evaluate the resulting positions simultaneously no problem. Maybe one evaluation causes the branch to terminate and then that thread needs to undo the move, whereas the other branch needs to keep going and generate and search subsequent moves. This sort of divergence is the norm, not the exception, and it's impossible to handle in any sort of efficient way with a GPU. It's great that people have made GPU software to visit all possible positions to depth N, and it's great that somebody is making a MCTS engine run on a GPU. Both are tricky to do, and significant accomplishments if they work correctly. But in terms of making an effective engine these are just the absolute first initial baby steps and they don't signify anything about the viability of the rest of the project.

dragontamer 7y ago
I appreciate the discussion. > most of the time, the engine is in the quiescence search That seems to be the best case for GPUs. Whenever a GPU SIMD thread finishes a quiescence search, just grab another position that is under quiescence search. Frankly, the quiescence search part seems most ideally suited to GPUs out of all, as long as it is appropriate batched. > Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time. Put them onto the q-search queue, which will be checked as GPU threads go idle. The q-search problem is exactly identical to raytracers. GPUs don't know if a ray will bounce zero, once, or even 10 times. But that doesn't cause divergence because it's just about sticking rays onto a queue and evaluating them Rays in raytracers can even spawn multiple rays in a bounce, such as subsurface scattering. This pattern is solved!
- mot524 7y ago
  Like I've been saying, you don't know what you want to q-search next until you've finished the last q-search. So you can't make a q-search queue because you couldn't add anything to the queue until the previous addition was evaluated. I feel like I've said this a few times but for some reason you're not getting it, not really sure what the hangup is? Alpha-beta in general is so sequential that basically all the algorithms to parallelize it focus on making each thread as independent and sequential as possible. For example, the PV-split algorithm (which generalizes into Young Brothers Wait) splits the tree as low as possible (eventually to the root node) so that all threads can act as independently as possible. There is no local parallelism to be exploited because every branch is radically different from the last branch, and dependent on the result of the last branch. Local parallelism is necessary for a GPU to be effective and conventional game tree search algorithms have none.
  - dragontamer 7y ago
    > I feel like I've said this a few times but for some reason you're not getting it, not really sure what the hangup is? I think the hangup is that you aren't understanding what a C++ future is, and why it solves this problem. Remember, I'm operating under the assumption that the GPU-programmer has figured out how to write a C++ future on the GPU. I kinda have an overall idea of how one would be written, but I recognize that no one has done it yet. But I don't see any reason why a C++ Future couldn't be done. The real question I have is if C++ Futures can be implemented efficiently to make all of this worthwhile. (I've gone through a bunch of ideas in my brain... I think I've got one idea that is "efficient enough"... but many obvious implementations... like atomics or mutexes won't work well on a GPU. An implementation that is innately "task based cooprerative switching" is the only efficient implementation I can think of) > Like I've been saying, you don't know what you want to q-search next until you've finished the last q-search. So you can't make a q-search queue because you couldn't add anything to the queue until the previous addition was evaluated. Future<int> f = spawn(new q-search); f.wait(); <---- Really simple actually. If "f" is blocked, then the current task goes into the "blocked" list. The first task from the "unblocked list" gets pulled off. If the "unblocked list" is empty, then this SIMD-thread idles until someone else in the NVidia warp (or AMD workgroup) calls f.wait() for another opportunity. Yes, there is some divergence here, but the overall process of f.wait() is efficient enough that I don't think its a big penalty to have the warp stall. You only run Q-searches that are on the "Running" list. You only need 32-running Q-searches to keep an NVidia warp busy, or 64-running Q-searches to keep an AMD workgroup busy. Surely, there are at least 32 Q-searches that are unblocked at a time in a parallel chess search? Sure, not at ply 1, but the number of Q-searches that could be performed in parallel grows exponentially per ply, and also remember... an NVidia Warp will operate at 100% utilization with as little as 32-Q searches. An AMD Workgroup is less efficient, needing 64 Q-searches before operating at 100% utilization. But this is still a small number in the scope of the exponentially increasing chess game tree.
deleted 7y ago
[deleted]

by mot524 7y ago

dragontamer 7y ago

I appreciate the discussion. > most of the time, the engine is in the quiescence search That seems to be the best case for GPUs. Whenever a GPU SIMD thread finishes a quiescence search, just grab another position that is under quiescence search. Frankly, the quiescence search part seems most ideally suited to GPUs out of all, as long as it is appropriate batched. > Imagine you're in the q-search and you're at a node with two captures. Might as well search both at the same time. Put them onto the q-search queue, which will be checked as GPU threads go idle. The q-search problem is exactly identical to raytracers. GPUs don't know if a ray will bounce zero, once, or even 10 times. But that doesn't cause divergence because it's just about sticking rays onto a queue and evaluating them Rays in raytracers can even spawn multiple rays in a bounce, such as subsurface scattering. This pattern is solved!

mot524 7y ago
Like I've been saying, you don't know what you want to q-search next until you've finished the last q-search. So you can't make a q-search queue because you couldn't add anything to the queue until the previous addition was evaluated. I feel like I've said this a few times but for some reason you're not getting it, not really sure what the hangup is? Alpha-beta in general is so sequential that basically all the algorithms to parallelize it focus on making each thread as independent and sequential as possible. For example, the PV-split algorithm (which generalizes into Young Brothers Wait) splits the tree as low as possible (eventually to the root node) so that all threads can act as independently as possible. There is no local parallelism to be exploited because every branch is radically different from the last branch, and dependent on the result of the last branch. Local parallelism is necessary for a GPU to be effective and conventional game tree search algorithms have none.
- dragontamer 7y ago
  > I feel like I've said this a few times but for some reason you're not getting it, not really sure what the hangup is? I think the hangup is that you aren't understanding what a C++ future is, and why it solves this problem. Remember, I'm operating under the assumption that the GPU-programmer has figured out how to write a C++ future on the GPU. I kinda have an overall idea of how one would be written, but I recognize that no one has done it yet. But I don't see any reason why a C++ Future couldn't be done. The real question I have is if C++ Futures can be implemented efficiently to make all of this worthwhile. (I've gone through a bunch of ideas in my brain... I think I've got one idea that is "efficient enough"... but many obvious implementations... like atomics or mutexes won't work well on a GPU. An implementation that is innately "task based cooprerative switching" is the only efficient implementation I can think of) > Like I've been saying, you don't know what you want to q-search next until you've finished the last q-search. So you can't make a q-search queue because you couldn't add anything to the queue until the previous addition was evaluated. Future<int> f = spawn(new q-search); f.wait(); <---- Really simple actually. If "f" is blocked, then the current task goes into the "blocked" list. The first task from the "unblocked list" gets pulled off. If the "unblocked list" is empty, then this SIMD-thread idles until someone else in the NVidia warp (or AMD workgroup) calls f.wait() for another opportunity. Yes, there is some divergence here, but the overall process of f.wait() is efficient enough that I don't think its a big penalty to have the warp stall. You only run Q-searches that are on the "Running" list. You only need 32-running Q-searches to keep an NVidia warp busy, or 64-running Q-searches to keep an AMD workgroup busy. Surely, there are at least 32 Q-searches that are unblocked at a time in a parallel chess search? Sure, not at ply 1, but the number of Q-searches that could be performed in parallel grows exponentially per ply, and also remember... an NVidia Warp will operate at 100% utilization with as little as 32-Q searches. An AMD Workgroup is less efficient, needing 64 Q-searches before operating at 100% utilization. But this is still a small number in the scope of the exponentially increasing chess game tree.

deleted 7y ago

[deleted]