PDF de programación - Librerías Paralelas de Álgebra Lineal Densa - Computación Matricial y Paralela

Computación Matricial y Paralela

Librerías Paralelas de Álgebra Lineal 

Densa

Javier Cuenca

Domingo Giménez

Dpto. de Ingeniería y Tecnología de Computadores

Dpto. de Informática y Sistemas

Universidad de Murcia

http://dis.um.es/~domingo

1

2

Contenido

 Introducción
 Librería BLACS
 Librería PBLAS
 Librería ScaLAPACK

Introducción

3

ScaLAPACK

Paso de mensajes

Direccionamiento
global

PBLAS

LAPACK

BLACS

Dependiente de la
plataforma

BLAS

Comunicaciones: PVM, MPI

Direccionamiento
local

Independiente de la
plataforma

Secuencial

Librería BLACS
(Basic Linear Algebra Communication Subprograms)

4

 “ Basic Linear Algebra Communication Subprograms”

 Hace uso de los paquetes software de paso de

mensajes.

 Proporciona facilidad de uso y portabilidad para la

comunicación en problemas de álgebra lineal.

Librería BLACS.
Motivación

5

 Hay varios paquetes que proporcionan una interfaz de paso
de mensajes que permanecen invariables a través de varias
plataformas (ej. PVM, MPI, PICL).

 Pero, estos paquetes son librerías generales y sus

interfaces no son tan fáciles de usar en álgebra lineal como
sería deseable.

Librería BLACS.
Objetivos

 Facilidad de programación

6

 Simplifica el paso de mensajes y así reduce los errores

de programación.
 Facilidad de uso

 Está a un nivel en el que es fácilmente usable por los

programadores de álgebra lineal.

 Portabilidad

 Proporciona una interfaz que está soportada por un gran

abanico de computadores paralelos.

Librería BLACS.
Resultado

7

 Con BLACS la interfaz y los métodos de uso de las rutinas,

han sido especializados y por tanto simplificados.

8

Librería BLACS.
Ideas base

 Comunicación de matrices

 Generales

 M filas por N columnas
 LDA: Distancia entre dos elementos fila consecutivos (Column-

major).

 Trapezoidales, definidas por

 MxN, LDA
 UPLO, DIAG (‘ U’ ,’ N’ )

9

Librería BLACS.
Ideas base.
Parámetro UPLO

UPLO

M <= N

‘U’

‘L’

m

n

n­m+1
n­m+1

n

M>N

n

m

m­n+1

m

m

m­n+1

n

Librería BLACS.
Ideas base

 Mapeo de los procesos en un grid

Array lineal de ID de procesos

0

1

2

...

Np­1

10

0

0

4

2

1

5

3

2

6

4

3

7

0

1

8 procesos mapeados en 

un grid 2x4

Un conjunto de procesos 0,1,...,Np-1
se mapea como una malla de PxQ procesos,
donde PxQ = Ng <= Np

Librería BLACS.
Ideas base

11

 Ámbito de una operación en una malla 2D

Ámbito

Fila

Columna

Significado

Todos los procesos de la fila participan en la 
operación

Todos los procesos de la columna participan en 
la operación

Todos

Todos los procesos participan en la operación

Librería BLACS.
Ideas base

12

 Contextos

 Cada malla lógica de procesos está contenida en un

contexto BLACS.

 Los contextos permiten:

 Crear grupos de procesos arbitrarios
 Crear grids solapados o disjuntos
 Aislar los procesos de los grids para que no interfieran con los de

otros grids.

13

Librería BLACS.
Rutinas

Comunicación

Pto. a pto.
Difusión
Reducción

Rutinas

Apoyo

Inicialización
Destrucción
Información y otras
No oficiales

Librería BLACS.
Rutinas.
Comunicación Pto a pto

14

 Nomenclatura de las rutinas punto a punto y difusión

vXXYY2D

Tipo de datos:

I (Integer), S, D, C, Z

v

Forma de la matriz:

XX

GE
TR

Tipo Comunicación:

YY

SD, RV (Send, Recieve)
BS, BR (Bcast send, recv)

Librería BLACS.
Rutinas.
Comunicación Pto a pto

15

 Envío

 vGESD2D(ICONTXT,M,N,A,LDA,RDEST,CDEST)

 vTRSD2D(ICONTXT,UPLO,DIAG,M,N,A,LDA,RDEST,CDEST)

 Recepción

 vGERV2D(ICONTX,M,N,A,LDA,RSRC,CSRC)

 vTRRV2D(ICONTX,UPLO,DIAG,M,N,A,LDA,RSRC,CSRC)

Librería BLACS.
Rutinas.
Difusión

16

 Envío

 vXXBS2D(ICONTX,SCOPE,TOP[,UPLO,DIAG],M,N,A,LD

A)

 Recepción

 vXXBR2D(ICONTX,SCOPE,TOP[,UPLO,DIAG],M,N,A,L

DA,RSRC,CSRC)

Librería BLACS.
Rutinas.
Difusión - Topologías

17

 Basadas en anillo (pipelining)

 Anillo unidireccional

 Anillo dividido

 Multianillo

 Basadas en árboles (non-pipelining)

 Hipercubo

 Árbol general

Librería BLACS.
Rutinas.
Difusión

18

 Máximo

 vGAMX2D(ICONTX,SCOPE,TOP,M,N,A,LDA,RA,CA,RCFLAG,RDE

ST,CDEST)

 Mínimo

 vGAMN2D(ICONTXT,SCOPE,TOP,M,N,A,LDA,RA,CA,RCFLAG,RD

EST,CDEST)

 Suma

 vGSUM2D(ICONTXT,SCOPE,TOP,M,N,A,LDA,RDEST,CDEST)

Librería BLACS.
Rutinas.
Difusión - Topologías

 General Tree Gather

 Intercambio bidireccional

19

Librería BLACS.
Rutinas.
Apoyo

 Inicialización

20

 BLACS_PINFO: usada cuando se necesita alguna información inicial del

sistema. Devuelve el índice de proceso y el número de procesos.

 BLACS_SETUP: esta solo tiene sentido en PVM que permite añadir

dinámicamente procesos.

 BLACS_GRIDINIT: mapea los procesos disponibles en el grid BLACS.

Devuelve el contexto.

 BLACS_GRIDMAP: establece como se mapearán los procesos

coordenados BLACS respecto de la numeración nativa de la máquina.

Librería BLACS.
Rutinas.
Apoyo

 Destrucción

21

 BLACS_FREEBUF: libera los buffers usados por BLACS.

 BLACS_GRIDEXIT: libera un contexto BLACS.

 BLACS_ABORT: utilizada para abortar un proceso, normalmente se

llama cuando ocurre un error.

 BLACS_EXIT: esta rutina se debe llamar cuando un proceso ha

terminado de usar BLACS. Se puede indicar si la capa inferior de
comunicación se va a seguir usando o si se puede liberar
(pvm_exit).

Librería BLACS.
Rutinas.
Apoyo

 Información y otras:

22

 BLACS_GRIDINFO: devuelve información acerca de un proceso

en un determinado contexto.

 BLACS_PNUM: devuelve el número de proceso del sistema dado

su posición en el grid.

 BLACS_PCOORD: dado el número de proceso del sistema

devuelve sus coordenadas en el grid.

Librería BLACS.
Rutinas.
Apoyo

23

 BLACS_GET: devuelve información interna de BLACS (context

handle, rango de IDs de mensajes, nivel de depuración,...).

 BLACS_SET: establece valores internos de parámetros BLACS.

Librería BLACS.
Rutinas.
Apoyo

24

 Rutinas no oficiales

 No forman parte del BLACS estándar.

 Pueden no estar en todas las implementaciones de BLACS.

 Ejemplos:

 SETPVMTIDS

 DCPUTIME

 DWALLTIME

Librería BLACS.
Referencias

25

 BLACS:

 Página principal: http://www.netlib.org/blacs/

 LAPACK Working Note 94, "A User's Guide to the BLACS

v1.1", Jack J. Dongarra, R. Clint Whaley, May 5, 1997

Librería BLACS.
Ejemplos

26

 scala_01.c
 scala_02.c
 Compilación

$ make scala_01

cc -migrate -fast -ieee scala_01.c gm.o -o scala_01

/usr/opt/SCALAPACK/libscalapack.a /usr/opt/BLACS/LIB/blacsCinit_MPI-
ALPHA-1.a /usr/opt/BLACS/LIB/blacs_MPI-ALPHA-1.a
/usr/opt/BLACS/LIB/blacsCinit_MPI-ALPHA-1.a -lfor -lcxml -lmpi -lrt
-pthread -lm

 Ejecución

dmpirun – np num_procesos scala_01 num_fil num_col

Librería BLACS.
Ejemplo scala_01.c

27

 blacs_pinfo_(&iam,&nprocs);

 &iam (o): quién soy yo
 &nprocs (o): total de procesos disponibles, antes de inicializar

BLACS

 blacs_get_(&i_cero,&i_cero,&contxt);

 &i_cero (i): si estoy en un contexto ya, si no, se ignora
 &i_cero (i): qué devolver en 3er argumento. =0 un handler del

contexto de sistema por defecto

 &contxt (o): El handler del contexto sistema por defecto

 Obtiene el handler del contexto del sistema

Librería BLACS.
Ejemplo scala_01.c

28

 blacs_gridinit_(&contxt,"R",&nprow,&npcol);

 &contxt (i/o):

 input: el handler que indica el contexto del sistema (blacs_get)
 Output: el nuevo handler para el contexto de BLACS

 “ R” (i): row-major en el número de procesos en el grid
 &nprow (i): cuántas filas de procesos en el grid
 &npcol (i): cuántas columnas de procesos en el grid

 Inicializa el grid de procesos

Librería BLACS.
Ejemplo scala_01.c

29

 blacs_gridinfo_

(&contxt,&nprow,&npcol,&myprow,&mypcol);
 &contxt (i): el handler del contexto
 &nprow (o): número de filas de procesos en el grid
 &npcol (o): número de columnas de procesos en el grid
 &myprow (o): mi fila en el grid
 &mypcol (o): mi columna en el grid

 Obtiene informacion del grid existente

Librería BLACS.
Ejemplo scala_01.c

30

 icaller=blacs_pnum_(&contxt,&myprow,&mypcol);

 &contxt (i): handler del contexto
 &myprow (i): mi número de fila
 &mypcol (i): mi número de columna

 Devuelve el número de proceso del sistema correspondiente a las

coordenadas que se le pasa

Librería BLACS.
Ejemplo scala_01.c

31

 igerv2d_(&contxt,&i_uno,&i_uno,&icaller,&i_uno,&i,&j)

 &contxt (i):
 &i_uno (i): numero filas matriz a recibir
 &i_uno (i): numero columnas matriz a recibir
 &i_caller (o): matriz a recibir
 &i_uno (i): lead dimension
 &i (i): nº fila del proceso fuente del envio
 &j (i): nº columna del proceso fuente del envio

 Recibe una matriz de datos

Librería BLACS.
Ejemplo scala_01.c

32

 blacs_pcoord_(&contxt,&icaller,&hisrow,&hiscol);

 &contxt
 &icaller (i): número de proceso
 &hisrow (o): número de fila del proceso
 &hiscol (o): número de columna del proceso

 Dado un número de proceso devuelve sus coordenadas en el grid

Librería BLACS.
Ejemplo scala_01.c

 blacs_abort_(&contxt,&i_uno);

 &contxt(i)
 &i_uno (i): número de error por el que se detiene

33

Librería BLACS.
Ejemplo scala_01.c

34

 igesd2d_

(&contxt,&i_uno,&i_uno,&icaller,&i_uno,&i_cero,&i_cer
o);
 &contxt (i)
 &i_uno: número de filas de la matriz
 &i_uno: número de columnas de la matriz
 &i_caller: la matriz que se envía
 &i_uno: lead dimension de la matriz
 &i_cero: coordenada fila de proceso destino
 &i_cero: coordenada columna de proceso destino

 Envía una matriz de datos a otro proceso

Librería BLACS.
Ejemplo scala_02.c

35

 dgebs2d_(&contxt,p_all,p_vacio,&N,&N,A,&ldA);

 &contxt
 P_all (i): scope del broadcast: “ All” , “ Row” , “ Column”
 P_vacio (i): topología del algoritmo de broadcast, “ “ es la de por

defecto más eficiente.

 &N,&N,A,&ldA: la matriz y sus dimensiones

 Broadcast de una matriz, el emisor

Librería BLACS.
Ejemplo scala_02.c

36

 dgebr2d_

(&contxt,p_all,p_vacio,&N,&N,A,&ldA,&i_Cero,&i_Cero);

 &contxt
 P_all