5 ms·

I still don't get the "no good for branching code" point... Since most of the work is split in millions of "threads" which all run in parallel, then why is bran

by wiz21c 3y ago

I still don't get the "no good for branching code" point... Since most of the work is split in millions of "threads" which all run in parallel, then why is branching an issue ? Some threads will take a bit longer than the others. Maybe groups of threads will go as slow as the slowest but still, prallelism should make up the bulk of the acceleration. No ?

maeln 3y ago
Most GPU's only have so much compute cores. Even if you have a million threads, you might only have a few hundreds cores to execute them. If you have heavy branching you might slow down the whole lane (which size can vary from 8 to 64 execution most of the time). Which at this scale still do make a big difference. Although for small branching, masking help avoid too much slowdown.
- WJW 3y ago
  To expand on this, even the latest Nvidia 4090 card "only" has about 16k cores. That's a lot, but it's hardly "millions" either.
  - ben-schaaf 3y ago
    To expand further the 16k cores aren't real cores. What people would normally consider a core is what Nvidia calls a "streaming multiprocessor" (SM), of which the 4090 has 128. These cores each have 128 "cuda cores", analogous to a SIMD lane - although not quite since "cuda cores" are themselves SIMD. To simplify: Each 128 SMs can run a different program and each of their 128 "cuda cores" can do ~single-cycle (small) matrix operations.
    - 6keZbCECT2uB 3y ago
      I'm not sure about the 4090, but most of the GPUs I use have a warp size of 32, and warp divergence affects only up to those 32 threads. If you have a branch and all threads agree, you only walk down one branch. My mental model is a bit more like you have collections of warps in a block, and all warps in a block get scheduled onto an SM. Different GPU architectures allow for different numbers of warps to be simultaneously active or inactive, and each warp has its own instruction pointer and can be suspended while waiting for things like memory. I found the picture on pg 22 here really helpful: https://images.nvidia.com/aem-dam/en-zz/Solutions/data-center/nvidia-ampere-architecture-whitepaper.pdf https://images.nvidia.com/aem-dam/en-zz/Solutions/data-cente... Note that although there's 4 schedulers, on the A100, they don't dispatch every cycle iirc.
      - ben-schaaf 3y ago
        Those are tensor cores, not cuda cores. They're used for AI rather than general compute/shaders. The 4090 has 512 of those. Correct me if I'm wrong, but as far as I can tell tensor cores are just accelerators. They can't do general compute: no branch or jump.
        6keZbCECT2uB 3y ago
        The tensor core accelerates mostly matrix operations and is the big block you can see has 4 per SM. Cuda core refers to the thread per SM, which you can see as FP32 or INT32 units, so there are (32*4) per SM on that diagram. Like you said, tensor core is similar to a special purpose ALU and is at a lower level of abstraction than something with an instruction pointer.
seanmcdirmid 3y ago
The threads share control units. So if threads sharing the same control unit branch differently, they have to do both branches for all the threads (well, it depends on the GPU architecture). The threads will never finish before the others (again, if they are sharing the same control units). It works out for graphics and well engineered GGPU code because adjacent pixels and vertexes usually are similar enough to have a high chance of having the same branching behavior.
sspiff 3y ago
Most GPUs run threads in groups of 16 or more, with one instruction pointer shared by all of the threads in a single group. So if some threads need to take an IF-branch, and some need to take an ELSE-branch, both paths are executed in sequence, with all threads in the group executing in lock-step, and a per-thread mask disabling the effects of the instructions that aren't needed for each specific thread. If you do this enough times, with sufficiently complicated branching, you'll quickly negate any efficiency gain you get from the massive parallelism.
- trashtester 3y ago
  That's kind of like hitting a tree with a chainsaw, and complain it's a bad axe.
  - raincole 3y ago
    No one is complaining about anything. It's a brief explanation for a simple fact.
    - trashtester 3y ago
      Fair enough.
c4mpute 3y ago
GPU threads aren't "threads" as you know them on a CPU. They aren't independent units of execution with their own control flow. Each instruction decoder in the GPU feeds a few hundred execution units, each addressing and fetch unit feeds a few hundred execution units. So if suddenly one of those hundreds of execution units takes a different branch, that control flow will have to be executed in sequence, before or after the control flows that didn't branch. This means that all the other execution units will be flushed, stay idle, and wait while the few instruction decoder and fetch units will process that one different branch. So a branch penalty won't be just a few cycles, as in a CPU, but a few thousand cycles times a few hundred execution units. Plus an additional memory fetch latency because GPU memory also isn't really designed for random access patterns.

by wiz21c 3y ago

maeln 3y ago

Most GPU's only have so much compute cores. Even if you have a million threads, you might only have a few hundreds cores to execute them. If you have heavy branching you might slow down the whole lane (which size can vary from 8 to 64 execution most of the time). Which at this scale still do make a big difference. Although for small branching, masking help avoid too much slowdown.

WJW 3y ago
To expand on this, even the latest Nvidia 4090 card "only" has about 16k cores. That's a lot, but it's hardly "millions" either.
- ben-schaaf 3y ago
  To expand further the 16k cores aren't real cores. What people would normally consider a core is what Nvidia calls a "streaming multiprocessor" (SM), of which the 4090 has 128. These cores each have 128 "cuda cores", analogous to a SIMD lane - although not quite since "cuda cores" are themselves SIMD. To simplify: Each 128 SMs can run a different program and each of their 128 "cuda cores" can do ~single-cycle (small) matrix operations.
  - 6keZbCECT2uB 3y ago
    I'm not sure about the 4090, but most of the GPUs I use have a warp size of 32, and warp divergence affects only up to those 32 threads. If you have a branch and all threads agree, you only walk down one branch. My mental model is a bit more like you have collections of warps in a block, and all warps in a block get scheduled onto an SM. Different GPU architectures allow for different numbers of warps to be simultaneously active or inactive, and each warp has its own instruction pointer and can be suspended while waiting for things like memory. I found the picture on pg 22 here really helpful: https://images.nvidia.com/aem-dam/en-zz/Solutions/data-center/nvidia-ampere-architecture-whitepaper.pdf https://images.nvidia.com/aem-dam/en-zz/Solutions/data-cente... Note that although there's 4 schedulers, on the A100, they don't dispatch every cycle iirc.
    - ben-schaaf 3y ago
      Those are tensor cores, not cuda cores. They're used for AI rather than general compute/shaders. The 4090 has 512 of those. Correct me if I'm wrong, but as far as I can tell tensor cores are just accelerators. They can't do general compute: no branch or jump.
      - 6keZbCECT2uB 3y ago
        The tensor core accelerates mostly matrix operations and is the big block you can see has 4 per SM. Cuda core refers to the thread per SM, which you can see as FP32 or INT32 units, so there are (32*4) per SM on that diagram. Like you said, tensor core is similar to a special purpose ALU and is at a lower level of abstraction than something with an instruction pointer.

seanmcdirmid 3y ago

The threads share control units. So if threads sharing the same control unit branch differently, they have to do both branches for all the threads (well, it depends on the GPU architecture). The threads will never finish before the others (again, if they are sharing the same control units). It works out for graphics and well engineered GGPU code because adjacent pixels and vertexes usually are similar enough to have a high chance of having the same branching behavior.

sspiff 3y ago

Most GPUs run threads in groups of 16 or more, with one instruction pointer shared by all of the threads in a single group. So if some threads need to take an IF-branch, and some need to take an ELSE-branch, both paths are executed in sequence, with all threads in the group executing in lock-step, and a per-thread mask disabling the effects of the instructions that aren't needed for each specific thread. If you do this enough times, with sufficiently complicated branching, you'll quickly negate any efficiency gain you get from the massive parallelism.

trashtester 3y ago
That's kind of like hitting a tree with a chainsaw, and complain it's a bad axe.
- raincole 3y ago
  No one is complaining about anything. It's a brief explanation for a simple fact.
  - trashtester 3y ago
    Fair enough.

c4mpute 3y ago

GPU threads aren't "threads" as you know them on a CPU. They aren't independent units of execution with their own control flow. Each instruction decoder in the GPU feeds a few hundred execution units, each addressing and fetch unit feeds a few hundred execution units. So if suddenly one of those hundreds of execution units takes a different branch, that control flow will have to be executed in sequence, before or after the control flows that didn't branch. This means that all the other execution units will be flushed, stay idle, and wait while the few instruction decoder and fetch units will process that one different branch. So a branch penalty won't be just a few cycles, as in a CPU, but a few thousand cycles times a few hundred execution units. Plus an additional memory fetch latency because GPU memory also isn't really designed for random access patterns.