I am calculating the Summed Area Table(SAT) of a texture with help of a compute shader in OpenGL. The texture which needs to be summed, has a dimension size of more than my GPU supports (GL_MAX_COMPUTE_WORK_GROUP_SIZE).
Right now I am trying to do this with two steps. First build the sum for each row, in a 2nd step build the sum for each column using the first result.
To simply explane how it is working, I only write down the horizontal calculation, because the vertical works in the same way.
My workGroupSize is 1024 * 1 * 1 (the maximum my GPU supports) and each workgroup has its own row.
This is how it works: First, each invocation loads its pixel from the texture and stores the result into a shared array. Then a invocation synchronization of a workgroup (barrier();) is performed within the shader. After the texture row has been stored to the shared memory, the invocations group themself into blocks with size of potentials of 2 beginning with 2, 4, 8, 16... the sum will be stored to the shared memory and a synchronization manages, that the next iteration can read without conflicts the last value of the previous block. This value needs to be summed to each arrayindex of the shared array within the block. With this technique I only have one pixel read per invocation and log2(textureSize.x) iterations of calculation.
The big problem is, that when the texture size if larger than 1024 pixels, then the algorithm needs that all workgroups are synchronized to read out the left neighboring blocks last result. Which can be stored to SSBO...
Here my code to calculate one row per workgroup:
layout (local_size_x = 1024, local_size_y = 1, local_size_z = 1) in;
shared float sat[1024];
void main()
{
uvec4 value;
if(pass == 0) //sat horizontal
value = imageLoad(textureBase, ivec3(gl_GlobalInvocationID.xy,0));
else //sat vertical
value = imageLoad(textureBase, ivec3(gl_GlobalInvocationID.yx,0));
sat[gl_LocalInvocationIndex] = uintBitsToFloat(value.x);
barrier(); //until here, the SAT is initialized.
for(int i = 0; i < log2(1024); ++i)
{
int size = int(pow(2, i+1));
int locationGroup = int(mod(int(gl_LocalInvocationIndex), size));
int doAdd = locationGroup >= size / 2 ? 1 : 0;
int addIndex = int(gl_LocalInvocationIndex) - (locationGroup - size / 2) - 1;
barrier();
float valueToAdd = sat[addIndex];
barrier();
if(doAdd == 1)
{
sat[gl_LocalInvocationIndex] += valueToAdd;
}
barrier();
}
uint result = floatBitsToUint(sat[gl_LocalInvocationIndex]);
imageStore(textureBase, ivec3(gl_GlobalInvocationID.xy,0), uvec4(gl_LocalInvocationIndex,0,result,0));
if(pass == 0) //sat horizontal
imageStore(textureBase, ivec3(gl_GlobalInvocationID.xy,0), uvec4(result,0,0,0));
else //sat vertical
imageStore(textureBase, ivec3(gl_GlobalInvocationID.yx,0), uvec4(result,0,0,0));
}
When having a 2048x2048 texture, two workgroups would calculate the result of one row (1st [0, 1024) 2nd [1024, 2048) ). At the end of this shader program, the SAT of each 1024 block has finished. The next step would be reading the 1023th value of the previous (left) neighboring workgroup and add this value to each other value within its shared array.
How can I synchronize the workgroups, so that at the end of this code they will be synchronized to then load the last value of the previous block?
All invocations of all workgroups have the same number of barrier().