ordenación rápida en GLSL?

Question

Estoy considerando portar una gran parte del procesamiento de la GPU mediante un sombreado GLSL. Uno de los problemas inmediatos que tropezamos es que en uno de los pasos, el algoritmo necesita mantener una lista de elementos, clasificarlos y tomar las pocas más grandes (cuyo número depende de los datos). En la CPU Esto se hace simplemente utilizando un vector de STL y qsort () pero en GLSL no tengo este tipo de instalaciones. ¿Hay una manera de hacer frente a esta deficiencia?

Answer 1

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

.

A 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 una pequeño conjunto de datos y cada fragmento tiene su propio conjunto de datos para ordenar. Más como tratar de hacer la mediana de filtrado 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 que las personas han pasado carreras preocuparse de que es el mejor algoritmo de clasificación de grandes bases de datos, para N pequeño que realmente no importa si usted utiliza ordenamiento rápido, Pila Ordena, Radix Ordena, Shell Ordena, optimizado ordenamiento de burbuja, la burbuja no optimizado especie, etc. por lo menos, no importa mucho en una CPU.

GPU son dispositivos SIMD, por lo que les gusta tener cada núcleo de ejecución de las mismas operaciones en el paso de bloqueo. Los cálculos son baratos, pero las ramas son ramas costosos y dependientes de los datos que cada núcleo filiales de una manera diferente es muy, muy, muy, caro.

Así que si cada núcleo tiene su propio pequeño conjunto de datos para ordenar, y el # de los datos para ordenar depende de los datos y podría ser un número diferente para cada núcleo, es probablemente mejor de la selección de un tamaño máximo (si es posible ), el relleno de las matrices con Infinity o alguna gran número, y teniendo cada núcleo realizan la misma especie exacta, lo que sería una burbuja sin sucursales sin optimizar especie, algo como esto:

Pseudocódigo (ya 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 segura de que estaba buscando un algoritmo de ordenación rápida o un algoritmo de ordenación rápida. El algoritmo en el artículo utiliza ordenamiento por mezcla ...

Answer 3

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

que haría uso de heapsort lugar de la clasificación rápida, porque dijiste que sólo tiene que mirar en la parte superior unos valores. El montón se puede construir en el tiempo O(n), pero conseguir el valor superior es log(n). Por lo tanto, si el número de valores que necesita es significativamente menor que el número total de elementos que podría ganar algo de rendimiento.