4 ms·

What's interesting, and I don't quite understand, is that even for problems with a decent amount of branching, they can still be surprisingly fast. I wrote a pa

What's interesting, and I don't quite understand, is that even for problems with a decent amount of branching, they can still be surprisingly fast. I wrote a path tracer as an OpenGL shader that had a lot of branching and didn't use any special data structures for ray intersections and it was still much faster than running it on my CPU. So in my example, the GPU for each pixel has to find out of a ray collides with any object in the scene, and then scatter that light off of that object up to some maximum number of scattering or until it leaves the scene. This results in a variable number of branches per pixel (between about 1 and 16), but still gets good performance.

pierrebai 8y ago
The GPU is actually divided in group of units. The vendor use terms like wave or warp to descibe this unit. On such execution unit contains in the order of 32-64 ALU. When a branch is hit, if all unit do not go into the same branch, I believe they still all execute both branches. The ALU keepa a flag telling it which branch is live and the other branch basically execute as noop. So if a warp has a mix of branch taken and not taken, your execution time is proportional to the total cost of both branches added together. It's still faster than a CPU due to the huge number of ALU. (Plus, image coherence makes it that you will often hit only one branch in all ALU, which is optimized.)
dahart 8y ago
> What's interesting, and I don't quite understand, is that even for problems with a decent amount of branching, they can still be surprisingly fast. If your threads are uniformly spread between 1 and 16 branches, then you're probably always paying for 16 branches, and you could make it a lot faster by grouping similar workloads or getting rid of branches. But yes, branchy code can be fast as long as almost all threads do the same thing. Branches don't automatically cost extra. What matters is how many threads in your wavefront / warp / work group are executing the same branch. If they all take the first branch in an if-else, and no threads in the warp take the else clause, then you don't pay for execution of both branches. But if one thread in the warp does take the else path, then all the threads in the warp pay the cost of executing both paths. The story is starting to change for the newest AMD & NVIDIA GPUs, they are now supporting per-thread instruction pointers, and parallel divergent execution. But there are big restrictions and caveats, and the high level bit hasn't changed: it is still best if all threads in a warp all do the same thing.
- westoncb 8y ago
  > ... and you could make it a lot faster by grouping similar workloads Could anyone clarify what's meant by that, or more concretely how it might be done?
  - dahart 8y ago
    One way people do this is to group pixels by which material shader needs to execute. You want all threads in a warp to execute the same material shader, if at all possible. One way to do this is to use a deferred shading architecture, and do some kind of radix sort by shader id in between the visibility and shading passes. Using the GP's example of ray tracing with 1-16 branches, if you can figure out in advance, or even just estimate, how many branches you're going to take, you could sort, or even create 16 separate work queues. Assuming we're talking about recursion that involves identical code for each branch, then by grouping threads into chunks that are likely to execute only 1 branch, your entire warp will (hopefully) execute 1 branch, and it will finish in 1/16th of the time that it would take if any one of the threads went the full 16 branches. If you're not doing graphics, the way people do this kind of stuff is to have some kind of mapping function on the (virtual) thread id that lets them re-arrange the order of events. You have complete control over what the thread id means, so it doesn't have to point to a memory location nor handle your data in a consecutive order. (Of course, you will lose cache coherence for out of order memory access, but that might be small compared to divergence problems.)
pcwalton 8y ago
To a first approximation, as long as spatially-local fragments all take the same branches, you can get good performance from branching on GPU. What matters is whether individual threadgroups ("warps", in NVIDIA speak) have coherent branches. The rasterizer makes an attempt to schedule nearby pixels on the same threadgroup, mostly to improve memory locality, but also to benefit workloads like yours. In your case, if your scene objects are relatively large and nearby rays all tend to hit the same objects, then per-threadgroup branch divergence can be minimal.

pierrebai 8y ago

The GPU is actually divided in group of units. The vendor use terms like wave or warp to descibe this unit. On such execution unit contains in the order of 32-64 ALU. When a branch is hit, if all unit do not go into the same branch, I believe they still all execute both branches. The ALU keepa a flag telling it which branch is live and the other branch basically execute as noop. So if a warp has a mix of branch taken and not taken, your execution time is proportional to the total cost of both branches added together. It's still faster than a CPU due to the huge number of ALU. (Plus, image coherence makes it that you will often hit only one branch in all ALU, which is optimized.)

dahart 8y ago

> What's interesting, and I don't quite understand, is that even for problems with a decent amount of branching, they can still be surprisingly fast. If your threads are uniformly spread between 1 and 16 branches, then you're probably always paying for 16 branches, and you could make it a lot faster by grouping similar workloads or getting rid of branches. But yes, branchy code can be fast as long as almost all threads do the same thing. Branches don't automatically cost extra. What matters is how many threads in your wavefront / warp / work group are executing the same branch. If they all take the first branch in an if-else, and no threads in the warp take the else clause, then you don't pay for execution of both branches. But if one thread in the warp does take the else path, then all the threads in the warp pay the cost of executing both paths. The story is starting to change for the newest AMD & NVIDIA GPUs, they are now supporting per-thread instruction pointers, and parallel divergent execution. But there are big restrictions and caveats, and the high level bit hasn't changed: it is still best if all threads in a warp all do the same thing.

westoncb 8y ago
> ... and you could make it a lot faster by grouping similar workloads Could anyone clarify what's meant by that, or more concretely how it might be done?
- dahart 8y ago
  One way people do this is to group pixels by which material shader needs to execute. You want all threads in a warp to execute the same material shader, if at all possible. One way to do this is to use a deferred shading architecture, and do some kind of radix sort by shader id in between the visibility and shading passes. Using the GP's example of ray tracing with 1-16 branches, if you can figure out in advance, or even just estimate, how many branches you're going to take, you could sort, or even create 16 separate work queues. Assuming we're talking about recursion that involves identical code for each branch, then by grouping threads into chunks that are likely to execute only 1 branch, your entire warp will (hopefully) execute 1 branch, and it will finish in 1/16th of the time that it would take if any one of the threads went the full 16 branches. If you're not doing graphics, the way people do this kind of stuff is to have some kind of mapping function on the (virtual) thread id that lets them re-arrange the order of events. You have complete control over what the thread id means, so it doesn't have to point to a memory location nor handle your data in a consecutive order. (Of course, you will lose cache coherence for out of order memory access, but that might be small compared to divergence problems.)

pcwalton 8y ago

To a first approximation, as long as spatially-local fragments all take the same branches, you can get good performance from branching on GPU. What matters is whether individual threadgroups ("warps", in NVIDIA speak) have coherent branches. The rasterizer makes an attempt to schedule nearby pixels on the same threadgroup, mostly to improve memory locality, but also to benefit workloads like yours. In your case, if your scene objects are relatively large and nearby rays all tend to hit the same objects, then per-threadgroup branch divergence can be minimal.