OpenGL Compute Shader Shared Maximum

Question

I'm working on an OpenGL compute shader in which each work item results in a single number output I'll call x, as well as a struct output with more information, I'll call y. What I would like is a single output for each work group being the y of the work item with the maximum x.

Now I'm aware of the GLSL atomic operations and I believe I could easily get the maximum x, but I'm having trouble thinking of how to get the y associated with the maximum x. I could, in the compute shader, do a conditional right after I check for maximum x to check if x changed and change y accordingly, but I believe there is no guarantee that no other work item has replaced the maximum x at that point. I think this might be possible with memory barriers but I'm having trouble figuring out if it really is.

So I guess my question is, is there an established method to do something like this? Am I perhaps over complicating it? Is there a way, with memory barriers, to create critical section-like behavior? Do I need to do the maximums on the CPU or in another serial compute shader?

Answer 1

You can figure out which thread has the max value by modifying x: pack gl_LocalInvocationIndex in the least significant bits of x. The number of bits you need for the index depends on your group size.

If you need all 32 bits of x then I suggest using 2 compute shaders - first record max per group. Then compute x again and compare.

Answer 2

One way to do it: first find the maximum x using atomics on a shared variable. Then, have each thread compare its local version of x to the found maximum, and store to y only if they are equal.

shared uint x, y;
...
uint localX, localY;
// each thread computes its localX and localY
atomicMax(x, localX);
barrier();  // ensure all threads have done the atomicMax before going on
if (x == localX)
{
    atomicExchange(y, localY);
}
barrier();
// now you can read the final x and y values

This should work even if there are multiple threads with the same maximum value of x, as the stores to y are atomic, so you'll just end up with an arbitrary one of them "winning".

A variation on this, which may be useful if y is a larger struct of multiple pieces of data and therefore can't be atomically stored natively, is to use the local invocation index to pick the "winning" thread.

shared uint x, winningThread;
shared MyStruct y;
...
uint localX;
MyStruct localY;
// each thread computes its localX and localY
atomicMax(x, localX);
barrier();  // ensure all threads have done the atomicMax before going on
if (x == localX)
{
    atomicExchange(winningThread, gl_LocalInvocationIndex);
}
barrier();
if (winningThread == gl_LocalInvocationIndex)
{
    y = localY;  // only one thread will ever do this store, so doesn't need to be atomic
}
barrier();
// now you can read the final x and y values