Story Transcript
Linear Algebra PACKage (LAPACK) Avances en la Generación de Bibliotecas de Álgebra Lineal Universidad Politécnica de Valencia Marzo, 2006
Estructura
¿Qué es la biblioteca LAPACK? Organización de LAPACK Funcionalidad de LAPACK Sistemas lineales Mínimos cuadrados Valores propios Valores singulares Prestaciones de LAPACK Valores propios Factorización LU Optimización de la factorización LU Fuentes de información
LAPACK
¿Qué es la Biblioteca LAPACK?
Recordar que en un gran número de aplicaciones científicas aparecen problemas del Álgebra lineal numérica: Solución de sistemas lineales de ecuaciones Problemas de mínimos cuadrados Problemas de valores propios Problemas de valores singulares ...pero el BLAS no resuelve estos problemas, sólo implementa operaciones numéricas básicas
LAPACK es un conjunto de rutinas escritas en Fortran 77 para la resolución de problemas numéricos y que contiene el “estado del arte” en bibliotecas para Álgebra lineal (¿FLAME?)
LAPACK
¿Qué es la Biblioteca LAPACK?
A diferencia de BLAS que es una especificación, LAPACK es una biblioteca de algoritmos numéricos http://www.netlib.org/lapack Factorización LU SUBROUTINE xGETRF( M, N, A, LDA, IPIV, INFO ) ...implementa una variante por bloques específica del algoritmo de factorización LU con pivotamiento
LAPACK está diseñada para ser eficiente en los computadores actuales: es tan eficiente como los núcleos del BLAS que hay por debajo
LAPACK permite explotar el paralelismo en arquitecturas multiprocesador con memoria compartida haciendo uso de BLAS con múltiples threads
LAPACK
¿Qué es la Biblioteca LAPACK?
LINPACK y EISPACK fueron las bibliotecas de Álgebra lineal precursoras de LAPACK J.J. Dongarra, J.R. Bunch, C.B. Moler, G.W. Stewart. LINPACK Users' Guide. SIAM, Philadelphia, PA, 1979 B.T. Smith, J.M. Boyle, J.J. Dongarra, B.S. Garbow, Y. Ikebe, V.C. Klema, C.B. Moler. Matrix eigensystem routines – EISPACK Guide, vol. 6 of Lecture Notes in Computer Science, SpringerVerlag, Berlin, 1976
LAPACK
Organización de LAPACK
LAPACK se estructura en tres tipos de rutinas: Rutinas “drivers” para la resolución de problemas de tipo estándar Ejemplo: Resolución de un sistema lineal de ecuaciones
Rutinas “computacionales” para la resolución de tareas Ejemplo: Cálculo de la factorización LU de una matriz
Rutinas “auxiliares” para la realización de cálculos de entidad menor Ejemplo: Aplicación de las permutaciones resultantes de la factorización LU a otra matriz
LAPACK
Funcionalidad de LAPACK
Sistemas lineales (de ecuaciones) AX =B
Problemas lineales de mínimos cuadrados min x ∥b− Ax∥2
Problemas lineales de mínimos cuadrados generalizados
Problemas (generalizados) de valores propios
Problemas (generalizados) de valores singulares
LAPACK
Ax =vx A=U ∑ V T
Funcionalidad de LAPACK
Tipos de datos Simple precisión (IEEE 754 – 32 bits) Doble precisión (IEEE 754 – 64 bits) Reales Complejos
LAPACK
Funcionalidad de LAPACK: Sistemas Lineales
Resolución del sistema y bastante más...
Estimación del número de condición del problema, test de singularidad, monitorización del crecimiento de la magnitud de los elementos
Refinado de la solución y cálculo de cotas para el error regresivo y progresivo
Equilibrado de la matriz
LAPACK
Funcionalidad de LAPACK: Sistemas Lineales
Tipos de sistemas General: Factorización LU
General
A ∏ = LU
Simétrico positivo definido: Factorización de Cholesky
Densa
A=U T U o A=L L T
Simétrico no definido: Factorización LDL
Banda
A= L ∑ LT Tridiagonal
Formatos empaquetados disponibles
LAPACK
Simétrica/ Hermitiana
Funcionalidad de LAPACK: Mínimos Cuadrados
Tipos de problemas: General
Densa
Solución de problemas sobredeterminados (rango completo) Factorización QR Solución con mínima 2-norma para problemas infradeterminados (rango incompleto) Descomposición de valores singulares Descomposición ortogonal completa basada en factorización QRP
LAPACK
Funcionalidad de LAPACK: Valores Propios
Tipos de problemas General
Densa
Banda
Tridiagonal
LAPACK
NO
NO
Simétrica/ Hermitiana
Funcionalidad de LAPACK: Valores Propios
Cálculo parcial y total del espectro y de los vectores propios Para problemas simétricos, métodos basados en iteración QR y dividey-vencerás Para problemas no simétricos, método basado en la iteración QR; estimación del número de condición y cálculo de subespacios invariantes/deflactantes
Solución de problemas generalizados:
LAPACK
Ax =vEx
Funcionalidad de LAPACK: Valores Singulares
Tipos de problemas General
Densa
Dos métodos: Variaciones de Golub-Reinsch y Chan Basado en divide-y-vencerás
Solución de problemas de valores singulares generalizados
LAPACK
Prestaciones Plataforma: Procesador: Memoria: Biblioteca BLAS: Compilador: S.O.:
Intel Xeon 2.4 GHz 512 KB de caché L2 y 1 GB de RAM GotoBLAS 0.96st gcc 3.3.5; optimización -O3 Linux 2.4.27
Parámetro de rendimiento:
MFLOPs
Velocidad pico teórica:
4800 MFLOPs
LAPACK
Prestaciones: Valores Propios
LAPACK
Prestaciones: Factorización LU
LAPACK
Optimización de la Factorización LU
¿Por qué las prestaciones de dgetrf están por debajo de las de dgemm?
1. A11
A21
A11
A12
nb
=
L11 U11 L21 −1
2. A12=U12=U11
A12
3. A22= A22−L21 U12 A21
nb
LAPACK
A22 Las operaciones de la etapa 3 se realizan en términos de BLAS-3 (GEPP)
Optimización de la Factorización LU
¿Qué parte representan las operaciones de BLAS-3 en dgetrf? n/n b−1
∑
n−k 1 nb 2 nb
k =1
2 3 n 3
2 3 2 n −n nb 3 ≈ ≈1 si n b ≪n 2 3 n 3
En teoría, cuanto menor es el tamaño de bloque, más operaciones se realizan en términos de BLAS-3
Sin embargo, no todas las operaciones en BLAS-3 son de la misma “calidad”
LAPACK
Optimización de la Factorización LU
LAPACK
Optimización de la Factorización LU
LAPACK
Fuentes de Información: www, google,...
LAPACK 3.0 (1995-1999) E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen. LAPACK Users' Guide, 3rd ed., SIAM, Philadelphia, PA, 1999
LAPACK