Qualcuno può fornirmi un algoritmo parallelo per il calcolo della fattorizzazione sparsa di Cholesky? Deve essere adatto per l'esecuzione su una GPU. Qualsiasi risposta in CUDA, OpenCL o persino in pseudo-codice sarebbe molto apprezzata.Algoritmo di fattorizzazione Cholesky sparse per GPU
In generale, i metodi di spargimento diretto non sono particolarmente adatti per la GPU. Mentre i migliori risolutori diretti (pensando a pacchetti come CHOLMOD, SuperLU, MUMPS qui) usano strategie per generare sottoinsiemi densi che possono essere processati usando L3 BLAS, le dimensioni e la forma dei blocchi non tendono a trarre profitto dall'uso di un BLAS GPU per accelerazione. Ciò non significa che non possa essere fatto, solo che i miglioramenti delle prestazioni potrebbero non valerne la pena.
Vedendo come si sta chiedendo una scarsità di fattorizzazione di Cholesky, ho assunto che la matrice sia definita positiva simmetrica. In tal caso, potresti prendere in considerazione l'utilizzo di un risolutore iterativo - ci sono un certo numero di buone implementazioni del Gradiente coniugato e di altri metodi di subspace di Krylov con precondizionatori semplici che potrebbero essere di qualche utilità. La libreria Cusp per CUDA potrebbe valere la pena di indagare se il tuo problema è suscettibile di metodi iterativi. La libreria ViennaCL offre qualcosa di simile se stai cercando OpenCL.
Ho intenzione di provare il metodo Conjugate Gradient all'inizio. Grazie! –
Dai un'occhiata a questi articoli, per gentile concessione di ACM (SC'08 e PPoPP '09 sono eccellenti conferenze).
V. Volkov, J. W. Demmel. Benchmarking GPU per accordare l'algebra lineare densa. SC'08.
Jung, J.H., O'Leary, D.P. Decomposizione di Cholesky e programmazione lineare su una GPU. Scholarly Paper, University di Maryland, 2006.
G. Quintana-Orti, F. D. Igual, E. S. Quintana-Orti, R. A. van de Geijn. Risoluzione di sistemi lineari densi su piattaforme con più acceleratori hardware. PPoPP '09.
Se non si ha accesso a questi tramite ACM Portal/DL, potrebbero essere online da qualche parte. Altrimenti ... Probabilmente potrei citare alcune delle sezioni più rilevanti, con citazioni, e farne un uso corretto.
MODIFICA:
Controllare questo fuori forse?
EDIT2: perso la parte di "sparse".
Guardando in giro online e all'ACM/IEEE, non vedo molto che mi salti addosso. Quello che vedo non sembra promettente ... potrebbe non essere un calcolo in cui si vede un grande beneficio dall'utilizzo della GPU.
Questi riferimenti sembrano tutti per la fattorizzazione a matrice densa. Gli algoritmi per la scomposizione sparsa sono un po 'diversi ... –
Oh, totalmente mancato nella domanda. Prenderò un altro sguardo ... – Patrick87
L'algoritmo multifrontale sembra essere una scelta popolare per la fattorizzazione sparsa parallela. Controlla il pacchetto MUMPS, here.
Come ho capito, il codice fa ampio uso di chiamate di livello 3 BLAS (DGEMM e così via) per ottenere prestazioni elevate. Vorrei verificare se è possibile eseguire il collegamento a un'implementazione GPU basata su BLAS, ad esempio CUDA BLAS o simili se si desidera utilizzare il proprio GPU anziché FPU.
Contrariamente alla densa fattorizzazione, i metodi sparsi includono sempre una quantità non trascurabile di lavoro intero oltre al lavoro in virgola mobile (sebbene il punto in virgola mobile sia ancora dominante). Non sono esperto su GPU's, ma il CPU dovrebbe essere più adatto per il lavoro su interi rispetto allo GPU ?? Questo potrebbe essere un argomento contro l'implementazione dell'intero algoritmo per il GPU ...
Spero che questo aiuti.
La cosa intera, di per sé, non è un argomento contro GPU. Detto questo, schemi di accesso/strutture di dati irregolari di memoria (ad esempio con puntatori) e/o flusso di controllo divergente/ramificato sono argomenti validi contro l'uso della GPU. Non sono esperto di fattispecie Cholesky sparse, ma facendo Cholesky sparse è praticamente il bambino poster per accesso irregolare alla memoria e flusso di controllo divergente, giusto? – Patrick87
@ Patrick87 - Buoni punti. Come ho già detto sopra, non avrei dovuto essere così specifico nella mia domanda. Farà qualsiasi algoritmo per risolvere un sistema simmetrico di equazioni lineari sparse. –
@Pat: i buoni algoritmi (ad esempio multi-frontali, supernodali, ecc.) Utilizzano aggiornamenti "bloccati", almeno per il lavoro in virgola mobile, in cui la sub-struttura semi-densa consente l'uso di densi kernel (cioè routine 'BLAS') . La fase iniziale "simbolica" iniziale generalmente implica l'accesso irregolare, per quanto ho capito. –
Le fattorizzazioni di Cholesky sparse su una GPU sono un problema aperto. Anche il Linear Programmingpaper menzionato in precedenza utilizza un algoritmo denso mentre la maggior parte dei problemi è scarsa. Il mercato del solutore LP commerciale è molto competitivo, ma nessuno ha un prodotto che faccia ancora molto uso della GPU.
Vedere UHM - Solver Hyper Matrix non assemblato. Può calcolare la fattorizzazione di Cholesky sparsa utilizzando più GPU su un host.
Invia qualche pseudo-codice per farlo su un normale uniprocessore, e sarei felice di discutere di portarlo sulla GPU. Inoltre, questo è probabilmente qualcosa che esiste già ... fammi fare una ricerca veloce. Aha. Vedi la mia risposta qui sotto. – Patrick87
Deve essere una fattorizzazione di Cholessky? In generale, i metodi iterativi che possono sfruttare un'implementazione spMV ad alte prestazioni sono molto più adatti alle GPU che risolvono i risolutori. – talonmies
@talonmies - Ah! Non avrei dovuto essere così specifico. Quello di cui ho veramente bisogno è un algoritmo che risolva un sistema simmetrico sparso di equazioni lineari. La fattorizzazione di Cholesky è ciò che viene attualmente utilizzato per risolvere questo problema. Tuttavia, nel caso della GPU, se altri algoritmi sono più appropriati, sono aperto a questo. –