4 ms·

I've already spent a bunch of time explaining to you why this won't work. But hey, apparently you're the expert. If you want to reimplement Stockfish on a GPU s

by mot524 7y ago

I've already spent a bunch of time explaining to you why this won't work. But hey, apparently you're the expert. If you want to reimplement Stockfish on a GPU such than it's faster than a CPU then nobody's stopping you. The source code is only ~10k lines and very well-written, clear, well-documented, and easy to understand. Go for it. You'll be famous as the first person to effectively implement alpha-beta on a GPU and as the author of the strongest conventional chess engine in history. So go for it.

dragontamer 7y ago
Regardless, I appreciated the discussion! Maybe I'll give it a whack. It all comes down to whether or not I could build "future" efficiently on a GPU. I don't want to pretend I'm an expert at all. I've looked at symbolic manipulation and chess mostly as a hobby (since the Chess community has so many cool bitwise algorithms they've invented). And the GPU-community is small, but interesting to me. HPC programmers / C++ programmers in another bunch... information really isn't flowing as well between the "styles of compute", I'm just trying to connect a bunch of ideas that other people have thought up together.
- mot524 7y ago
  Okay, as long as we're not arguing, I will tell you that any sort of fine-grained intra-thread communication is to be avoided like the plague in computer chess. Engines are able to search millions of positions per second... most multithreading frameworks (e.g., the ones that give you your "futures" and "promises") rely on locks that can halt threads for milliseconds at a time. It's absolutely disastrous for efficiency. I believe Stockfish uses the idea of "Lazy SMP" for parallel search which literally means no intra-thread communication other than locks on hash table entries to avoid data corruption of the hash table. Anything more sophisticated has proven to be a loss. So any sort of discussion of tasks, futures, promises, or even Young Brothers Wait is going to be fairly pointless. Also, anything that relies on offloading data to the GPU for processing for more than a few milliseconds is going to be a net loss for obvious reasons. Meaning that even if you could evaluate a million positions in parallel, and you already (somehow) knew which positions you needed to evaluate, doing the evaluation on the GPU is probably still going to be a loss due to the time it takes to copy the positions to/from the GPU. Really, if you were tasked to come up with an algorithm that was poorly suited for GPGPU computation, it might be computer chess. That being said, it doesn't really matter. How much were you hoping to speed up Stockfish? AlphaZero still crushes Stockfish at 10:1 time odds. Even if you were able to make Stockfish 10x faster it wouldn't change the dynamic of CNN chess engines being superior to conventional engines.
  - dragontamer 7y ago
    > Engines are able to search millions of positions per second... most multithreading frameworks (e.g., the ones that give you your "futures" and "promises") rely on locks that can halt threads for milliseconds at a time. It's absolutely disastrous for efficiency. Yeah, that's what I mean as "efficiently create a future" on the GPU. GPUs absolutely cannot spinlock, and atomics are way slower than CPU atomics. So mutex / spinlock / atomic based synchronization absolutely won't work. So... what's my plan? Well... as I said, task-based cooperative multithreaded futures. I've talked about some ideas for how to implement it above... but I won't post another wall of text. Also: some advanced synchronization primitives are free on SIMD-based GPUs (ex: thread-barriers within a warp are literally free and compile down to a no-op). I think there's a rich set of efficient GPU synchronization primitives. Lazy SMP works for Stockfish, but clearly won't work with 163,840 threads (Vega 64 at max thread occupancy). So I'd have to do something else. (163840 threads locking the RAM one-at-a-time to access a shared hash table? Probably not going to work) > How much were you hoping to speed up Stockfish? The Vega64 GPU has 4096 shaders at 1.5 GHz. 5k to 50k shader-cycles per node would give 122 Million nodes/second to 1220 Million nodes/second. Vega64 GPU also has 500 GBps of memory bandwidth of 8GBs of HBM2 RAM, with "64kB Shared Memory" per CU having an aggregate bandwidth of 9,000 GBps (which should lead to potentially better cross-thread synchronization structures within a workgroup) Hard to say where a project would land, but probably within that range somewhere. It'd HAVE to land there to be successful (and hopefully closer to the 5k shader-cycles per node) The only major instruction GPUs are missing is the pext and pdep instructions from x86. Sliding piece attacks may need a rework to be efficient on a GPU due to the very low amounts of L1 RAM available. Otherwise, GPUs support popcount, AND, XOR, etc. etc. that chess bitboard use. BTW: Threadripper 1950x running Stockfish processes 2-million Nodes/Second, or roughly 32k core-cycles per node (4GHz 16-cores)). Which served as the basis of my estimate (+/- a magnitude)
    - mot524 7y ago
      I already told you that intra-thread synchronization is to be avoided but you're still talking about it (promises, futures, tasks, etc.) so I don't know what to say. Nothing you're saying is going to work like you think it is, but it seems like you're going to have to figure that out for yourself. Clearly you want to talk more than you want to program. Maybe reimplementing Stockfish on a GPU is too daunting of a task. Why don't you get something simple like TSCP running on a GPU and see how far you get with that? TSCP is only about 2k lines of code and probably half of those lines are comments. With the state of GPU cores and compilers these days maybe you can get the C code running on a GPU core directly without much modification. TSCP also uses less than 64k of RAM so it should fit nicely in an Nvidia SM.

by mot524 7y ago

dragontamer 7y ago

Regardless, I appreciated the discussion! Maybe I'll give it a whack. It all comes down to whether or not I could build "future" efficiently on a GPU. I don't want to pretend I'm an expert at all. I've looked at symbolic manipulation and chess mostly as a hobby (since the Chess community has so many cool bitwise algorithms they've invented). And the GPU-community is small, but interesting to me. HPC programmers / C++ programmers in another bunch... information really isn't flowing as well between the "styles of compute", I'm just trying to connect a bunch of ideas that other people have thought up together.

mot524 7y ago
Okay, as long as we're not arguing, I will tell you that any sort of fine-grained intra-thread communication is to be avoided like the plague in computer chess. Engines are able to search millions of positions per second... most multithreading frameworks (e.g., the ones that give you your "futures" and "promises") rely on locks that can halt threads for milliseconds at a time. It's absolutely disastrous for efficiency. I believe Stockfish uses the idea of "Lazy SMP" for parallel search which literally means no intra-thread communication other than locks on hash table entries to avoid data corruption of the hash table. Anything more sophisticated has proven to be a loss. So any sort of discussion of tasks, futures, promises, or even Young Brothers Wait is going to be fairly pointless. Also, anything that relies on offloading data to the GPU for processing for more than a few milliseconds is going to be a net loss for obvious reasons. Meaning that even if you could evaluate a million positions in parallel, and you already (somehow) knew which positions you needed to evaluate, doing the evaluation on the GPU is probably still going to be a loss due to the time it takes to copy the positions to/from the GPU. Really, if you were tasked to come up with an algorithm that was poorly suited for GPGPU computation, it might be computer chess. That being said, it doesn't really matter. How much were you hoping to speed up Stockfish? AlphaZero still crushes Stockfish at 10:1 time odds. Even if you were able to make Stockfish 10x faster it wouldn't change the dynamic of CNN chess engines being superior to conventional engines.
- dragontamer 7y ago
  > Engines are able to search millions of positions per second... most multithreading frameworks (e.g., the ones that give you your "futures" and "promises") rely on locks that can halt threads for milliseconds at a time. It's absolutely disastrous for efficiency. Yeah, that's what I mean as "efficiently create a future" on the GPU. GPUs absolutely cannot spinlock, and atomics are way slower than CPU atomics. So mutex / spinlock / atomic based synchronization absolutely won't work. So... what's my plan? Well... as I said, task-based cooperative multithreaded futures. I've talked about some ideas for how to implement it above... but I won't post another wall of text. Also: some advanced synchronization primitives are free on SIMD-based GPUs (ex: thread-barriers within a warp are literally free and compile down to a no-op). I think there's a rich set of efficient GPU synchronization primitives. Lazy SMP works for Stockfish, but clearly won't work with 163,840 threads (Vega 64 at max thread occupancy). So I'd have to do something else. (163840 threads locking the RAM one-at-a-time to access a shared hash table? Probably not going to work) > How much were you hoping to speed up Stockfish? The Vega64 GPU has 4096 shaders at 1.5 GHz. 5k to 50k shader-cycles per node would give 122 Million nodes/second to 1220 Million nodes/second. Vega64 GPU also has 500 GBps of memory bandwidth of 8GBs of HBM2 RAM, with "64kB Shared Memory" per CU having an aggregate bandwidth of 9,000 GBps (which should lead to potentially better cross-thread synchronization structures within a workgroup) Hard to say where a project would land, but probably within that range somewhere. It'd HAVE to land there to be successful (and hopefully closer to the 5k shader-cycles per node) The only major instruction GPUs are missing is the pext and pdep instructions from x86. Sliding piece attacks may need a rework to be efficient on a GPU due to the very low amounts of L1 RAM available. Otherwise, GPUs support popcount, AND, XOR, etc. etc. that chess bitboard use. BTW: Threadripper 1950x running Stockfish processes 2-million Nodes/Second, or roughly 32k core-cycles per node (4GHz 16-cores)). Which served as the basis of my estimate (+/- a magnitude)
  - mot524 7y ago
    I already told you that intra-thread synchronization is to be avoided but you're still talking about it (promises, futures, tasks, etc.) so I don't know what to say. Nothing you're saying is going to work like you think it is, but it seems like you're going to have to figure that out for yourself. Clearly you want to talk more than you want to program. Maybe reimplementing Stockfish on a GPU is too daunting of a task. Why don't you get something simple like TSCP running on a GPU and see how far you get with that? TSCP is only about 2k lines of code and probably half of those lines are comments. With the state of GPU cores and compilers these days maybe you can get the C code running on a GPU core directly without much modification. TSCP also uses less than 64k of RAM so it should fit nicely in an Nvidia SM.