Ordinamento rapido in GLSL?

Question

Sto valutando la possibilità di trasferire una grande porzione di elaborazione sulla GPU utilizzando uno shader GLSL. Uno dei problemi immediati in cui mi sono imbattuto è che in uno dei passaggi, l'algoritmo deve mantenere un elenco di elementi, ordinarli e prendere i più grandi (il cui numero dipende dai dati). Sulla CPU questo è fatto semplicemente usando un vettore STL e qsort() ma in GLSL non ho tali servizi. C'è un modo per affrontare questa carenza?

Answer 1

Disclosure: Non so davvero GLSL - Ho eseguito la programmazione GPGPU con AMD Stream SDK, che ha un linguaggio di programmazione diverso.

Da di commentare la risposta di Bjorn, mi risulta che tu sei non interessati ad utilizzare la GPU per ordinare un enorme database - come la creazione di una rubrica telefonica inversa o qualsiasi altra cosa, ma invece, hai un insieme di dati e ciascuno frammento ha il proprio set di dati da ordinare. Più come provare a fare filtraggio pixel mediano?

posso solo dire in generale:

Per i piccoli insiemi di dati, l'algoritmo di ordinamento in realtà non importa. Mentre le persone hanno speso carriere preoccuparsi di quale sia il miglior algoritmo di ordinamento per database di grandi dimensioni, per N piccoli non importa se si utilizza Ordinamento rapido, Ordinamento heap, Ordinamento radice, Ordinamento shell, Ordinamento bolla ottimizzato, Ordinamento Bubble non ottimizzato, ecc. Almeno non importa molto su una CPU.

Le GPU sono dispositivi SIMD, quindi preferiscono che ciascun kernel esegua le stesse operazioni in blocco. I calcoli sono economici ma i rami sono costosi e le diramazioni dipendenti dai dati, dove ogni kernel si dirama in un modo diverso, sono molto, molto, molto costosi.

Quindi, se ogni kernel ha il proprio set di dati di piccole dimensioni da ordinare e il numero di dati da ordinare dipende dai dati e potrebbe essere un numero diverso per ogni kernel, probabilmente è meglio scegliere una dimensione massima (se si può), riempire gli array con Infinity o un numero elevato e fare in modo che ogni kernel esegua esattamente lo stesso ordinamento, che sarebbe un ordinamento bubble senza branching non ottimizzato, qualcosa del genere:

Pseudocodice (dal momento che non conosco il 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

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

io non ero sicuro che stavate cercando un algoritmo Quicksort o un algoritmo di ordinamento rapido. L'algoritmo nell'articolo utilizza l'unione di ordinamento ...

Answer 3

non ho alcuna conoscenza di programmazione GPU.

Vorrei usare heapsort anziché quicksort, perché hai detto che devi solo guardare i primi valori. L'heap può essere costruito nel tempo O(n), ma il valore massimo è log(n). Pertanto, se il numero di valori necessario è significativamente inferiore al numero totale di elementi, è possibile ottenere un certo rendimento.