La forma más rápida de encontrar pares propios de una pequeña matriz no simétrica en una GPU en memoria compartida

Tengo un problema en el que necesito encontrar todos los pares propios positivos (ya que el valor propio es positivo) de una matriz no simétrica pequeña (generalmente más pequeña que 60x60). Puedo dejar de calcular cuando el valor propio es menor que un cierto umbral. Sé que los valores propios son reales. ¿Alguna sugerencia sobre algoritmos que podría usar para tratar de obtener el mejor rendimiento? Tengo que hacer varios miles de estas descomposiciones, por lo que la velocidad es importante.

Gracias de antemano.

EDITAR: Necesito hacer esto en la GPU en la memoria compartida. Las matrices tampoco son necesariamente del mismo tamaño. No conozco ninguna biblioteca que haga esto en este momento. Se agradecerán sugerencias de algoritmos que se adapten bien al problema.

performance eigensystem gpu Kantoku
fuente

Si lo entendí bien, tiene un núcleo CUDA que calcula miles de pequeñas matrices en la memoria compartida, y no está dispuesto a copiarlas en la memoria global. Antes de intentar dar una respuesta, hay algunos puntos para aclarar. En CUDA, la vida útil de la memoria compartida está destinada a bloquear la vida útil: ¿cuántos subprocesos tiene para que se descomponga cada matriz? ¿Es realmente importante el rendimiento extremo? (¿Cómo se comparan los tiempos de extracción de valores propios esperados con los tiempos de generación de matrices?) ¿Con base en qué argumento sabe que el sistema propio es real? ¿Puede el sistema propio ser defectuoso?

Stefano M

Hola Stefano y gracias por tu comentario. Por ahora, tendré el múltiplo más cercano del tamaño de urdimbre a la dimensión de la matriz que me gustaría descomponer. Los tiempos de generación de matriz varían mucho, y hay casos en los que el tiempo de generación de matriz es más costoso, pero hay muchas situaciones en las que el tiempo de generación de matriz es menor que la descomposición. Sé que los valores propios son reales debido a la forma en que se genera la matriz. Prefiero no entrar en detalles aquí, ya que esto restaría valor a la pregunta original. Finalmente, sí, el sistema puede estar defectuoso.

Kantoku

Respuestas:

Sin hacer muchas búsquedas, te recomiendo que mires la biblioteca MAGMA . Código de libre acceso con soporte continuo. NVIDIA reconoció a MAGMA como "Un gran avance en soluciones para problemas de valor propio".

También hay una biblioteca CULA , que generalmente es un producto comercial, aunque recientemente se ha hecho gratis para uso académico (ver detalles aquí ).

Alejandro
fuente

Gracias por tu respuesta Alexander. He examinado ambas bibliotecas antes y, que yo sepa, las funciones se invocan desde el host y la memoria debe estar en la memoria global. Creo que la sobrecarga sería demasiado para justificar el uso. Todas estas matrices se generan en la memoria compartida, se usan en el núcleo y luego se descartan. Me gustaría mantenerlos allí sin tener que volver a ponerlos en la memoria global. Incluso si los empujara allí, aún habría el problema de llamar a muchas funciones del núcleo desde el host (aunque en múltiples flujos).

Kantoku

@Kantoku, sí, esas bibliotecas son más generales y almacenan toda la matriz en la memoria global. Si sus matrices están en la memoria compartida, solo una SM puede trabajar en ellas, ¿no? Por lo tanto, la implementación de EVD debería ser bastante sencilla.

Alexander

Sí, me lo imagino, por eso estaba buscando algoritmos que fueran apropiados para la situación. No estoy demasiado familiarizado con evd no simétrico, así que estaba buscando sugerencias.

Kantoku

@Kantoku (y Alexander). Los EVD no simétricos están lejos de ser sencillos, incluso en el caso secuencial. Sigue siendo un área activa de investigación.

Jack Poulson

@JackPoulson Ah sí, tienes razón, pero yo (y supongo que Alexander también) quise decir que sería sencillo aplicar un algoritmo establecido al problema, considerando que se pueden hacer muchas simplificaciones cuando tomamos el tamaño y la naturaleza. de la matriz en consideración. El problema es: qué algoritmo.

Kantoku

Use las funciones en LAPACK, es poco probable que pueda vencerlas en su propia implementación.

Wolfgang Bangerth
fuente

Hola wolfgang Gracias por la respuesta, pero tengo la intención de implementar esto en una GPU usando CUDA y para varios miles de estas pequeñas matrices (donde cada bloque maneja la descomposición de una sola matriz), y las matrices no son necesariamente del mismo tamaño, por lo que implementar Algo que uso memoria compartida parece ser mi única opción. ¿Alguna idea de qué algoritmo sería el más adecuado para este tipo de matrices? PD: Gracias por el trato. II conferencias que diste en KAUST el semestre pasado. Los disfruté :)

Kantoku

@ Kantoku Debe agregar estos detalles en su pregunta, de lo contrario es engañoso.

Alexander

@Alexander He actualizado la pregunta con más detalles. ¡Gracias por la sugerencia!

Kantoku

@Kantoku: las GPU están un poco más allá de mi reino, pero estoy seguro de que ya hay bibliotecas que hacen lo que quieres (y de hecho veo que otras respuestas ya están vinculadas a ellas). ¡Me alegra saber que te gustaron mis clases!

Wolfgang Bangerth