Ho dovuto risolvere un problema piuttosto standard sulla GPU, ma sono abbastanza nuovo per la pratica GPGPU, quindi sono alla ricerca di idee per affrontare questo problema.Riduzione segmentata con segmenti sparsi
Ho molti punti in 3-spazio che sono assegnati a un numero molto piccolo di gruppi (ogni punto appartiene a un gruppo), in particolare 15 in questo caso (non cambia mai). Ora voglio calcolare la matrice di media e covarianza di tutti i gruppi. Così sulla CPU è più o meno lo stesso di:
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
Poiché il numero dei gruppi è estremamente piccolo, l'ultimo passo può essere fatto sulla CPU (Ho bisogno di quei valori della CPU, in ogni caso). Il primo passo è in realtà solo una riduzione segmentata, ma con i segmenti sparsi in giro.
Quindi la prima idea che mi è venuta in mente era quella di ordinare prima i punti in base ai loro gruppi. Ho pensato a un ordinamento del bucket semplice utilizzando atomic_inc per calcolare le dimensioni della benna e gli indici di rilocazione per punto (ho un'idea migliore per l'ordinamento ?, l'atomica potrebbe non essere la migliore idea). Dopo di che sono ordinati per gruppi e potrei eventualmente trovare un adattamento degli algoritmi di scansione segmentati presentati here.
Ma in questo caso speciale, ho ottenuto una grande quantità di dati per punto (9-10 float, forse anche doppio se necessario), quindi gli algoritmi standard che utilizzano un elemento di memoria condivisa per thread e thread per punto potrebbe creare problemi relativi alle risorse per multiprocessore come memoria o registri condivisi (Ok, molto altro sulla capacità di calcolo 1.x rispetto a 2.x, ma comunque).
A causa del numero molto piccolo e costante di gruppi, ho pensato che ci potrebbero essere approcci migliori. Forse esistono già idee adatte a queste specifiche proprietà di un problema di questo tipo. O forse il mio approccio generale non è poi così male e hai idee per migliorare i singoli passaggi, come un buon algoritmo di ordinamento adatto per un numero molto piccolo di chiavi o un algoritmo di riduzione segmentato che minimizza l'uso di memoria condivisa/registro.
Sto cercando approcci generali e non voglio usare librerie esterne. FWIW Sto usando OpenCL, ma non dovrebbe avere molta importanza in quanto i concetti generali di GPU computing non differiscono in realtà sui principali framework.
Questo è un modello piuttosto comune. Usando Thrust, dovresti dapprima 'sort_by_key' per mettere insieme i dati in ogni segmento, e quindi' reduce_di_key' per calcolare la media e la covarianza di ciascun gruppo. –