PDF de programación - Sesión: Visión general+BLAS - Librerías Matriciales

Curso: Herramientas Informáticas para

Sesión: Visión general+BLAS

Computación Científica

Parte: Librerías Matriciales

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

Contenido y organización

 Planificado:

 Visión histórica de las librerías matriciales

de álgebra numérica (1Te+0 Pr+0 Tr)

 BLAS (1.5 Te+1 Pr+3 Tr)

 Organización:

 Visión general+BLAS: 1.5 horas
 Prácticas ¿cuándo? ¿cómo?: 1 hora
 Trabajo sin evaluar

Universidad de Murcia

3

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

4

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

5

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

6

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

7

Antecedentes históricos (IV)

 1996: ARPACK
 1997: ScaLAPACK. PLAPACK
 1999: SuperLU
 2000: ATLAS. PETSc
 2002: GotoBLAS
 ...: FLAME. LAPACK07. HeteroScaLAPACK

Universidad de Murcia

8

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

Comunicaciones: PVM, MPI

Universidad de Murcia

9

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

BLAS

Comunicaciones

Universidad de Murcia

10

Obteniendo información

 www.netlib.org/liblist.html
 www.netlib.org/utk/people/JackDongarra/la-sw.html

Universidad de Murcia

11

BLAS

ScaLAPACK

Paso de mensajes

Direccionamiento
global

PBLAS

LAPACK

BLACS

Dependiente de la
plataforma

Secuencial

Direccionamiento
local

BLAS

Comunicaciones: PVM, MPI

Universidad de Murcia

12

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

13

BLAS

 Hay tres niveles según el coste

computacional:
tipo
operaciones



coste

accesos
computacional memoria

BLAS1 vector-vector

BLAS2 matriz-vector

BLAS3 matriz-matriz

n

n2

n3

n

n2

n2

Universidad de Murcia

14

BLAS 1

Universidad de Murcia

15

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

16

BLAS

 Formato de las funciones (niveles 2 y 3): 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

17

BLAS 2

Universidad de Murcia

18

BLAS 2

Universidad de Murcia

19

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

20

BLAS 3

Universidad de Murcia

21

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

22

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

23

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

24

Algoritmos por bloques (en CAP)

 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

25

BLAS - Práctica

 Una sesión presencial (¿cuándo? ¿dónde?)

para explicar el uso de BLAS.

 Versiones de multiplicación de matrices,

normal, con BLAS 1, 2 y 3:
 Compilarlas lincando con BLAS
 Ejecutar y comprobar el resultado, determinando la

forma de llamar a las matrices en BLAS

 Comparar tiempos de ejecución para las distintas

versiones variando el tamaño de las matrices

Universidad de Murcia

26