3 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. If your t
by 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 agoOne 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.)