Hi! I've heard that you should be careful with the dynamic branching that can be done in SM3 pixel shaders. But to what extent? What happens in the pipeline when you put in if statements in the shader code? Naturally there will be a disturbance in the coherence if different pixels processed at the same time follow different paths, but exactly HOW does this affect efficiency? And if I where to write something like this: if(condition) result = float4(1,1,1,1); else result = float4(0,1,0,1); Would this disturb the coherence? My intuition tells me that because the two assignments here should take equal time to complete, the shaders would be running the rest of the code (after the if thingy) in parallell again. Is this right? Thanx

Not sure what you mean by coherence. You're guaranteed that the output is corect, even if different pixels end up taking different code paths. And they don't have to run 100% synchronized or anything. They're assigned separate shader units executing the shader.

The problem is a classic pipelining problem, and CPU's suffer from the same (except they dedicate more resources to reducing the impact, and they have shorter pipelines lessening the impact as well)

Quite simply, a pipelined CPU doesn't wait for one instruction to complete before starting on the next. Instead, once one instruction has been loaded, it is passed to the next pipeline stage, which may consist of actually executing the instruction, and when that is done, the result is passed to the stage responsible for storing the result back into the registers. (That's a unrealistically simple model, but it should serve to explain my point)

Now, once instruction i has been read, it is passed to the execute stage. This leaves the read stage idle, so it starts reading instruction i+1. In the next clock cycle, i will be at the write stage, while i+1 is being executed, and again, the read stage is free to begin on another instruction, i+2.

That's all fine, as long as there are no dependencies between instructions. Let's say i+1 uses the result computed in i. When i+1 is at the execute stage, i is at the write stage, but it hasn't written its result back yet. So i+1 has to wait one cycle for the data it needs to be available.

That can usually be solved by forwarding the result directly, without waiting for it to store to the register file.

A bigger problem is branches. How does the read stage know which instruction to read next, if we don't yet know whether the previous instruction was a branch?
It doesn't. So it has to make a guess, trying to predict whether the previous instruction was a branch, if the branch is actually taken, and if so, where we should jump to. In the worst case, you might have to sit idle for several cycles, just waiting to be told which instruction you should read next. That's a nasty performance hit.

Now replace my primitive 3-stage pipeline (where you might lose one or two cycles here or there) with the ~15 stages of an Athlon 64. Or the 30+ of a Pentium 4. Or the several hundred (Exact number isn't known outside NVidia/ATI, but a figure I heard some years ago was 250'ish) stages in a modern GPU. Imagine if you encounter a branch, and you have to wait 50 cycles just to find out which instruction to read next.

Branch prediction can be done very accurately on CPU's (to the extent that something like 98% of all branches may be guessed correctly)
On a GPU, that's trickier. First, you don't really have an accurate history to refer to. You could look at what this shader unit did on the last, say, 10 pixels it computed, but they took very different input, and might just mislead you. Or you could try to look at the branch history of all shader units, which would be just as misleading.
Or you could look at the last 10 times you encountered this instruction in the current pixel, but since shader programs are very short, so most of the time, you won't encounter any specific branch more than a few times.

Furthermore, branch prediction isn't free. It requires a good chunk of the die, transistors which could have been used on other things.

Basically, GPU's have looong pipelines, which make branch prediction expensive. They also don't have very advanced branch prediction units, which means they can't really do much to minimize this branch penalty.

Hope this makes sense

Thank you for your answer. I pretty much got it, but just to make sure...

What you are saying is that the penalty doesn't come from the fact that the different parallelly processed pixels may take different paths, but from the branch instruction itself?

Is there a way to help the GPU with the branch prediction, for example when pixels close to each other use the same branching. (I'm just processing data from one texture to a rendertarget texture (General Purpose Computation on the GPU), so I could organize it).

The coherency issue comes in cases like this:

if(testResult)
outColor=DoCheapThing();
else
outColor=DoExpensiveThing();

The way this implemented in GPU is that all the pixels in a region of the screen (around 30x30 pixels for most current GPUs) will take the same "path" through the program. So unless 'testResult' is either TRUE or FALSE for almost all the pixels in a block the you not see any speed up (as all the pixels end up executing the code for DoCheapThing AND DoExpensiveThing).

Edit - I mean all the pixels, not almost all, in a block, as long MOST of the block are either all true or all false (i.e. only a few blocks of pixels end up executing both paths) you should see a speed up. The classic example of where this kind of algorithm is used is PCF shadow filtering.

Guys, where do you learn this sort of things? Thank you so much! You've been very helpful.

Quote:Original post by fortia
Guys, where do you learn this sort of things? Thank you so much! You've been very helpful.

I know I'm not one of the "guys", but some of the the best places to learn is
NVidia documentation
ATI's technical publications
ATI's presentations

Then there is a lot of papers/presentations floating around the net (SIGGRAPH, GDC). Also the ShaderX and GPU Gems series of books contains lots of valuable information. And if you look a little more on NVidia's and ATI's site I'm sure you can find some more information. You might even want to look into general techniques used for "processing units" (CPU/GPU/PPU/etc.), techniques such as branch prediction, out of order execution, etc.

Quote:Original post by fortia
Guys, where do you learn this sort of things? Thank you so much! You've been very helpful.

My part was just basic CPU architecture. Learned that in one of my computer science classes. (And unfortunately, I completely forgot about some of the GPU quirks mentioned by the people after me, like the fact that it processes bigger batches of pixels at a time.)
So yeah, the penalty comes both from problems with branches on any pipelined architecture, and from the GPUs running large batches of pixels through the same code path.

Quote:btw do you have a source/link for the 250 stage pipeline... that doesn't sound correct but I could be wrong.

Nope, just found an article about it a way back... Think it might have been on Ars Technica, but honestly can't remember. But keep in mind that they have to be long enough to be able to hide the latency from texture accesses and such. Of course, it's possible that this figure referred to old fixed-function pipelines, and todays shader-based ones are shorter. I don't know, wish I could find the article again, so I could at least check how old it was. In any case, GPU pipelines are long. But hard to say *how* long. [grin]