GLSL Vulkan вычисляет шейдер для эффективного удаления нулей из общего массива для создания сжатого массива

Question

У меня есть вычисляющий шейдер vulkan с общим массивом внутри локальной группы, и я хочу выполнить следующее преобразование: Удаление Vulkan Shader Zero из массива В принципе, я хочу удалить / обрезать все нули. Есть ли быстрый или параллельный способ сделать это? Я попытался сделать это последовательно, как показано ниже

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

, но кажется, что это займет 1-2 [мс] с 256 элементами массива на моем GPU. Есть ли более быстрый способ сделать это? Предположительно, параллельный алгоритм будет быстрее, существует ли такой алгоритм?

Answer 1

Благодаря ответу Юрия Килочека я смог найти решение с помощью параллельного prefix-sums / scan

Предположим, к данным был добавлен массив «флаг», который равен 1, если соответствующая ячейка массива не равна нулю, иначе 0. Затем « параллельное исключительное сканирование » в массиве флагов даст индекс compressed_array, в который вызовы с активным флагом должны записывать свое соответствующее содержимое «массива» (операция разброса).

In Vulkan this can be implemented efficiently using подгруппы .

Однако каждая подгруппа обычно может выполнять сканирование только до 32 (Nvidia) или 64 (AMD) элементов, в то время как локальная группа может быть в несколько раз больше. Чтобы выполнить сканирование всей локальной группы, необходим многоуровневый подход сканирования как , описанного здесь, и , кодированного здесь .

Answer 2

Да. Эта проблема называется сжатие параллельного потока .