Parallel Reduction basics

Very often in computer graphics we need some form of parallel reduction.

For example, I stumbled on a vvvv blog post about boids simulation. In that case there is two main things you need for efficient simulation:

• Average of all positions.
• Acceleration structure for neighbours

Since actually both techniques use similar concepts, but the second one is slightly more advanced, I'll explain the first one.

So here is the deal:

We have let's say 4096 (64*64) boids, and we need average for some rules.

Our boids are stored in a StructuredBuffer (so we can Read/Write into it).

If we do this in CPU, we have something like this (pseudo code)

float3 sum;

foreach(boid in boids)

{

    sum += boid.pos;

}

sum /= (float)boidscount;

Of course, problem is our data is in GPU, so we don't want to transfer back and forth.

What is actually fun in DirectX11 is you have many ways to cover the same technique, let go trough a few of them.

1/Additive Render

Create a 1x1 texture (R32G32B32A32_Float)

Render all your boids, vertex shader is like this:

Code Snippet

3. struct vsInput
4. {
5.     uint iv : SV_VertexID;
6. };
7.  
8. struct psInput
9. {
10.     float4 screenpos : SV_POSITION;
11.     float4 objectpos : TEXCOORD0;
12. };
13.  
14. psInput VS(vsInput input)
15. {
16.     psInput output;
17.     output.screenpos = float4(0,0,0,1);
18.     output.objectpos = float4(PositionBuffer[input.iv],0.0f);
19.     return output;
20. }

Here we just set position to be 0,0 (since anyway we have single pixel), Boid position is sent to pixel shader as Texture Coordinate.

No here is our (hardcore) pixel shader:

Code Snippet

22. float4 PS(psInput input): SV_Target
23. {
24.     return input.objectpos;
25. }

We only return object position (please make sure to set Blend to Additive).

Now our single pixel contains the sum of all positions.

Divide this by boids count (in another pixel shader or a single compute shader), and you have your average position.

2/Good old MipMap

For this one, this is also pretty simple. Create a texture in R32G32B32A32_Float format as well, big enough to fit all boids (in our case 64*64 fits perfectly).

Now render your boids as PointList (so each boids position must arrive in a single output pixel).

So either draw 4096 elements, position boids from SV_VertexID to match a pixel (basic 1D->2D conversion). 

Alternatively you can make an instanced Draw Call (like 64 instances of 64 vertices each), So you will have SV_VertexID and SV_InstanceID as vertex shader input (each one representing row/column index)

Write boid position in the pixel as above (no additive this time, just a plain write).

Now just call GenerateMips on your texture, and your average position is in last mipmap.

So now since we use DirectX11 and have access to compute shaders, we might as well use them.

So here we are, compute shader way.

3/Dummy Loop 

Easiest technique to compute average is a simple dummy loop. 

You send a 1,1,1 dispatch, and here is the compute shader code:

Code Snippet

7. [numthreads(1,1,1)]
8. void CS_Average(uint3 dtid : SV_DispatchThreadID)
9. {
10.     float3 sum = 0;
11.     uint cnt, s;
12.     PositionBuffer.GetDimensions(cnt,s);
13.     for (uint i = 0; i < cnt; i++)
14.     {
15.         sum += PositionBuffer[i];
16.     }
17.     
18.     RWAverageBuffer[0] = sum * invcnt;
19.     
20. }

This (excluding simplicity), is an example on how NOT to use compute shaders.

You use a single thread which does all the job, so you have plenty of threads doing nothing and one doing big job, which is more like a serial algorithm.

But this will be useful at a later stage. Doing the whole calculation like that is a NO GO tho.

4/Iterative

Now let's improve that a bit. we want to use [numthreads(64,1,1)]

We have 4096 elements (eg: 64*64).

So what we'll do is the following:
Create a buffer with 64 elements.

Each of our threads will work on a part of the sum.

Code Snippet

2. StructuredBuffer<float3> PositionBuffer;
3.  
4. RWStructuredBuffer<float3> RWAverageBuffer : BACKBUFFER;
5.  
6. [numthreads(64,1,1)]
7. void CS_Average(uint3 dtid : SV_DispatchThreadID)
8. {
9.     float3 sum = 0;
10.     for (uint i = 0; i  < 64; i++)
11.     {
12.         uint idx = i * 64 + dtid.x;
13.         sum += PositionBuffer[idx];
14.     }
15.     
16.     RWAverageBuffer[dtid.x] = sum;
17. }
18.  
19. [numthreads(64,1,1)]
20. void CS_AverageTransposed(uint3 dtid : SV_DispatchThreadID)
21. {
22.     float3 sum = 0;
23.     for (uint i = 0; i  < 64; i++)
24.     {
25.         uint idx = dtid.x * 64 + i;
26.         sum += PositionBuffer[idx];
27.     }
28.     
29.     RWAverageBuffer[dtid.x] = sum;
30. }

So now we have a 64 elements buffer containing a part of that sum. But we made efficient use of your threads (please note that I show two read patterns , "row or column" based).

Now what we can simply do it run our dummy loop above, but it will only run on 64 elements.

So by decomposing like this and adding an extra dispatch, we allowed the first part to run MUCH faster, and leaving a very little job to do for our unefficient shader, which gives a (very) significant gain.

Let's see another way

5/Using groupshared and Thread Sync

Now let's look if we can do this in Compute and a Single pass. Since our element count is not that high it should quite easily allow it.

We've seen that we store temporary sum into a structured buffer. Now compute shader have a small memory space where they can share data (it's big enough to fit our 64 elements).

So here are declarations:

Code Snippet

1. float invcnt;
2. StructuredBuffer<float3> PositionBuffer;
3.  
4.  
5. RWStructuredBuffer<float3> RWAverageBuffer : BACKBUFFER;
6.  
7. //Used for local averages
8. groupshared float3 averages[64];

Here nothing that complicated, you can just notice the groupshared declaration to store temporary results.

Now here is Compute Shader code.

Code Snippet

10. [numthreads(64,1,1)]
11. void CS_Average(uint3 dtid : SV_DispatchThreadID)
12. {
13.     //Compute 64 averages in parallel
14.     float3 sum = 0;
15.     for (uint i = 0; i  < 64; i++)
16.     {
17.         uint idx = dtid.x * 64 + i;
18.         sum += PositionBuffer[idx];
19.     }
20.     
21.     averages[dtid.x] = sum;
22.     
23.     /*We need to wait for all threads to execute,
24.     so our groupshared is ready to use */
25.     GroupMemoryBarrierWithGroupSync();
26.     
27.     //Just make sure only one thread finish the job
28.     if (dtid.x > 0) { return ; }
29.     
30.     float3 endsum = 0;
31.     for (uint j = 0; j  < 64; j++)
32.     {
33.         endsum += averages[j];
34.     }
35.     
36.     RWAverageBuffer[0] = endsum * invcnt;
37. }

Here we do the same dispatch as above, but threads write into this temporary buffer instead of on the output.

Then to apply final pass, we need to wait for all threads to have finished to process their writes, which is what GroupMemoryBarrierWithGroupSync does.

It will block all threads until all have finished (and since in our case they do pretty much the same job, the stalling should be fairly minimal).

Now we keep only one thread for the rest of the execution (other ones have finished their job), which performs the last small loop, but reading from groupshared instead.

That's it, instead we've done in in a single pass!

Performance wise, it's more or less equivalent (except it saves us a second dispatch on CPU). In that scenario it saves us on dispatch and to create one buffer, which is always handy also.

Please note that something like 64*64 is some pretty ideal scenario which might not reflect real life, so this example will potentially require a bit more gymnastics.

Performance tuning with groupshared is fairly complex, so I advise to test iterative/group versions on your scenarios, with a very large number of element some efficient iterative algorithm might win (also this will be very architecture dependent).

Of course, we can notice that compute shader version would also work perfectly for min/max like operations (which can be useful for some other purposes).

That's it for now )

Shader Programming and Authoring

For this post i'll go into something a bit different, and speak about things in a more general way.

So we're in 2013, graphics card power has exploded and the "way to go" for real time graphics is shaders.

We see them everywhere, demos, new webgl fancy showcases, visual programming...

Cool thing with shaders (depending on environment you use), is they can easily be compiled on the fly, and you have reflection data to tweak parameters. That can make it an easy "designer friendly tool".

That of course create some issues. Creating bad shaders is easy. Creating good shader subsystem, or good advanced shaders is (very) hard. It's simple to copy paste and modify a random piece of hlsl/glsl/cg found on the net, tweak it to do (approximately) whatever you (kinda) want to do with it. No need for graphics API understanding (almost)

That brings another problem, most of your code base becomes a bulk of copy/paste bits of GPU code (that you don't really know what it does).

That's fine for basic post processors and fancy visuals like in the excellent shadertoy , and for random prototyping, but when you have advanced systems (fully fledged particles systems/geometry processors/compute shaders doing some heavy simulations, then it's a different kettle of fish).

So shader programming is no different than standard programming (in some aspects), you need to really understand how it works, have some coding guidelines and keep code pretty clean (and also know how parallel processing works, specially when you go into gpgpu eg Cuda/Compute/OpenCL).

People will always argue that strict guidelines makes things less tweakable, like having a proper predefined naming, includes and conditional compilation defines to modify shader, pipeline that does one job but very well instead of having a full shader from which you can change any single part if you want, I don't agree with that.

A clean system is easier to maintain, correct naming means all classes use the same base code, without need to change any variable name or semantic, adding properties to data means you only change relevant parts/add a conditional compile define instead of rewrite half of your code base, much easier to run a test compile (less files) and glue things together. It's not easy to do and takes time.

Let's take an example, procedural force field for particles.

Concept is simple as hell, for each particle, get position, compute force based on that position, accumulate to a force buffer (integrate later), or push to velocity right away (not ideal).

Now you can easily have 20+ functions like that. Copying 20 times all the cooking code is prohibitive (not mentioning that if you improve a little part outside of the function you need to copy paste code all the time. That's how most things are done in vvvv and is sucks (badly).

So includes implies some more strict guidelines (naming), but will save you a lot of time (and that's also what I call tweak-able).

For other type of functions (distance functions), you could use the same include in a Sphere Tracer and a particle collider at the same time.

And best of all, you can still use dynamic compilation (using include handlers feature in DirectX).

More advanced (dx11 only), use class linkage and allow several functions in the same handler that you can dynamically switch....

I'll show an example of this at some point, but that's a full topic.

One other thing about shaders is it's a piece of code, but what if you could design shaders on the fly like in vvvv?

For example you have a graph editor in Visual Studio 2012 (it's called DGSL). You can edit your shader via nodes.

Nice isn't it? Not really...

Visual Shader programming is not an easy thing to achieve (as Josh Petrie and other people pointed out in their blog), fitting a feature set which is not too minimal (10 nodes and clicks instead of 2 lines of code), or some nodes which are so complex that you would not need a graph anyway, it's a very hard balance to get.

You mostly end up with a very minimal feature set (like some pixel based material), or have such a low level implementation that it kinda takes twice the time (compared to an efficient code editor with good reflection).


Example 1:
float4 result = a+b;

Why do you need an editor for that? ))

Example 2:
float3 v = cross(v1,v2);

If you don't know what a cross product does, doing it via code or patch will not make any difference.

Example 3:
float3 color = CookTorrance(materialdata); (Patch Cook Torrance with operators)

Patching that with nodes would be a crappy mess, you'd rather have a prebuilt function for it (but then some people will complain they can't tweak...).

Example 4:
float3 color = CookTorrance(materialdata); (Cook Torrance as built in node)

Well just add an include and you go back to example 1.

So in any case (low/high level), I still find it hard to see any decent benefit (not mentioning generally looking at resulting code means any coder will just rewrite it from scratch instead of tweak it).

Also HLSL is still a "minimal" language (compared to java/c#/c++), functions are not that many, no big framework and namespaces, so it's much easier to go into reference page and learn what they do.

So personally I think proper Shader editors with good reflectors, are a much nicer way for authoring.