GLSL Vulkan compute shader to efficiently prune zeros from a shared array to make a compressed array

user_1439414 0
Viewed 398

I have a vulkan compute shader with an array shared inside the local group and I want to perform the following transform: Vulkan Shader Zero removal from array Basically, I want to remove/prune all the zeros. Is there a fast or parallel method to do this? I tried to do this in series as follows

            shared int arraySize;
            shared int array[256];
            shared int compressed_array[256];

            /*... prepare array in parallel ... */

            // run in series on 1st worker 
            if(gl_LocalInvocationID.x == 0 && gl_LocalInvocationID.y == 0){
               arraySize= 0; // initilize arraySize
                for (int i = 0; i < 256; i++) { 
                    if(array[i] > 0) // incrementally search for non-zeroes
                    {
                        compressed_array[arraySize] = array[i];
                        arraySize= arraySize + 1;
                    }
                }
            }

but it seems to take 1-2[ms] with 256 elements of the array on my GPU, is there any faster way to do this? A parallel algorithm would presumably be faster, does such an algorithm exist?

vulkan glsl shader parallel-processing algorithm
2 Answers

Thanks to Yuri Kilochek's answer, I was able to find a solution via parallel prefix-sums/scan

Suppose a 'flag' array was added to the data that is 1 if the corresponding array cell is non-zero and 0 otherwise. Then a 'parallel exclusive scan' on the flag array will yield the index of the compressed_array to which invocations with an active flag should write their respective 'array' contents to (scatter operation). enter image description here

In Vulkan this can be implemented efficiently using subgroups.

However, each subgroup can typically only perform scans up to 32 (Nvidia) or 64 (AMD) elements long while the local group may be several times larger. To perform scans over the whole local group, a layered approach of scans as described here and coded here is necessary.

user_14394140

Yes. This problem is called parallel stream compaction.

user_15540200
Related