PDF de programación - BLAS - Curso: Algoritmos Paralelos y Computación de Altas Prestaciones

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

Universidad de Murcia

4

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

Universidad de Murcia

10

BLAS

ScaLAPACK

Paso de mensajes

Direccionamiento
global

PBLAS

LAPACK

BLACS

Secuencial

Dependiente de la
plataforma

Direccionamiento
local

BLAS
Universidad de Murcia

Comunicaciones: PVM, MPI

11

Independiente de la
plataforma

Basic Linear
Algebra
Subprograms

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
accesos
operaciones computacional memoria

coste

BLAS1 vector-vector

BLAS2 matriz-vector

BLAS3 matriz-matriz

n

n2

n3

n

n2

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):

BLAS

XYYZZZ

X: Tipo de datos:

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):

800

Método\tam 200

400

Normal

Blas 1
Blas 2
Blas 3

0.0463

0.7854

7.9686

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