PDF de programación - Librerías matriciales paralelas

Librerías matriciales paralelas

Antonio M. Vidal
Murcia 2010

Contenido

• Librerías matriciales y arquitecturas
• El modelo de paso de mensajes
• MPI: una implementación del modelo de paso de 

mensajes

• La librería Scalapack. Filosofía y entorno

– BLACS
– PBLAS
– ScaLAPACK

• Otras librerías matriciales
• La colección ACTS

¿Por qué usar librerías matriciales?

• Desde los principios de la computación científica se entendió la 

necesidad de utilizar librerías numéricas y matriciales

• Objetivos:

– Legibilidad
– Eficiencia
– Portabilidad
– Fiabilidad: calidad de código
– No reprogramar códigos sencillos: organización por niveles

Librerías matriciales y arquitecturas

•Computadores secuenciales: …­1980
Librerías: Legilibilidad, robustez, portabilidad
LINPACK, EISPACK,…

•Operaciones vector­vector: BLAS 1 (1973­
1977)

•Aprovechamiento de las 
unidades funcionales pipeline: 
máquinas vectoriales
Operaciones matriz­vector: BLAS 2 
(1988)

xj
aj

xjaj

*

b

+

b+xjaj

Librerías matriciales y arquitecturas

•Optimización del uso de la jerarquía de memorias
Utilización de múltiples procesadores: Operaciones  matriz­matriz. 
Organización por bloques.
BLAS 3. (1990)

Memoria central

C

P

C

P

C

P

C: Cache

P: Procesador

Memoria 
masiva 
(disco)

•LAPACK: Librería secuencial/paralela (memoria 
compartida). (1992)
Sistemas lineales, Mínimos cuadrados, Valores y vectores 
propios y singulares, Descomposiciones matriciales   

Multiprocesadores y Multicomputadores

Espacio único de direcciones: 
MEMORIA COMPARTIDA

P0

P1

P2

P3

Hacia 1990 empiezan a tomar protagonismo los multiprocesadores con 
memoria distribuida o multicomputadores

Espacios de direcciones locales: 
MEMORIA DISTRIBUIDA

M0

P0

M1

M2

M3

P1

P2

P3

Red de Interconexión

El Modelo de Paso de Mensajes (Kruskal, 1990)
• Abstracción del modelo físico de multiprocesador con memoria 

distribuida

Características
• p procesadores RAM convenientemente modificados
• Cada uno dispone de su propia memoria local con su propio espacio 

• No existe memoria común o no se puede usar para intercambiar 

• Cada procesador tiene un índice por el que se le reconoce y se 

de direcciones

información

puede referenciar

• Todos los procesadores ejecutan el mismo programa (SPMD)
• Los códigos pueden particularizarse en función del índice 

identificador del procesador

• Los datos están en memoria local al empezar una ejecución y se 

devuelven a una memoria local al acabar

• Cualquier comunicación entre procesadores se hace a través de 

paso de mensajes

El Modelo D­RAM (DCM en Kruskal, 1990)

Características 
• Cada procesador dispone de un buffer donde almacenar un mensaje
• Existen primitivas de comunicación:
• Send(v,i)   : Escribe el mensaje almacenado en la variable v en el 

buffer del procesador Pi

• Receive(v)  : Almacena el mensaje que haya en el buffer en la 

variable v y vacía el buffer
• Modelo DCM (Directed connected machine): El coste de enviar un 
mensaje de tamaño n es de la forma:  nt +b  , siendo b  el tiempo de 
latencia y t  el tiempo de envío de una palabra.
mensaje de tamaño n entre nodos conectados es de la forma: nt +b , 
siendo b  el tiempo de latencia y t  el tiempo de envío de una palabra.

• Modelo SCM (Sparse connected machine): El coste de enviar un 

• Pueden existir mecanismos de sincronización
• El coste de ejecutar un algoritmo es el número de ciclos de reloj que 

requiere su ejecución más el tiempo de comunicación

Memoria local
Datos(0)

Memoria local

Datos(1)

Memoria local
Datos(p­2)

Memoria local
Datos(p­1)

Programa(0)

Programa(1)

Programa(p­2)

Programa(p­1)

P0

P1

…

Pp­2

Pp­1

Reloj

Red de interconexión

Tiempo

P0
(m,n)

P1

(m,n)

tb=m/p

tb=m/p

A(m/p:2m/p­1,:) (b)

A(2m/p:3m/p­1,:) (b)

A(3m/p:m­1,:) (b)

(A) (b)

Calcula 
x= A(0:m/p­1,:) b

Calcula 
x= Ab

x

Copiar a x

P2

(m,n)

tb=m/p

P3

(m,n)
tb=m/p

(A) (b)

Calcula 
x= Ab

x

(A) (b)

Calcula 
x= Ab

x

Programa (0)

Programa (1)

Programa (2)

Programa (3)

A b

n

m

A b

n

m

A b

n
m

A b

n

m

P0

A,b,m,n

P1

P2

A,b,m,n

P3

A,b,m,n

Red de interconexión

Programa (0)

Programa (1)

Programa (2)

Programa (3)

x

A b

n

m

x

A b

n

m

x

A b

n
m

x

A b

n

m

P0

P1

P2

P3

Red de interconexión

Programa(0)
x

A b

n

m

Programa(1)

Programa(2)

Programa(3)

x

A b

n

m

x

A b

n

m

x

A b

n

m

P0

x

P1

P2

x

P3

x

Red de interconexión

Entornos de paso de mensajes

•Aparecen los entornos de paso de mensajes que 
facilitan la programación de estas máquinas

– PVM (Parallel Virtual Machine): 1989­1990
– MPI (Message Passing Interface): 1994

•El entorno MPI se ha convertido en el estándar de 
facto del modelo de paso de mensajes
•Ofrece las primitivas de comunicación necesarias 
para implementar las comunicaciones
•Permiten el desarrollo software de herramientas 
eficientes de computación: Librerías Matriciales

Modelo de Programación en MPI
Modelo de Programación en MPI

 

prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI

0
0
0

1
1
1

2
2
2

3
3
3

prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI

prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI

prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI

prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI
prog _MPI

Procesos y Comunicadores (I)

• En MPI, los procesos involucrados en la ejecución de un programa 

paralelo se identifican por una secuencia de enteros, que denominamos 
rangos.

• Si tenemos p procesos ejecutandose en un programa, estos tendrán 

rangos 0,1, ..., p­1.

• Todas las operaciones de comunicación en MPI se realizan dentro de un 

espacio o ámbito, llamado comunicador. 

• Un comunicador contiene un conjunto de procesos pertenecientes a 

una aplicación MPI.

• Cada proceso posee un rango dentro de cada comunicador.

17

INTRODUCCIÓN
INTRODUCCIÓN

Procesos y Comunicadores (II)
Procesos y Comunicadores (II)

• Este rango permite identificar a todos los procesos que 

forman parte de un comunicador.

• El uso de diferentes comunicadores permitirá exclusivizar 

los mensajes enviados entre diferentes partes de un 
programa de forma más cómoda que con el uso de 
etiquetas.

18

INTRODUCCIÓN

Procesos y Comunicadores (y III)

MPI_COMM_WORLD

COMM_4
0
0
2

2
2
0

COMM_1

1
1
1

3
2

7
2

COMM_3
4
1

5
0

6
3

1

8
0

COMM_2

19

Introducción a la Programación en MPI
Introducción a la Programación en MPI

Comunicación entre 
Comunicación entre 

Procesos
Procesos

Comunicación entre Procesos
Comunicación entre Procesos
Construcción de un mensaje (I)
Construcción de un mensaje (I)

Los mensajes en MPI se definen mediante tres Parámetros.
         message: puntero al inicio del mensaje.
         count: número de elementos que posee el mensaje.
         type: tipo de datos de los elementos del mensaje.

 

Memoria

message

1
1
2
2

datatype
datatype

3...
3...
...
...
...
...
...
...
count -1
count -1
count
count

message+count*sizeof(datatype)
message+count*sizeof(datatype)

Comunicación entre Procesos

Operaciones de Comunicación punto a punto (i)

Para hacer el envío de un mensaje en MPI es necesaria la siguiente 
información:

El rango del receptor.
El rango del emisor.
int MPI_Send(void* message, int count, MPI_Datatype datatype, 

Una etiqueta.
El comunicador.

int dest, int tag, MPI_Comm comm)

int MPI_Recv(void* message, int count, MPI_Datatype datatype, 
               int source, int tag, MPI_Comm comm, MPI_Status* status)

Las constantes MPI_ANY_SOURCE y MPI_ANY_TAG se utilizan para 
especificar cualquier fuente y cualquier etiqueta respectivamente.
El último argumento de MPI_Recv es una estructura de dos elementos 
que contiene el rango del emisor y la etiqueta del mensaje.

22

MPI_Bcast

comm

message
1
.
.
.

rank=1

count

message

1
.
.
.

rank=0
Root=0
Root=0

              count

message
1
.
.
.

rank=3

count

message
1
.
.
.

rank=2

count

MPI_Reduce

comm

operand

rank=0

rank=1

*result

1
.
.
.

count

Root=0
Root=0

result

op
operand
1
.
.
.
count

1
.
.
.
count

operand
1
.
.
.

rank=2

*result

count

operand
1
.
.
.

rank=3

*result

count

MPI_Gather

comm

root=0
root=0

rank=0

.

send_buf

recv_buf
1
...

0

                    1
.                     .
                     .
send_count

  4*recv_count

1

2

3

rank=1

send_buf
1...
send_count

*recv_buf

rank=3

send_buf
1...
send_count

*recv_buf

rank=2
send_buf
1...
send_count

*recv_buf

MPI_Scatter

comm

root=0
root=0

rank=0

.

recv_buf

send_buf
1
...

0

                    1
.                     .
                     .
recv_count

  4*send_count

1

2

3

rank=1

recv_buf
1...
recv_count

*send_buf

rank=3

recv_buf
1...
recv_count

*send_buf

rank=2
recv_buf
1...
recv_count

*send_buf

Referencias

• MPI­Forum:    http://www.mpi­forum.org. Disponibles de manera 

electrónica todos los estándares ( MPI 1.1, MPI­2)

• A User’s Guide to MPI. Peter S. Pacheco. Lectura más amena que 

el estándar, acompañado de ejemplos prácticos.

• An Introduction to Message Passing and Parallel Programming with 

MPI.  Dr. Gerhard Wellein, Georg Hager

• A Survey of MPI Implementations. William Shapir. Historia de MPI, 

información sobre implementaciones existentes, herramientas, 
problemas, ejercicios prácticos,…
Introducción a la Programación Paralela. F. Almeida et al. Dedica 
un capítulo al entorno MPI. 

•

Librerías para el modelo de paso de mensajes

 La librería ScaLAPACK. (1995)

• Librería de rutinas de algebra lineal numérica, para 
ordenadores de memoria distribuida con paso de  
mensajes.

• Capacidades similares al LAPACK: Sistemas lineales, 

Mínimos cuadrados, Valores y vectores propios y 
singulares, Descomposiciones matriciales 

• Objetivos:

• Eficiencia
• Escalabilidad
• Fiabilidad
• Portabilidad
• Flexibilidad
• Facilidad de uso

                 

La librería Scalapack. Filosofía y entorno.
Se trata de emplear la misma filosofía de diseño que en el LAPACK:

Núcleos computac