Álgebra Lineal
Clase 10
Motivaciones
• Algébra Lineal Computacional para resolver
• Sistemas lineales.
• Problemas de autovalores y autovectores.
• Problemas comunes en todas las áreas de las ciencias.
• Requiere adaptar métodos específicos del álgebra lineal al hardware via software.
• Se utilizan como benchmarks (Top 500, HPL).
Motivaciones: Matrices• Matrices: arreglos rectangulares de
números.
• Son la representación de numerosos procesos en distintas áreas.
• Esa representación genera el significado de la ubicación de los números en la matriz.
• Jiu Zhang Suanshu, Nueve capítulos sobre el arte matemático, Cap. 8, sobre ‘Tablas rectangulares’, 200 dC.
九章算術
Matrices: Page Rank (Brin, Page)
Aij=1 si i j
Ax=b DirectoA=LU
Iterativox’=Sx
No simétricoDescomposición
LUPivoteo
GMRES,QMR
Simétrico, definido positivo Cholesky Gradiente
Conjugado
Ejemplo: Sistemas lineales densos
Factorización LU
• A es una matriz de n x n, general, densa
• L es triangular inferior, Lii=1
• U es triangular superior
Ax=b
LUx=b
Ux=yLy=bFactorización
LU
Sustitución hacia adelante
(forward substitution)
y=L-1 b x=U-1 ySustitución hacia
atrás(backward
substitution)
U = A , L =I do k=1,n-‐1
do j=k+1,n L(j,k) = U(j,k)/U(k,k) U(j,k:n) = U(j,k:n) -‐ L(j,k) * U(k,k:m)
Factorización LU (sin pivot)
Factorización LU
Ax=b
LUx=b
Ux=yLy=bFactorización
LU
Sustitución hacia adelante
(forward substitution)
y=L-1 b x=U-1 ySustitución hacia
atrás(backward
substitution)
Do implícito
Factorización LU (sin pivot)
U = A , L =I do k=1,n-‐1
do j=k+1,n L(j,k) = U(j,k)/U(k,k) U(j,k:n) = U(j,k:n) -‐ L(j,k) * U(k,k:m)
Factorización LU
Do implícito
nop = O(n3) nop = O(n2)
Ax=b
LUx=b
Ux=yLy=bFactorización
LU
Sustitución hacia adelante
(forward substitution)
y=L-1 b x=U-1 ySustitución hacia
atrás(backward
substitution)
Factorización LU (sin pivot)• La factorización LU sin pivot no es estable
10-20 1
1 1A =
1 0
10+20 1
10-20 1
0 1-1020=
• En doble precisión
A =10-20 1
0 10 20=
10-20 1
1 0=
10-20 1
1 1
1 0
10+20 1
Factorización LU (con pivot)
U = A , L =I, p=I do k=1,n-‐1 i = pos_max(abs(U(k,k:n))) swap(U(k,k:m),U(i,k:m)) swap(L(k,1:k-‐1),L(i,1,k:-‐1)) p(k)=i do j=k+1,n L(j,k) = U(j,k)/U(k,k) U(j,k:n) = U(j,k:n) -‐ L(j,k) * U(k,k:m)
Ax=b
LUx=p-1b
Ux=yLy=p-1bFactorización
LU
Sustitución hacia adelante
(forward substitution)
y=L-1 p-1b x=U-1 ySustitución hacia
atrás(backward substitution)
Factorización LU
Do implícito
Factorización LU in-place
Ukkk
k
p=I do k=1,n-‐1 i = pos_max(abs(A(k:n,k))) swap(A(k,:),A(i,:)) p(k)=i do j=k+1,n A(j,k) = A(j,k)/A(k,k) A(j,k+1:n) = A(j,k+1:n) -‐ A(j,k) * U(k,k+1:m)
Right Looking Algorithm
Factorización LU por Bloques
A11 A12
A21 A22
L11 0
L21 L22
U11 U12
0 U22
A11 = L11 U11
A12 = L11 U12
A21 = L12 U11
A22 = L12 U12 + L22 U22
(L11, U11) = FactorLU(A11)
U12 = L11-1 A12
L12 = U11-1 A21
A22 - L12 U12 = L22 U22
= x
Factorización LU por Bloques
A11 A12
A21 A22
L11 0
L21 L22
U11 U12
0 U22 Paralelizable != x
A11 = L11 U11
A12 = L11 U12
A21 = L12 U11
A22 = L12 U12 + L22 U22
(L11, U11) = FactorLU(A11)
U12 = L11-1 A12
L12 = U11-1 A21
A22 - L12 U12 = L22 U22
• Nivel 1: vector-vector.
• Nivel 2: Matriz-vector.
• Nivel 3: Matriz-matriz.
Blas: Basic Linear Algebra Routines
• Versiones optimizadas: Intel Mkl, OpenBlas.
• Single/Multi-thread.
CPU
Lapack LU
• xGETRF
• x = s, d (simple/doble precisión, números reales)
• x = c, z (simple/doble precisión, números complejos)
• Basada en BLAS, nivel 3.
* M (input) INTEGER * The number of rows of the matrix A. M >= 0. * * N (input) INTEGER * The number of columns of the matrix A. N >= 0. * * A (input/output) COMPLEX*16 array, dimension (LDA,N) * On entry, the M-‐by-‐N matrix to be factored. * On exit, the factors L and U from the factorization * A = P*L*U; the unit diagonal elements of L are not stored. * * LDA (input) INTEGER * The leading dimension of the array A. LDA >= max(1,M). * * IPIV (output) INTEGER array, dimension (min(M,N)) * The pivot indices; for 1 <= i <= min(M,N), row i of the * matrix was interchanged with row IPIV(i). * * INFO (output) INTEGER * = 0: successful exit * < 0: if INFO = -‐i, the i-‐th argument had an illegal value * > 0: if INFO = i, U(i,i) is exactly zero. The factorization * has been completed, but the factor U is exactly * singular, and division by zero will occur if it is used * to solve a system of equations.
SUBROUTINE ZGETRF( M, N, A, LDA, IPIV, INFO )
CPU
Distribuido ScalapackMP Linpack
Un núcleo LapackBlas
1998
CPU Híbrido
Distribuido Scalapack
Multi-núcleo Plasma Quark
Un núcleo LapackBlas
GPU Acelerador
Magma Quark
DPlasma / Scalapack+GPUDAGue / StarPU
MagmaCuda/OpenCL/Mic
2015
• Nivel 1: vector-vector.
• Nivel 2: Matriz-vector.
• Nivel 3: Matriz-matriz.
Blas: Basic Linear Algebra Routines
• Versiones optimizadas: Intel Mkl, OpenBlas.
• Single/Multi-thread.
•cuBlas, para GPU nVidia (cublas_).
•magma_blas, las mejores han sido incorporadas en cuBlas (magma_).
•Vectores y matrices en GPU.
•http://docs.nvidia.com/cuda/cublas/index.html
CPU
GPU
Magma: Matrix Algebra on GPU and Multicore Architectures
• ‘Lapack’ for GPUs
• Versiones para GPU (nVidia, ATI), intel Phi.
• Algunas rutinas multigpu (_mgpu).
• Escrita en C, bindings para Fortran.
FEATURES AND SUPPORT1.6 FOR CUDA
Linear system solvers
Eigenvalue problem solvers
Auxiliary BLAS
Batched LA
Sparse LA
CPU Interface
GPU Interface
Multiple precision support
Non-GPU-resident factorizations
Multicore and multi-GPU support
LAPACK testing
Linux
Windows
Mac OS
MAGMA MIC 1.3 FOR Intel Xeon Phi
clMAGMA 1.3 FOR OpenCL
PERFORMANCE & ENERGY EFFICIENCY
MAGMA on Kepler K40LU factorization in double precision arithmetic
1 GPU
2 GPUs
CPUMKL
2K 4K 36K
Gflop/w
34K32K30K28K26K24K22K20K18K16K14K12K10K8K6K
2500
2000
1500
1000
500
0
Gflop
/s
MATRIX SIZE
NVIDIA K40 (Atlas)15 MP x 192 @ 0.88 GHz
GPU Intel Xeon ES-2670 (Sandy Bridge)2 x 8 cores @ 2.60 GHz
CPU
4.74.74.44.4
1.11.1
1.6 DRIVER ROUTINES
ABBREVIATIONSGESPD/HPDTR D&C B&I It MP
GeneralSymmetric/Hermitian Positive DefiniteTriangularDivide & Conquer Bisection & Inverse IterationMixed-precision Iterative Refinement
LIN
EAR
EQUA
TION
S
LEASTSQUARES
STAN
DARD
EVP
STAND.SVP
GEN
ERAL
IZED
EVP
GE
SPD/HPD
GE
GE
SY/HE
GE
SPD/HPD
Solve using LUSolve using MPSolve using CholeskySolve using MPSolve LLS using QRSolve using MPCompute e-values,optionally e-vectorsComputes all e-values,optionally e-vectorsRange ( D&C )Range ( B&I It. )Range ( MRRR )Compute SVD,optionally s-vectorsCompute all e-values,optionally e-vectorsRange ( D&C )Range ( B&I It.)Range ( MRRR )
{sdcz}gesv{zc,ds}gesv{sdcz}posv{zc,ds}posv{sdcz}gels{zc,ds}geqrsv{sdcz}geev
{sd}syevd{cz}heevd{cz}heevdx{cz}heevx{cz}heevr{sdcz}gesvd{sdcz}gesdd{sd}sygvd{cz}hegvd{cz}hegvdx{cz}hegvx{cz}hegvr
✓ ✓ ✓ ✓ ✓ ✓✓✓✓✓✓✓✓✓
✓✓✓✓✓✓ ✓✓✓✓✓
NAMING CONVENTIONmagma_{routine name}[_gpu]
MATRIX OPERATION ROUTINEINTERFACES
CPU GPU
Instalando Magma
• http://icl.cs.utk.edu/magma/software/index.html
• Instalación similar a Lapack:
tar -zxf magma-1.6.2.tar.gz
Editar make.inc (ver ejemplos make.inc.*)
make
• http://icl.cs.utk.edu/magma/docs/
magmablas/
contrib/
control/
exp/
src/
Makefile
testing/
Makefile.internal
include/
make.inc.goto
make.inc.mkl-‐gcc
make.inc
ls magma-‐1.6.2:
Magma LU
• magma_xGETRF[_gpu,_mgpu,....]
• Usa la misma interface que Lapack.
• Vamos a compilar y correr algunos ejemplos de la instalación (magma-1.6.2/testing)
• http://icl.cs.utk.edu/magma/docs/
zgetrf2_mgpu.cpp
zgetrf.cpp
zgetrf_gpu.cpp
zgetrf_incpiv_gpu.cpp
zgetrf_m.cpp
zgetrf_mgpu.cpp
zgetrf_nopiv.cpp
zgetrf_nopiv_gpu.cpp
SUBROUTINE ZGETRF( M, N, A, LDA, IPIV, INFO)
Magma LU
• module load cuda-6.5 intel/intel-12 magma-1.6.2
• ccompile.sh [s,d,c,z]
• fcompile.sh [s,d,c,z]
• Varios submit_xx.sh
• correr ejemplos en C con -h para ver las opciones
• comparar los submit_xx.sh
Códigos en C
Códigos en Fortran
Magma LU, C y Fortran
!-‐-‐-‐-‐ Call magma LU -‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐
call magma_wtime_f(tstart)
call magmaf_sgetrf(n, n, A, lda, ipiv, info)
call magma_wtime_f(tend)
/*===========================================
Performs operation using MAGMA =======================================*/
gpu_time = magma_wtime();
magma_sgetrf( M, N, h_A, lda, ipiv, &info);
gpu_time = magma_wtime() -‐ gpu_time;
testing_sgetrf_f.f90testing_sgetrf.cpp
• Fortran Wrappers para las rutinas de magma.
• Interface igual a la de Lapack.
• La rutina se ocupa de reservar memoria en GPU.
Magma LU, C y Fortrantesting_sgetrf_gpu.cpp
• Es necesario reservar memoria en el device (d_A, devptrA).
• Interface igual a la de Lapack.
!-‐-‐-‐-‐ Call magma LU -‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐-‐
call magma_wtime_f(tstart)
call magmaf_dgetrf_gpu(n, n, devptrA, ldda, ipiv, info)
call magma_wtime_f(tend)
/*===========================================
Performs operation using MAGMA =======================================*/
gpu_time = magma_wtime();
magma_sgetrf_gpu( M, N, d_A, lda, ipiv, &info);
gpu_time = magma_wtime() -‐ gpu_time;
testing_zgetrf_gpu_f.F90testing_zgetrf_gpu.cpp
Magma LU, C, Multi GPUtesting_sgetrf_gpu.cpp
• testing_xgetrf_mgpu -N numero —ngpu [1,2]
• Comparar simple (s,c) vs. doble precisión (d,z)
• Comparar 1 vs 2 GPUs. Convencerse que el scaling es lineal !!!
• M,N < 15000
/*===========================================
Performs operation using MAGMA =======================================*/
start = get_current_time();
magma_zgetrf_mgpu( num_gpus, M, N, d_lA, ldda, ipiv, &info);
end = get_current_time();
testing_zgetrf_mgpu.cpp
Resumen
• A partir de testing_ se puede construir un programa simple que resuelva un sistema lineal.
• Interface similar a Lapack.
• Benchmarking tiene sentido si el tamaño de la matriz es tal que la GPU está completamente ocupada.
• MultiGPU en C.
• Magma usa Lapack (Fortran). Si Lapack es multithreaded, también será Magma en CPU.