¿Alguien puede proporcionarme un algoritmo paralelo para calcular la factorización de Cholesky dispersa? Debe ser adecuado para la ejecución en una GPU. Cualquier respuesta en CUDA, OpenCL, o incluso pseudocódigo sería muy apreciada.Algoritmo de factorización de Cholesky disperso para GPU
Hablando en general, los métodos directos dispersos no son una gran opción para la GPU. Mientras que los mejores solucionadores directos (pensando en paquetes como CHOLMOD, SuperLU, MUMPS aquí) usan estrategias para generar subbloques densos que pueden procesarse utilizando L3 BLAS, el tamaño y la forma de los bloques no suelen beneficiarse del uso de una GPU BLAS para la aceleración. No significa que no se puede hacer, solo que las mejoras en el rendimiento pueden no valer la pena.
Al ver que está preguntando sobre una factorización de Cholesky dispersa, asumí que la matriz es positiva simétrica definida. En ese caso, podría considerar el uso de un solucionador iterativo: hay varias implementaciones buenas de Graduate conjugado y otros métodos de subespacio de Krylov con precondicionadores simples que pueden ser de alguna utilidad. La biblioteca Cusp para CUDA podría valer la pena investigar si su problema es susceptible a métodos iterativos. La biblioteca ViennaCL ofrece algo similar si está buscando OpenCL.
Voy a probar el método de Degradado conjugado para comenzar. ¡Gracias! –
Eche un vistazo a estos artículos, cortesía del ACM (SC'08 y PPoPP '09 son conferencias excelentes).
V. Volkov, J. W. Demmel. Benchmarking GPUs para sintonizar álgebra lineal densa. SC'08.
Jung, J.H., O'Leary, D.P. Descomposición de Cholesky y Programación lineal en una GPU. Scholarly Paper, Universidad de Maryland, 2006.
G. Quintana-Orti, F.D. Igual, E.S. Quintana-Orti, R.A. van de Geijn. Solución de sistemas lineales densos en plataformas con múltiples aceleradores de hardware. PPoPP '09.
Si no tiene acceso a estos a través del Portal/DL de ACM, es posible que estén en línea en alguna parte. De lo contrario ... probablemente pueda citar algunas de las secciones más relevantes, con citas, y que sean de uso legítimo.
EDITAR:
¿Lo puede ver?
Edit2: la falta de la parte de "escasa".
Mirando en línea y en el ACM/IEEE, no veo mucho que salte hacia mí. Lo que veo no suena prometedor ... esto podría no ser un cálculo en el que se vean muchos beneficios al usar la GPU.
Todas estas referencias parecen ser para la factorización de matriz densa. Algoritmos para la descomposición escasa son un poco diferentes ... –
Oh, lo extrañé por completo en la pregunta. Voy a echar otro vistazo ... – Patrick87
El algoritmo multi-frontal parece ser una opción popular para la factorización dispersa paralela. Consulte el paquete MUMPS, here.
Según tengo entendido, el código hace un uso extensivo de llamadas de nivel 3 BLAS (DGEMM y etc.) para lograr un alto rendimiento. Investigaría si es posible vincular a una implementación GPU basada en BLAS, como CUDA BLAS o similar si está interesado en usar su GPU en lugar de FPU.
Contrariamente a la factorización densa, los métodos dispersos siempre incluyen una cantidad no despreciable de enteros además del trabajo de coma flotante realizado (aunque el punto flotante sigue siendo dominante). No soy un experto en GPU's, pero ¿sería mejor el CPU para un trabajo entero que el GPU? Este podría ser un argumento en contra de implementar todo el algoritmo para el GPU ...
Espero que esto ayude.
El entero, por sí mismo, no es un argumento en contra de las GPU. Dicho esto, los patrones de acceso a memoria irregulares/estructuras de datos (por ejemplo, con punteros) y/o flujo de control de ramificación/divergencia son argumentos fuertes contra el uso de la GPU. No soy un experto en factorizaciones dispersas de Cholesky, pero hacer Cholesky disperso es más o menos el ejemplo de acceso irregular a la memoria y flujo de control divergente, ¿verdad? – Patrick87
@ Patrick87 - Buenos puntos. Como comenté anteriormente, no debería haber sido tan específico en mi pregunta. Cualquier algoritmo para resolver un sistema simétrico disperso de ecuaciones lineales servirá. –
@Pat: buenos algoritmos (es decir, multi-frontales, supernodales, etc.) usan actualizaciones "bloqueadas", al menos para el trabajo de coma flotante, donde la subestructura cuasi-densa permite el uso de núcleos densos (es decir, rutinas 'BLAS') . La fase inicial inicial "simbólica" generalmente implica un acceso irregular, por lo que yo entiendo. –
Las factorizaciones de Cholesky dispersas en una GPU son un problema abierto. Incluso el Linear Programmingpaper mencionado anteriormente utiliza un algoritmo denso, mientras que la mayoría de los problemas son escasos. El mercado comercial de solucionador de LP es muy competitivo, pero nadie tiene un producto que haga mucho uso de la GPU todavía.
Ver UHM - Solucionador de Hyper Matrix sin ensamblar. Puede calcular la factorización de Cholesky dispersa utilizando múltiples GPU en un host.
Publique un pseudo-código para hacer esto en un uniprocesador regular, y me complacería hablar sobre portarlo a la GPU. Además, esto es probablemente algo que ya existe ... déjame hacer una búsqueda rápida. Aha. Ver mi respuesta a continuación. – Patrick87
¿Debe ser una factorización de Cholessky? En general, los métodos dispersos e iterativos que pueden aprovechar una implementación spMV de alto rendimiento se ajustan mucho mejor a las GPU que dirigen los solucionadores. – talonmies
@talonmies - ¡Ah! No debería haber sido tan específico. Lo que realmente necesito es un algoritmo que resuelva el sistema simétrico disperso de ecuaciones lineales. La factorización de Cholesky es lo que se está utilizando actualmente para resolver este problema. Sin embargo, en el caso de la GPU, si otros algoritmos son más apropiados, estoy abierto a eso. –