# Impact of variable-length loops on GPU shaders

Its popular to render procedural content inside the GPU e.g. in the demoscene (drawing a single quad to fill the screen and letting the GPU compute the pixels).

Ray marching is popular:

This means the GPU is executing some unknown number of loop iterations per pixel (although you can have an upper bound like maxIterations).

How does having a variable-length loop affect shader performance?

Imagine the simple ray-marching psuedocode:

t = 0.f;
while(t < maxDist) {
p = rayStart + rayDir * t;
d = DistanceFunc(p);
t += d;
if(d < epsilon) {
... emit p
return;
}
}


How are the various mainstream GPU families (Nvidia, ATI, PowerVR, Mali, Intel, etc) affected? Vertex shaders, but particularly fragment shaders?

How can it be optimised?

• Unfortunately, this question is too hard to be answered properly here. Although one answer already given points to such a source worth reading (involves dynamic branching). +1 for the "topic".. – teodron Jul 6 '12 at 11:27
• @teodron don't be defeatist! I was hoping someone would say that on NVidia cards screen pixels in 8x8 blocks will all iterate as deep as the deepest needs to, and that blocks of 8x8 pixels can be done in any order, or something like that; that's not true, that's just the kind of wisdom I'm hoping people will be able to share. Links on Larrabee, hmm, are pretty indirect. – Will Jul 6 '12 at 12:13
• Doesn't seem like he's discussing Larrabee, but the Stanford guy gave the same talk two years after, in 2010 ( you can see it here ). From his figures, considering a while loop, I didn't understand whether the pixels that "end" their computations sooner do make up for any performance. In CUDA, threads wait at a barrier. In analogy, what happens with shader threads? – teodron Jul 6 '12 at 13:55
• @teodron yeah, I've taken my understanding of CUDA and applied to to GPUs; I'm sure they are in lockstep, but I'd like someone knowledgeable to chime in; anyway, here's something related williamedwardscoder.tumblr.com/post/26628848007/rod-marching – Will Jul 6 '12 at 14:35

There was a nice talk at GDC 2012 on GPU distance field ray-marching (and other topics): http://directtovideo.wordpress.com/2012/03/15/get-my-slides-from-gdc2012/

As far as performance goes, the latest (DX11-class) graphics cards execute shaders on SIMD units that run 32 (NVIDIA) or 64 (AMD) "threads" in lockstep. These groups are variously known as warps or wavefronts. For pixel shaders, each thread equals one pixel, so I would expect that the SIMD unit is processing something like an 8x4 (NVIDIA) or 8x8 (AMD) block of pixels together. Branching and flow control is done per-wavefront, so all the threads in a wavefront have to loop as many times as the deepest individual pixel within that wavefront. SIMD lane masks will turn off execution for the pixels that have finished already, but they still have to silently go along with the overall wavefront's flow control. This means, of course, that the system is much more efficient when the branching is coherent, so that threads in a wavefront tend to all branch the same way or have similar numbers of iterations.

In my experience, branch overhead is still pretty high even if all threads in the wavefront branch the same way. I've seen performance gains in some cases by unrolling the loop to amortize some of the branch overhead. However, it depends on how much work you're doing in each loop iteration, of course. If the loop body has enough "stuff" in it, unrolling won't be a win.

I suggest reading Running Code at a Teraflop: How GPU Shader Cores Work (pdf) from SIGGRAPH 2008: Beyond Programmable Shading. It talks about dynamic branching.

With regards to dynamic branching, one additional note (may be obvious, but still worth noting to some people): it can severely affect the performance of unrolled loops (you obviously cannot unroll a loop if there is a non-constant number of iterations).

int s=0;

now for(int k=1;k<=n;k++){s+=k;} is the same like s=n*(n+1)/2

so thats not true in general :D

• You might be getting downvoted a lot because nobody's quite sure what you're trying to convey here or what it has to do with the question. – doppelgreener Sep 28 '12 at 14:17