Publicado el 30 de Julio del 2018
870 visualizaciones desde el 30 de Julio del 2018
314,6 KB
24 paginas
Creado hace 8a (15/11/2016)
Curso: Algoritmos Paralelos y Computación de
Altas Prestaciones
BLAS
Domingo Giménez
Departamento de Informática y Sistemas
Universidad de Murcia, Spain
dis.um.es/~domingo
Universidad de Murcia
1
Motivación
Muchas veces son la parte más costosa de la
resolución del problema
Identificar rutinas básicas, estandarizar e
implementarlas eficientemente:
Programación más fácil
Mantenimiento más fácil
Más portabilidad
Códigos eficientes
Universidad de Murcia
2
Motivación
Un gran número de aplicaciones científicas hacen
uso del Álgebra Lineal Numérica:
Simulación de moléculas (problemas de valores
propios)
Econometría (mínimos cuadrados)
Radiosidad (sistemas de ecuaciones)
Búsqueda de información en web (valores propios)
Reconocimiento de caras (valores propios)
...
Universidad de Murcia
3
Antecedentes históricos
(fuente: Enrique Quintana, UJI)
1962: Rounding errors, Wilkinson
1965: The Algebraic Eigenvalue Problem,
Wilkinson. SVD, Golub, Kahan
1969: NAG. Strassen
1972: EISPACK. QZ, Moler, Stewart
1973: BLAS Report
1974: Inicio LINPACK. Inicio BLAS-1
4
Universidad de Murcia
Antecedentes históricos (II)
1975: ACM Trans. on Math. Soft.
1976: EISPACK 2.0
1977: Fortran 77
1978: LINPACK. BLAS1 en ACM TOMS
1980: DV, Cupper
1982: Inicio BLAS-2
1983: Matrix computation, Golub, Van Loan
Universidad de Murcia
5
Antecedentes históricos (III)
1984: EISPACK 3.0. netlib
1986: Inicio BLAS3
1987: Inicio LAPACK. BLAS2 en ACM TOMS
1990: BLAS3 en ACM TOMS.
1992: LAPACK 3.0
1993: Inicio ScaLAPCK
Universidad de Murcia
6
Antecedentes históricos (IV)
1996: ARPACK
1997: ScaLAPACK. PLAPACK
1999: SuperLU
2000: ATLAS. PETSc
2002: GotoBLAS
...: FLAME. LAPACK07. HeteroScaLAPACK
Universidad de Murcia
7
Jerarquía de librerías
Independiente de la
plataforma
Secuencial
ScaLAPACK
Paso de mensajes
Direccionamiento
global
PBLAS
LAPACK
BLACS
Dependiente de la
plataforma
Direccionamiento
local
BLAS
Universidad de Murcia
Comunicaciones: PVM, MPI
8
Jerarquía de librerías
PDE Solver
Least Square Problem
Inverse Eigenvalue Problem
Se puede extender
la jerarquía resolviendo
problemas de alto coste
computacional. Necesarios
algoritmos eficientes
en sistemas de altas
prestaciones.
ScaLAPACK
PBLAS
LAPACK
BLACS
Universidad de Murcia
9
BLAS
Comunicaciones
Obteniendo información
www.netlib.org/liblist.html
www.netlib.org/utk/people/JackDongarra/la-sw.html
https://sourceforge.net/
Universidad de Murcia
10
BLAS
Independiente de la
plataforma
Basic Linear
Algebra
Subprograms
ScaLAPACK
Paso de mensajes
Direccionamiento
global
PBLAS
LAPACK
BLACS
Secuencial
Dependiente de la
plataforma
Direccionamiento
local
BLAS
Universidad de Murcia
Comunicaciones: PVM, MPI
11
BLAS
Conjunto de rutinas para realizar
operaciones básicas sobre vectores y
matrices
C. L. Lawson, R. J. Hanson, D. Kincaid, and F. T. Krogh, Basic Linear
Algebra Subprograms for FORTRAN usage, ACM Trans. Math. Soft
., 5 (1979), pp. 308--323.
J. J. Dongarra, J. Du Croz, S. Hammarling, and R. J. Hanson, An
extended set of FORTRAN Basic Linear Algebra Subprograms, ACM
Trans. Math. Soft., 14 (1988), pp. 1--17.
J. J. Dongarra, J. Du Croz, I. S. Duff, and S. Hammarling, A set of
Level 3 Basic Linear Algebra Subprograms, ACM Trans. Math. Soft
., 16 (1990), pp. 1--17.
Universidad de Murcia
12
BLAS
Hay tres niveles según el coste
computacional:
tipo
operaciones
coste
accesos
computacional memoria
BLAS1 vector-vector
BLAS2 matriz-vector
n
n2
n
n2
BLAS3 matriz-matriz
n3
n2
Universidad de Murcia
13
BLAS 1
Universidad de Murcia
14
BLAS 1
Ejemplo ddot.f
Calcula el producto escalar de dos
vectores
Se puede usar en el bucle más interno
de la multiplicación de matrices, dando
lugar a una versión con BLAS 1
Se compila con (depende del sistema)
cc –O3 mb1.c –lblas -lm
Universidad de Murcia
15
Formato de las funciones (niveles 2 y 3): XYYZZZ
X: Tipo de datos:
BLAS
S : REAL
D : DOUBLE PRECISION
C : COMPLEX
Z : DOUBLE COMPLEX
YY: Tipo de matriz: GE, GB, HE, HP, HB, SY, SP, TR, TP, TB
ZZZ: Operación:
MV: productor matriz vector
MM: producto matriz matriz
SV: sistema de ecuaciones ...
Universidad de Murcia
16
BLAS 2
Universidad de Murcia
17
BLAS 2
Universidad de Murcia
18
BLAS 2
Ejemplo dgemv.f
Calcula el producto de una matriz por un
vector
Se puede usar en el segundo bucle en la
multiplicación de matrices, dando
lugar a una versión con BLAS 2
Se compila con
cc –O3 mb2.c –lblas -lm
Universidad de Murcia
19
BLAS 3
Universidad de Murcia
20
BLAS 3
Ejemplo dgemm.f
Calcula el producto de una matriz por un
vector
Se puede hacer la multiplicación de
matrices llamando directamente a la
rutina correspondiente de BLAS
Se compila con
icc –O3 mb3.c –lgslcblas -lm
Universidad de Murcia
21
BLAS
Multiplicación de matrices (en kefren,
pentium 4):
Método\tam 200
400
800
Normal
0.0463
0.7854
7.9686
Blas 1
Blas 2
Blas 3
0.0536
0.0501
0.0429
0.8190
0.5861
0.6115
8.2311
5.9997
4.7252
Universidad de Murcia
22
Versiones de BLAS
BLAS de referencia: los códigos, los podemos instalar en
nuestro sistema, no optimizado
BLAS propietario: optimizado? por los vendedores para su
sistema
Intel: mkl
IBM: ESSP ...
GotoBLAS: muy eficiente en algunos casos
Multitud de versiones libres optimizadas? para distintos
sistemas, precompiladas
ATLAS se autoinstala
Universidad de Murcia
23
Algoritmos por bloques
En vez de realizar operaciones elemento a
elemento realizarlas con bloques de
elementos: menos accesos a memoria para
el mismo volumen de computación
menor
tiempo de ejecución.
Técnica utilizada desde los años 80. Se
utiliza en LAPACK para obtener rutinas
eficientes independientemente del sistema
donde se ejecuten.
Universidad de Murcia
24
Comentarios de: BLAS - Curso: Algoritmos Paralelos y Computación de Altas Prestaciones (0)
No hay comentarios