GLSL Vulkan 计算着色器可有效地从共享数组中删除零以生成压缩数组

Question

我有一个 vulkan 计算着色器，在本地组内共享一个数组，我想执行以下转换：基本上，我想 remove/prune 所有零。有没有快速或并行的方法来做到这一点？我尝试按如下方式按顺序执行此操作

            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;
                    }
                }
            }

但是在我的 GPU 上使用数组的 256 个元素似乎需要 1-2[ms]，有没有更快的方法来做到这一点？并行算法可能会更快，是否存在这样的算法？

Answer 1

是的。这个问题叫做 parallel stream compaction.

Answer 2

感谢 Yuri Kilochek 的回答，我能够通过并行找到解决方案 prefix-sums/scan

假设一个 'flag' 数组被添加到数据中，如果相应的数组单元格非零则为 1，否则为 0。然后标志数组上的“并行独占扫描”将产生 compressed_array 的索引，具有活动标志的调用应将其各自的 'array' 内容写入（分散操作）。

在 Vulkan 中，这可以使用 subgroups.

高效实现

但是，每个子组通常只能执行长达 32 (Nvidia) 或 64 (AMD) 个元素的扫描，而本地组可能大几倍。要对整个本地组执行扫描，需要采用 described here and coded here 的分层扫描方法。

GLSL Vulkan 计算着色器可有效地从共享数组中删除零以生成压缩数组

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

algorithm

parallel-processing

shader

glsl

vulkan