Clasificación rápida en GLSL?

Question

Estoy considerando transferir un gran fragmento de procesamiento a la GPU usando un sombreador GLSL. Uno de los problemas inmediatos que tropecé es que en uno de los pasos, el algoritmo necesita mantener una lista de elementos, ordenarlos y tomar los pocos más grandes (cuyo número depende de los datos). En la CPU esto simplemente se hace usando un vector STL y qsort() pero en GLSL no tengo tales facilidades. ¿Hay alguna manera de lidiar con esta deficiencia?

Answer 1

Divulgación: Realmente no sé GLSL - He estado haciendo programación GPGPU con AMD Stream SDK, que tiene un lenguaje de programación diferente.

partir de comentar sobre la respuesta de Bjorn, tengo entendido que son no interesado en utilizar la GPU para ordenar una enorme base de datos - como la creación de una guía telefónica inversa o lo que sea, pero en su lugar, usted tiene un pequeño conjunto de datos y cada fragmento tiene su propio conjunto de datos para ordenar. ¿Más como tratar de hacer un filtrado medio de píxeles?

sólo puedo decir en general:

Para los pequeños conjuntos de datos, el algoritmo de ordenación realmente no importa. Mientras las personas han dedicado su carrera a preocuparse por cuál es el mejor algoritmo de ordenamiento para bases de datos muy grandes, para N pequeña no importa si usa Clasificación rápida, Clasificación de pila, Clasificación de columna, Clasificación de burbuja, Clasificación de burbuja optimizada, Clasificación de burbuja no optimizada, etc. Al menos no importa mucho en una CPU.

Las GPU son dispositivos SIMD, por lo que les gusta que cada kernel ejecute las mismas operaciones en el paso de bloqueo. Los cálculos son baratos, pero las ramas son costosas y las sucursales dependientes de los datos, donde cada núcleo se ramifica de una manera diferente, es muy, muy, muy costoso.

Así que si cada núcleo tiene su propio pequeño conjunto de datos para ordenar, y el número de datos a ordenar depende de los datos y podría ser un número diferente para cada núcleo, probablemente sea mejor elegir un tamaño máximo (si can), rellenando las matrices con Infinity o algún número grande, y haciendo que cada kernel realice exactamente el mismo género, que sería una clasificación de burbuja sin sucursales no optimizada, algo como esto:

Pseudocódigo (ya que no sé GLSL) , una especie de 9 puntos

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; } 
for (size_t n = 8; n ; --n) { 
    for (size_t i = 0; i < n; ++i) { 
    TwoSort (A[i], A[i+1]); 
    } 
} 

Answer 2

¿Has visto este artículo? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

No estaba seguro de que estuviera buscando un algoritmo Quicksort o un algoritmo de ordenación rápido. El algoritmo en el artículo usa tipo de fusión ...

Answer 3

no tengo ningún conocimiento acerca de la programación de la GPU.

Utilizaría heapsort en lugar de quicksort, porque dijiste que solo necesitas mirar los primeros valores. El montón se puede construir en el tiempo O(n), pero obteniendo el valor superior es log(n). Por lo tanto, si la cantidad de valores que necesita es significativamente menor que la cantidad total de elementos, podría obtener algún rendimiento.