quick sort in GLSL?

Question

Sto pensando di porting un grande pezzo di elaborazione per GPU utilizzando uno shader GLSL. Uno dei problemi immediati mi sono imbattuto è che in uno dei passi, l'algoritmo ha bisogno di mantenere una lista di elementi, ordinarli e prendere i pochi quelli più grandi (il cui numero dipende i dati). Sulla CPU Questo viene fatto semplicemente utilizzando un vettore STL e qsort (), ma in GLSL non ho tali strutture. Esiste un modo per affrontare questa carenza?

Answer 1

Disclosure: Io davvero non so GLSL - ho fatto la programmazione GPGPU con l'AMD Stream SDK, che ha diverso linguaggio di programmazione

.

Da di commentare la risposta di Bjorn, mi risulta che si è non interessati a utilizzare la GPU per ordinare un enorme database - come la creazione di una rubrica telefonica inversa o qualsiasi altra cosa, ma invece, si dispone di un piccolo set di dati e ogni frammento ha il proprio set di dati è di per ordinare. Altri come cercare di fare il filtraggio mediano pixel?

Posso solo dire in generale:

Per i piccoli insiemi di dati, l'algoritmo di ordinamento in realtà non importa. Mentre le persone hanno speso una carriera preoccuparsi che è il miglior algoritmo di ordinamento per database di grandi dimensioni, per la piccola N in realtà non importa se si utilizza quick sort, Mucchio Sort, Radix Sort, Shell Ordina, ottimizzata Bubble Sort, non ottimizzato bubble sort, ecc almeno non importa molto su una CPU.

GPU

sono dispositivi SIMD, così come avere ogni kernel eseguire le stesse operazioni in fase di bloccaggio. I calcoli sono a buon mercato, ma i rami sono i rami costosi e dipendenti dai dati in cui ogni kernel Branchs un modo diverso è molto, molto, molto, costoso.

Quindi, se ogni kernel ha proprio piccolo set di dati è di per ordinare, e il # dei dati per ordinare è dati dipendenti e potrebbe essere un numero diverso per ogni kernel, siete probabilmente meglio scegliere una dimensione massima (se potete ), imbottitura le matrici con l'infinito o un gran numero, e se ogni kernel eseguire esattamente lo stesso tipo, che sarebbe un non ottimizzata bolla senza rami specie, qualcosa di simile a questo:

Pseudocodice (dal momento che non so GLSL), sorta di 9 punti

#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

Avete visto questo articolo? https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

Non ero sicuro che stavate cercando un algoritmo Quicksort o un algoritmo di ordinamento rapido. L'algoritmo in questo articolo utilizza merge sort ...

Answer 3

non ho alcuna conoscenza di programmazione GPU.

userei heapsort piuttosto che Quicksort, perché hai detto che solo bisogno di guardare le prime pochi valori. Il mucchio può essere costruito nel tempo O(n), ma ottenere il valore superiore è log(n). Quindi se il numero di valori necessari è significativamente più piccolo rispetto al numero totale di elementi si potrebbe guadagnare un po 'le prestazioni.