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