Come rimuovere valori zero da una matrice in parallelo

Question

Come rimuovere in modo efficiente i valori zero da una matrice in parallelo utilizzando CUDA. Le informazioni sul numero di valori zero sono disponibili in anticipo, che dovrebbe semplificare questa operazione.

È importante che i numeri rimangano ordinati come nell'array sorgente, durante la copia nell'array risultante.

---

Esempio:

sull'array, ad esempio contenere i seguenti valori: [0, 0, 19, 7, 0, 3, 5, 0, 0, 1] con le informazioni aggiuntive che 5 valori sono zeri. Il risultato finale desiderato sarebbe allora altro array contenente: [19, 7, 3, 5, 1] ​​

Answer 1

Per eliminare alcuni elementi di una matrice è possibile utilizzare Thrust Library's compaction operations. Dato un predicato is_not_zero, che restituisce false per valori zero, e true per gli altri, è possibile scrivere l'operazione simili

thrust::copy_if(in_array, in_array + size, out_array, is_not_zero); 

matrice di output includerà solo i valori che sono non-zero, perché il predicato indica così .

Si può anche utilizzare la funzione "remove_if" con un predicato inversa che restituiscono true per zeri, e false per gli altri ..

thrust::remove_if(in_array, in_array + size, is_zero); 

vi consiglio di dare un'occhiata a esempi di compattazione della biblioteca di spinta, o generale concetto di compattazione.

http://code.google.com/p/thrust/source/browse/examples/stream_compaction.cu

Answer 2

Che dire di una variante del merging odd-even ordinamento, o di fatto qualsiasi algoritmo di ordinamento, in cui l'ordinamento è definita da a < b === (a != 0 && b == 0)?

Answer 3

Se non si desidera utilizzare di spinta e si preferisce utilizzare CUDA, probabilmente la cosa migliore da fare è eseguire Sum Scan, descritto in dettaglio qui

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter36.html