5 ms·

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 cou

• 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.
• dragontamer 7y ago
  > 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. I forgot to respond to this half. Have you heard of Task-based parallelism? Pretty much any recursive algorithm can easily become parallel through the technique. Alpha-beta tree searches very easily follow the task-based parallelism. Give this page a look: https://software.intel.com/en-us/node/506102 https://software.intel.com/en-us/node/506102 ------- The key element that ties it all together is the future / promise construct. https://en.wikipedia.org/wiki/Futures_and_promises https://en.wikipedia.org/wiki/Futures_and_promises If you have a task-based parallelism model, with symbolically executed futures/promises (that... instead of waiting immediately on max(alpha, score)... where "alpha" and "core" are both futures... it can immediately return a symbol representing "max(alpha, score)" and carry on with the execution / evaluation. Lazily evaluating the future at a later time when alpha and/or score is ready. Yeah, its a few advanced threading concepts here and there. But I've seen the primitives written in various frameworks. And from my understanding of GPU-programming, C++ Futures / Promises CAN be implemented in GPUs. Its just that no one has really done it yet. From those perspectives, I keep looking at something as "sequential" as alpha-beta pruning and I don't see any major thread-divergence issues. Honest. I just don't think anyone has combined these 4 or 5 techniques together in one program yet. In short: * GPGPU programming / SIMD * Task-based parallelism (like TBB): https://software.intel.com/en-us/node/506102 https://software.intel.com/en-us/node/506102 * Futures * Symbolically-lazily executed symbols associated with the futures (only "Beta-cuttoff" absolutely requires a yield or stall. Everything else can be "lazily" executed at a later point in time, which should discover latent parallelisms in the program). * Alpha-Beta pruning ------- You keep saying "it cannot be done", but what I'm saying is "I've seen some new parallel primitives invented in the last 10 years. I think it can be done now". As long as someone ports these primitives over to the GPU. EDIT: I have looked through the AMD Vega instruction set. Modern GPUs allow the programmer to know the program-counter, to set the program counter (aka a jump), and all that good stuff. Function-pointers, as long as a full AMD workgroup (64-threads) or NVidia warp (32-threads) do in fact work (!) on a modern GPU. Yeah, there are issues like the CPU Stack (it won't translate to the GPU. So everything talked about here would have to be converted into iterative form). So I haven't solved all the issues yet. But the general thought process looks promising to my eyes