LP-metod

Report
.4.
TIPOS DE PROBLEMAS PARALELOS.
METODOLOGÍA DE DESARROLLO DE
PROGRAMAS PARALELOS.
Laboratorio de Paralelismo
IF - EHU
Índice
1. Introducción.
2. Análisis de algoritmos.
3. Metodología de desarrollo de programas
paralelos.
4. Esquemas de algoritmos paralelos.
5. Problemas numéricos. Librerías.
Laboratorio de Paralelismo
IF - EHU
Introducción
 Los problemas que pueden resolverse mediante un
algoritmo paralelo son, obviamente, muy
heterogéneos.
Suelen ser problemas de complejidad elevada,
aún no perteneciendo al grupo de problemas
intratables (el número de operaciones crece de
forma rápida –p.e. exponencial– con el tamaño del
problema).
Laboratorio de Paralelismo
IF - EHU
4
3
Introducción
4
 Dentro del conjunto de problemas tratables (el
número de operaciones crece polinómicamente con el
tamaño del problema) se suelen dar dos situaciones
que hacen necesaria la programación paralela:
- Problemas de gran dimensión
- Problemas de tiempo real
Otro tipo de problemas: problemas de gran desafío,
por su relevancia social (genoma humano,
meteorología, clima, fenómenos sísmicos…).
Laboratorio de Paralelismo
IF - EHU
4
Introducción
4
5
 Diferentes modelos sobre distintos aspectos de la
programación paralela:
- Modelo arquitectónico: arquitectura de la máquina
-- multiprocesadores: memoria compartida
-- multicomputadores: paso de mensajes
-- modelos mixtos
- Modelo de programación: herramientas de alto nivel
(OpenMP, MPI).
- Modelo de coste: permite evaluar el coste del
algoritmo.
Laboratorio de Paralelismo
IF - EHU
Índice
1. Introducción.
2. Análisis de algoritmos.
3. Metodología de desarrollo de programas
paralelos.
4. Esquemas de algoritmos paralelos.
5. Problemas numéricos. Librerías.
Laboratorio de Paralelismo
IF - EHU
Análisis de algoritmos
4
 En la programación paralela (al igual que en la
secuencial) son necesarias herramientas que permitan
estimar el tiempo de ejecución y la memoria
consumidos por un algoritmo, para determinar si es
adecuado o no para la resolución del problema.
El objetivo es desarrollar algoritmos eficientes
(eficiencia: relación entre los recursos que consume
y los resultados que obtiene).
Laboratorio de Paralelismo
IF - EHU
7
Análisis de algoritmos
4
 Factores que influyen en el tiempo de ejecución de un
programa:
-
el lenguaje de programación (el programador)
la máquina
el compilador (opciones)
los tipos de datos
los usuarios que estén trabajando en el sistema
Laboratorio de Paralelismo
IF - EHU
8
Análisis de algoritmos
4
9
 Factores que influyen en el tiempo de ejecución de un
programa paralelo:
-
la
la
la
la
competencia por la memoria (bloques de cache)
fracción de código secuencial (Amdahl)
creación/asignación de procesos
computación extra: variables de control,
identificación de procesos, cálculos
adicionales…
- la comunicación (para memoria distribuida)
- la sincronización
- los desequilibrios de carga
Laboratorio de Paralelismo
IF - EHU
Análisis de algoritmos
4
 Estudio del algoritmo a priori
Antes de hacer el programa correspondiente.
Sirve para identificar si el algoritmo es adecuado para
el problema, o para seleccionar entre varios
algoritmos.
También sirve para determinar el tamaño de los
problemas a resolver en función de las limitaciones
de tiempo y memoria.
Laboratorio de Paralelismo
IF - EHU
10
Análisis de algoritmos
 Estudio a posteriori
Tras haber hecho el programa.
Sirve para comparar entre dos programas según el
tamaño de entrada.
También para encontrar fallos o posibles mejoras de
un programa.
 Estudio teórico (a priori o posteriori) y estudio
experimental (a posteriori).
Laboratorio de Paralelismo
IF - EHU
4
11
Análisis de algoritmos
 Tipos de estudios teóricos:
Tiempo de ejecución (ej. ordenación)
- caso más favorable, cota inferior:
tm (n)
- caso más desfavorable, cota superior: tM (n)
- caso promedio:
tp (n)
t p n   t n,  p 
donde:
 S
n es el tamaño de la entrada
 es una entrada de las S posibles entradas
Laboratorio de Paralelismo
IF - EHU
4
12
Análisis de algoritmos
 Tipos de estudios teóricos:
Ocupación de memoria
- caso más favorable, cota inferior:
mm (n)
- caso más desfavorable, cota superior: mM (n)
- caso promedio:
mp (n)
mp n   mn,   p 
 S
donde:
n es el tamaño de la entrada
 es una entrada de las S posibles entradas
Laboratorio de Paralelismo
IF - EHU
4
13
Análisis de algoritmos
4
14
 Conteo de instrucciones
- decidir qué instrucciones/operaciones (flop) se
quieren contar.
- asignar costes a instrucciones de cada tipo.
- una función: coste de las instrucciones que la
componen.
- bucles: mediante sumatorios o cotas superior e inferior
si no se conoce el número de veces que se ejecutará.
- bifurcaciones: contar el número de veces que pasa por
cada rama, o establecer una cota superior (rama más
costosa) o una inferior (rama menos costosa).
Laboratorio de Paralelismo
IF - EHU
Análisis de algoritmos
4
 Conteo de instrucciones (caso promedio)
t p n   i 1 t p n, i 
k
k
número de instrucciones del programa
tp (n,i) número promedio de veces que la instrucción
i se ejecuta para una entrada de tamaño n
t p n, i    j 1 pi, j  j

p (i,j) probabilidad de que la instrucción i se ejecute
j veces
Laboratorio de Paralelismo
IF - EHU
15
Análisis de algoritmos
4
 Notación asintótica
Dado que lo que interesa es saber cómo se comporta
el algoritmo cuando crece el tamaño de la entrada
(tamaños grandes), ya que es cuando podemos
tener problemas de tiempo, se suelen utilizar
notaciones asintóticas.
Acotan la forma en que crece el tiempo de ejecución
cuando el tamaño de la entrada tiende a infinito, sin
tener en cuenta las constantes que le afectan.
Laboratorio de Paralelismo
IF - EHU
16
4
Análisis de algoritmos
17
 Acotar superiormente, orden de f:


O f   te : N   / k   , n0  N , n  n0 : ten  k f n
 Acotar inferiormente, omega de f:


 f   te : N   / k   , n0  N , n  n0 : ten  k f n
 Acotar sup. e inferiormente, orden exacto de f:
  f   te : N   / k, l   , n0  N , n  n0 : k f n  ten  l f n
Laboratorio de Paralelismo
IF - EHU
4
Análisis de algoritmos
18
 A nivel práctico, a veces interesa no perder la
información de las constantes del término de
mayor orden:

ten 

o f   te : N   / lim
 1
n f n 


 Algunas relaciones entre órdenes:
 
O1  Ologn  O n  On  On logn 
 
 
 
 
 On log n log n  O n2  O n3  ...  O 2n  On!  O nn
Laboratorio de Paralelismo
IF - EHU
Análisis de algoritmos
4
 Factores que afectan al tiempo de ejecución de un
programa paralelo:
t n, p  tcalc n, p  tcom n, p  toverhead n, p  toverlapping n, p
Estimación del tiempo de ejecución real
tcalc n, p 
Conteo de instrucciones
tcom n, p 
¿?
Laboratorio de Paralelismo
IF - EHU
19
Análisis de algoritmos
 Tiempo de comunicación punto a punto entre dos
procesadores:
tcom  ts  tw n
 Tiempo de comunicación de un mensaje dividido en
paquetes a distancia d:
tcom
 Lmens

 d t s  t w L paq   
 1 t s  t w L paq 
L

paq


 En general, conviene agrupar mensajes (full duplex?,
red conmutada?, Ethernet…)
Laboratorio de Paralelismo
IF - EHU
4
20
Análisis de algoritmos
 Ejemplo: suma de n números
s = a[0];
for(i=1; i<n; i++)
s = s + a[i];
 Tiempos de la versión secuencial:
- conteo de instrucciones: t(n) = tcalc(n) = 2n - 1
- conteo de operaciones: t(n) = tcalc(n) = n - 1
Laboratorio de Paralelismo
IF - EHU
4
21
Análisis de algoritmos
 Ejemplo: suma de n números (memoria compartida)
- una versión paralela con n/2 procesos
doall pid = 0, n/2-1
{
ini = 2 * pid;
des = 1;
act = true;
for (k=1; k++; k <= log n)
{
if (act) {
a[ini] = a[ini] + a[ini+des];
des = des * 2;
}
if ((i mod des)!=0) act = false;
}
}
Laboratorio de Paralelismo
IF - EHU
4
22
4
Análisis de algoritmos
 Ejemplo: suma de n números (memoria compartida)
- una versión paralela con n/2 procesos (memoria compartida):
0
1
0, 1
2
3
2, 3
0, 1, 2, 3
4
5
4, 5
IF - EHU
7
6, 7
4, 5, 6, 7
0, 1, 2, 3, 4, 5, 6, 7
Laboratorio de Paralelismo
6
k=1
k=2
…
k = log n
23
Análisis de algoritmos
4
 Ejemplo: suma de n números (memoria compartida)
 Tiempos de la versión paralela (mem. compartida):
- conteo de instrucciones: tcalc(n, n/2) = 3 + 6 log n
- conteo de operaciones: tcalc(n, n/2) = log n
(+ sincronización tras cada iteración)
 Problemas:
- distribución del trabajo entre procesos
- overheads = variables auxiliares, comprobaciones…
- ley de Amdahl
Laboratorio de Paralelismo
IF - EHU
24
Análisis de algoritmos
 Ejemplo: suma de n números (memoria distribuida)
- una versión paralela con n/2 procesos
doall Pi, i = 0, n/2-1 {
des = 1;
act = true;
for (k=1; k++; k <= log n -1) {
if (act) {
a = a + b;
des = des * 2;
if ((i mod des)!=0) {
act = false;
Envia (a, Pi-des/2);
}
else Recibe (b, Pi+des/2);
}
}
if (i = 0) a = a + b;
}
Laboratorio de Paralelismo
IF - EHU
4
25
4
Análisis de algoritmos
 Ejemplo: suma de n números (mem. distribuida)
 Tiempos de la versión paralela (mem. distribuida):
- instrucciones:
- operaciones:
tcalc(n, n/2) = 4+6 (log n -1)
tcalc(n, n/2) = log n
- comunicación:
tcom(n, n/2) = (log n -1) (ts + tw)
(suponiendo comunicaciones directas y en paralelo)
 Problemas:
- añade la comunicación y su gestión, cuyo coste
puede influir más o menos
Laboratorio de Paralelismo
IF - EHU
26
4
Análisis de algoritmos
 Ejemplo: suma de n números (mem. distribuida)
speed-up para n=64 y p=32 según relación entre ts, tw y top
sistema
mem.
compartida
flops
4.70
10.50
mem.
distribuida
ts = tw
tw = top
2.89
3.94
mem.
distribuida
ts = 2 tw
tw = 2 top
1.98
1.75
mem.
distribuida
ts = 10 tw
tw = 10 top
0.22
0.11
Laboratorio de Paralelismo
IF - EHU
intrucciones
27
Análisis de algoritmos
4
 Algunas conclusiones:
- No tiene sentido suponer p ilimitado para una
entrada constante (eliminar la restricción n = 2p),
n y p deben ser independientes.
- No tiene sentido utilizar programación paralela
para resolver problemas pequeños. Mejor
resolverlos secuencialmente. En el ejemplo, el
coste es lineal, y, por tanto, no es adecuado.
- Dependiendo de la plataforma, un programa
derivado de un algoritmo puede proporcionar unas
prestaciones muy diferentes.
Laboratorio de Paralelismo
IF - EHU
28
4
Análisis de algoritmos
29
 Medidas de prestaciones:
t n 
S n, p  
t n, p 
- Speed-up
 Ejemplo: suma de n números (instr./flops)
- Memoria compartida
2n  1
S n, p  
2
n
 6 log p
p
S n, p  
n 1
n
 log p  1
p
- Memoria distribuida
2n  1
S n, p  
2
Laboratorio de Paralelismo
IF - EHU
n
 6 log p  4  log p  1t s  t w 
p
S n, p  
n 1
n
 log p  1  log p  1t s  t w 
p
4
Análisis de algoritmos
 Medidas de prestaciones:
- Eficiencia
S n, p 
t n 
E n, p  

p
p * t n, p 
 Ejemplo: suma de n números (flops)
- Memoria compartida
- Memoria distribuida
Laboratorio de Paralelismo
IF - EHU
E n, p  
E n, p  
n 1
n  p log p  p
n 1
n  p log p  p  plog p  1t s  t w 
30
4
Análisis de algoritmos
 Medidas de prestaciones:
- Coste
C n, p   p *t n, p 
- Función overhead:
tover n, p  Cn, p  t n  p * t n, p  t n
 Ejemplo: suma de n números (flops)
- Memoria compartida
- Memoria distribuida
Laboratorio de Paralelismo
IF - EHU
Cn, p   n  p log p  p
tover n, p  p log p  p  1
Cn, p  n  p log p  p  plog p 1ts  tw 
tover n, p  p log p  p  1
31
Análisis de algoritmos
4
 Escalabilidad
Que se mantengan las prestaciones al aumentar p y el
tamaño del problema.
 Función de isoeficiencia
Indica la forma en la que debe aumentar el tamaño de la
entrada en función del tamaño del sistema para mantener
las prestaciones (despejar n en función de p).
t n 
t n 
t n
E n, p  


K
p * t n, p  C n, p  tover n, p   t n 
K
t n  
tover n, p   K ' tover n, p 
1 K
Laboratorio de Paralelismo
IF - EHU
32
4
Análisis de algoritmos
 Ejemplo: suma de n números (flops)
Memoria compartida
- manteniendo proporcional el coste del secuencial a la función
overhead:
t n  n 1  p log p  p  1  tover n, p
- comparando los términos de mayor orden:
I(p) = p log p
Memoria distribuida
- manteniendo proporcional el coste del secuencial a la función
overhead:
n 1  p log p  p  1  plog p 1ts  tw 
- comparando los términos de mayor orden:
Laboratorio de Paralelismo
IF - EHU
I(p) = p log p
33
4
Análisis de algoritmos
 Ejemplo: suma de n números (flops)
- en ambos casos
I(p) = p log p
Incremento de procesadores
Aumento de tamaño del
problema necesario para
mantener la eficiencia
4 a 16
16 a 64
64 a 256
8
6
5.33
p2 log p2
p1 log p1
Laboratorio de Paralelismo
IF - EHU
34
Índice
1. Introducción.
2. Análisis de algoritmos.
3. Metodología de desarrollo de
programas paralelos.
4. Esquemas de algoritmos paralelos.
5. Problemas numéricos. Librerías.
Laboratorio de Paralelismo
IF - EHU
Metodología
 Es diferente paralelizar un algoritmo o programa
secuencial, que programar en paralelo una
aplicación desde el comienzo.
 En el primer caso, interesa detectar aquellas partes
del código con un mayor coste computacional.
Lo más habitual es utilizar trazas, timers, profiling, etc.,
y ejecutar en paralelo aquellas partes que ofrecen un
buen rendimiento (por ejemplo, paralelismo incremental
de OpenMP).
Laboratorio de Paralelismo
IF - EHU
4
36
Metodología
4
 En el segundo caso, se empieza analizando las características de la propia aplicación, para determinar el/los
algoritmos paralelos más adecuados.
OJO: conviene partir de un buen algoritmo ya optimizado
(¡no hay que reinventar la rueda!).
 Aunque no hay un “camino único”, se suele
recomendar utilizar un determinado procedimiento o
metodología.
Laboratorio de Paralelismo
IF - EHU
37
Metodología
 La programación paralela añade, respecto a la
programación secuencial, una serie de aspectos a
tener en cuenta:
- Concurrencia (sincronización, comunicación).
- Asignación de datos y código a procesadores.
- Acceso simultáneo a datos compartidos
(sincronización).
- Escalabilidad.
Laboratorio de Paralelismo
IF - EHU
4
38
Metodología
4
 Otra diferencia entre la programación secuencial y la
paralela es la forma en que los módulos que
componen una aplicación se pueden ensamblar:
- Composición secuencial: los módulos se ejecutan
secuencialmente.
- Composición paralela: diferentes módulos se
ejecutan simultáneamente sobre conjuntos disjuntos
de procesos (escalabilidad y localidad).
- Composición concurrente: diferentes módulos se
ejecutan concurrentemente sobre los mismos
procesos (solapamiento computación y comunicación).
Laboratorio de Paralelismo
IF - EHU
39
Metodología
PROBLEMA
Modelo PCAM
Particionado
Comunicación
Aglomerado
Mapeado
Laboratorio de Paralelismo
IF - EHU
4
40
Metodología
PROBLEMA
Modelo PCAM
4
Particionado
Descomposición
Comunicación
(tareas+comunicación)
Aglomerado
Asignación (tareas a procesos)
Mapeado
Laboratorio de Paralelismo
IF - EHU
41
Metodología
Descomposición
4
 La descomposición consiste en dividir el cálculo en
partes de menor tamaño que vamos a denominar
tareas, con el objetivo de ejecutarlas en paralelo.
 Según el tamaño (coste computacional) de las tareas
se habla de:
- granularidad fina (muchas tareas pequeñas).
- granularidad gruesa (pocas tareas grandes).
Laboratorio de Paralelismo
IF - EHU
42
Metodología
Descomposición
 Es deseable obtener un número suficientemente alto
de tareas (grano fino) para tener más flexibilidad en
la fase de asignación.
 En esta fase es fundamental tener en cuenta las
dependencias entre las tareas y reflejarlas en un
grafo de dependencias para poder estimar las
necesidades de sincronización y estructura de
comunicación que hay entre las tareas.
Laboratorio de Paralelismo
IF - EHU
4
43
Metodología
Descomposición
4
 Ejemplo 1: Evaluación polinomial
Se trata de evaluar, para un valor x = b, m funciones
polinomiales de grado n
f i (x) con i=0,…,m-1; y
obtener el valor mínimo.
 Un posible reparto es asignar una tarea a la evaluación
de cada polinomio (o conjunto de polinomios) y luego
ir calculando el mínimo entre las tareas.
Laboratorio de Paralelismo
IF - EHU
44
Metodología
4
Descomposición
 Ejemplo 1: Evaluación polinomial
Veamos dos grafos de dependencias entre las tareas
(para el caso de 4 polinomios), con sus costes
computacionales (cc=5 para evaluar y cc=1 para calcular
el mínimo):
(a)
f0(b)
5
f1(b)
5
min
1
IF - EHU
f2(b)
5
f3(b)
5
min
1
min
1
Laboratorio de Paralelismo
(b)
f0(b)
5
f1(b)
5
f2(b)
5
f3(b)
5
min
1
min
1
min
1
45
Metodología
Descomposición
4
46
 Mediante el grafo de dependencias se puede establecer
el máximo grado de concurrencia de un algoritmo.
Para caracterizar el paralelismo potencial de un
algoritmo se suele calcular el grado medio de
concurrencia (gmc), es decir, el número medio de
tareas que se podrían ejecutar en paralelo.
1 N
gm c  cc(nodoi )
L i 1
L: long. camino crítico
cc: coste computacional
Laboratorio de Paralelismo
IF - EHU
gmc(grafo a) = 23/7 = 3,28
gmc(grafo b) = 23/8 = 2,875
Metodología
4
Descomposición
 Para el ejemplo 1 (evaluación polinomial) el grafo
con la estructura de comunicación necesaria para
el caso de paso de mensajes sería:
Lectura+reparto
4
4
4
4
f0(b)
f1(b)
f2(b)
f3(b)
5
5
5
5
1
1
1
1
min
min
1
1
1
1
min
1
Laboratorio de Paralelismo
IF - EHU
Patrón de comunicación
(recursiva)
47
Metodología
Descomposición
4
 Algunas técnicas de descomposición
- Descomposición de dominio (salida/entrada/bloques)
- Descomposición funcional (flujo de datos)
- Descomposición recursiva
- Descomposición exploratoria
- Descomposición especulativa
Laboratorio de Paralelismo
IF - EHU
48
Metodología
Descomposición
 Algunas técnicas de descomposición
- Descomposición de dominio
- Centrada en los datos de salida
 Ejemplo 2: diferencias finitas Jacobi
Patrón de comunicación
X i(,tj1) 
4 X i(,tj)  X i(t1), j  X i(t1), j  X i(,tj)1  X i(,tj)1
Laboratorio de Paralelismo
IF - EHU
8
4
49
Metodología
4
Descomposición
 Algunas técnicas de descomposición
- Descomposición de dominio
- Centrada en los datos de entrada
 Ejemplo 3: Producto escalar de dos vectores
Producto escalar de vectores de longitud n con p tareas
pepid 
n
( pid 1) 1
p
x y
j
j  pid
n
p
j
pe 
p 1
 pe
pid 0
pid
Suma final patrón recursivo (≈ ejemplo1)
Laboratorio de Paralelismo
IF - EHU
50
Metodología
4
Descomposición
 Algunas técnicas de descomposición
- Descomposición de dominio
- Basada en bloques (algoritmos matriciales)
 Ejemplo 4: Multiplicación matriz-vector (x=Ab)
Producto matriz-vector con 2 tareas
Laboratorio de Paralelismo
IF - EHU
A00
A01
A10
A11
×
b0
b1
=
x0
x1
A00
A01
A10
A11
tarea 0
tarea 1
51
Metodología
4
Descomposición
52
 Algunas técnicas de descomposición
- Descomposición funcional
Dirigida por el flujo de datos, se identifican las partes
funcionales del cálculo y se asocian con tareas. Luego se
hace un análisis del solapamiento de datos y del flujo de
datos entre tareas para validar o no la división planteada.
 Ejemplo 5: Filtrar una lista de enteros
Se desea encontrar aquellos números de una lista
(longitud n) que sean múltiplos de todos los números
primos pertenecientes a otra lista (longitud m, m<<n)
lista
entrada
Laboratorio de Paralelismo
IF - EHU
múltiplo
de 3?
múltiplo
de 5?
múltiplo
de 7?
tarea 0
tarea 1
tarea 2
lista
salida
Otros
diagramas
de flujo
Metodología
Descomposición
 Algunas técnicas de descomposición
- Descomposición recursiva
- aplicación de la técnica divide-y-vencerás.
- se generan subproblemas que son instancias del
original pero independientes entre sí.
- se sigue dividiendo hasta que no merezca la pena.
- al final, combinación de resultados.
- esquema de planificación adecuado: granja de
tareas (estructura de datos compartida).
Laboratorio de Paralelismo
IF - EHU
4
53
Metodología
Descomposición
4
 Algunas técnicas de descomposición
- Descomposición recursiva
 Ejemplo 6: Integración numérica por
cuadratura adaptativa
Se desea aproximar numéricamente el valor de una
integral, es decir, el área bajo la curva de una función.
Objetivo: una precisión determinada. No se conocen a
priori el número de iteraciones y hay que definir un criterio
de parada.
Laboratorio de Paralelismo
IF - EHU
54
Metodología
Descomposición
 Algunas técnicas de descomposición
- Descomposición exploratoria
- problemas de búsqueda de soluciones en un
espacio de estados.
- ir descomponiendo el espacio de búsqueda en
partes de menor tamaño para irlas asignando a
tareas diferentes.
- normalmente se estructura el espacio de
búsqueda en forma de árbol.
- el criterio de parada puede ser cuando se
encuentra la primera solución o cuando se han
explorado todos los nodos del árbol.
Laboratorio de Paralelismo
IF - EHU
4
55
Metodología
Descomposición
 Algunas técnicas de descomposición
- Descomposición exploratoria
 Ejemplo 7: Suma del subconjunto
Se trata de encontrar las posibles combinaciones de
números pertenecientes a un conjunto determinado tales
que la suma de los mismos valga un valor s concreto.
Se puede plantear como un algoritmo de búsqueda en el
que se van seleccionando los diferentes elementos del
conjunto determinando los subconjuntos cuya suma tiene
un valor de s.
Laboratorio de Paralelismo
IF - EHU
4
56
Metodología
Descomposición
4
 Algunas técnicas de descomposición
- Descomposición exploratoria
 Ejemplo 7: Suma del subconjunto
----
tarea i
0--00--
Laboratorio de Paralelismo
IF - EHU
tarea j
1--01--
ojo, reparto de trabajo!
57
Metodología
4
Descomposición
 Algunas técnicas de descomposición
- Descomposición especulativa
- en este tipo de descomposición se adelanta cálculo
que hay que realizar selectivamente (todas las
ramas o las estimadas más probables) para reducir el
tiempo medio de respuesta.
Cálculo tipo1
Cálculo tipo2
Entrada
…
Cálculo tipoX
Cálculo selección
Laboratorio de Paralelismo
IF - EHU
Salida
58
Metodología
Descomposición
 Algunas técnicas de descomposición
- Enfoques mixtos
En muchas ocasiones hay que aplicar diferentes
esquemas de descomposición para extraer paralelismo en
diferentes fases de procesamiento de una aplicación.
En el ejemplo 1 –evaluación polinomial– hemos aplicado
descomposición de dominio para realizar la evaluación
de los polinomios y descomposición recursiva para
calcular el mínimo de las evaluaciones.
Laboratorio de Paralelismo
IF - EHU
4
59
Metodología
Descomposición
 Algunas técnicas de descomposición
- Enfoques mixtos
Caso meteorológico/climático
> Paralelismo de datos
Laboratorio de Paralelismo
IF - EHU
> Paralelismo de función
4
60
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Características de las tareas
-- Creación estática/dinámica
Según se conozcan a priori las tareas a realizar
(ejemplo 2 – jacobi) o se vayan generando durante la
ejecución del programa (ejemplo 6 – integración
numérica).
Laboratorio de Paralelismo
IF - EHU
61
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Características de las tareas
-- Número de tareas obtenidas
Debería de ser suficientemente grande para facilitar
la fase de asignación de tareas.
Aconsejable obtener un orden de magnitud más de
tareas que de procesadores (si la aplicación lo
permite).
Es importante que el número de tareas escale con el
tamaño del problema.
Laboratorio de Paralelismo
IF - EHU
62
Metodología
Descomposición
 Factores a considerar en la descomposición
- Características de las tareas
-- Tamaño de las tareas
Interesa que el coste (computacional) de las
diferentes tareas sea similar y se pueda estimar a
priori (esto dependerá del problema), para evitar
problemas de load-balancing durante el reparto a
procesadores.
Laboratorio de Paralelismo
IF - EHU
4
63
Metodología
Descomposición
 Factores a considerar en la descomposición
- Características de las tareas
-- Tamaño de las tareas
Esto es fácil en los ejemplos 1, 2 y 3 –evaluación
polinomial, jacobi y producto escalar– pero no lo
es para el ejemplo 7 –suma del subconjunto– si se
aplican técnicas de poda.
Laboratorio de Paralelismo
IF - EHU
4
64
Metodología
Descomposición
 Factores a considerar en la descomposición
- Características de las tareas
--
Replicación de datos/cálculo
Conviene evitar que las tareas compartan mucho
cálculo o datos del problema.
--
Tamaño y localización de los datos
asociados a cada tarea
Deben ser accesibles por el proceso que ejecuta esa
tarea (fase de asignación) y hay que evitar una
sobrecarga por cálculo y/o comunicación.
Laboratorio de Paralelismo
IF - EHU
4
65
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Patrones locales/globales
Un patrón de comunicación se dice que es local
cuando cada tarea interacciona sólo con un
subconjunto pequeño de tareas (vecinas).
Se utiliza el grafo de dependencias para determinar las
necesidades de comunicación o sincronización.
Laboratorio de Paralelismo
IF - EHU
66
Metodología
Descomposición
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Patrones locales/globales
El ejemplo 2 –jacobi– es un caso de patrón local de
comunicación.
Laboratorio de Paralelismo
IF - EHU
4
67
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Patrones locales/globales
Un patrón de comunicación se dice que es global
cuando múltiples tareas aportan datos para realizar un
cálculo en paralelo. Ejemplo 3 – producto escalar.
Descomp. recursiva
Comunicación global (centralizado)
Laboratorio de Paralelismo
IF - EHU
Distribución de cálculo y comunicación
68
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Patrones estáticos/dinámicos
En los estáticos se conoce a priori qué tareas y
cuándo se comunican.
Los ejemplos 1, 2 y 3 –eval. polinomial, jacobi y
producto escalar– tienen patrones de comunicación
estáticos.
Sin embargo, en el ejemplo 6 –integración numérica–
no se sabe a priori cuándo se va a producir la
actualización del área global, ya que depende de la
función que se esté integrando.
Laboratorio de Paralelismo
IF - EHU
69
Metodología
Descomposición
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Patrones regulares/irregulares
Se habla de patrón regular cuando la comunicación
presenta una topología espacial. Los patrones
regulares simplifican la etapa de asignación y
programación en el modelo de paso de mensajes.
En el ejemplo 2 –jacobi– la comunicación se realiza
entre las cuatro tareas vecinas en la malla.
El ejemplo 6 –integración numérica– presenta un
patrón de comunicación irregular.
Laboratorio de Paralelismo
IF - EHU
4
70
Metodología
Descomposición
4
 Factores a considerar en la descomposición
- Patrones de comunicación entre tareas
-- Datos compartidos de lectura/lectura+escritura
-- Comunicación unilateral/bilateral
En la comunicación unilateral la comunicación de una
tarea con otra tarea (productora) se hace sin
interrumpirla; sin embargo, en la bilateral la
comunicación se hace de forma explícita entre la tarea
productora y la tarea que precisa de los datos.
En el modelo de paso de mensajes la comunicación
unilateral se convierte en bilateral, y con patrón irregular,
la dificultad aumenta (ejemplo 9 –suma del subconjunto
9– con poda).
Laboratorio de Paralelismo
IF - EHU
71
Metodología
Asignación
4
 Tras la fase de descomposición se obtiene un
algoritmo paralelo de grano fino, independiente de la
plataforma paralela que se vaya a usar para su
ejecución.
La fase de asignación es en la que se decide qué
tareas agrupar y en qué unidades de procesamiento
se va a ejecutar cada tarea y en qué orden. Por ello,
es en esta fase en la que se tienen en cuenta aspectos
de la plataforma paralela como: número de
unidades de procesamiento, modelo de memoria
compartida o paso de mensajes, costes de
sincronización y comunicación, etc.
Laboratorio de Paralelismo
IF - EHU
72
Metodología
Asignación
 Agrupamiento y replicación en la asignación
Mediante el agrupamiento de tareas se consigue
minimizar el volumen de datos a transferir entre
las tareas y se reduce el número de interacciones
entre ellas (también se suelen agrupar mensajes).
La replicación de datos y de cómputo/comunicación
también se utilizan para reducir el tiempo de
ejecución. ¡Ojo! Limitan la escalabilidad de la
aplicación.
Laboratorio de Paralelismo
IF - EHU
4
73
Metodología
Asignación
4
 En esta fase se asocian las tareas a los procesos
(entidades abstractas capaz de ejecutar cálculo) y no
a los procesadores (entidad física, hardware) para
mantener un mayor nivel de abstracción que
aumente la flexibilidad del diseño.
Será en las últimas fases de implementación del
algoritmo cuando se asignen los procesos a
procesadores (normalmente, uno a uno).
Laboratorio de Paralelismo
IF - EHU
74
Metodología
Asignación
4
 Objetivos de la asignación:
- Reducir el tiempo de computación.
- Minimizar el tiempo de comunicación.
- Evitar el tiempo de ocio (por mal reparto de carga
o por esperas en sincronizaciones/comunicaciones).
 Dos tipos generales de esquemas de asignación:
- Asignación estática (técnicas de planificación
deterministas).
- Asignación dinámica.
Laboratorio de Paralelismo
IF - EHU
75
Metodología
Asignación
4
 Asignación estática
Cuando se conoce o se puede estimar a priori el
coste computacional de las tareas y las relaciones
entre ellas, y, por tanto, se decide a priori qué unidad
de proceso ejecutará cada tarea.
El problema de asignación estática óptima es NPcompleto  técnicas heurísticas.
La gran ventaja frente a los dinámicos es que no
añaden ninguna sobrecarga en tiempo de ejecución.
Laboratorio de Paralelismo
IF - EHU
76
Metodología
Asignación
4
 Asignación dinámica
Se utiliza cuando las tareas se generan
dinámicamente (ejemplo 6 –integración numérica–),
o cuando no se conoce a priori el tamaño de las
tareas (ejemplo 7 –suma del subconjunto– con
poda).
Es más compleja que la estática: ¿cómo redistribuir el
trabajo en tiempo de ejecución?
Laboratorio de Paralelismo
IF - EHU
77
Metodología
Asignación
4
 Esquemas de asignación estática
Algunos se centran en métodos para
descomposición de dominio (distribuciones de
matrices por bloques, diferencias finitas en una malla
bidimensional…).
Otros se centran en métodos sobre grafos de
dependencias estáticas (normalmente obtenidas
mediante descomposición funcional o recursiva).
Laboratorio de Paralelismo
IF - EHU
78
Metodología
Asignación
 Esquemas de asignación dinámica
Cuando se aplican descomposiciones recursivas o
exploratorias suele ser más adecuado utilizar
esquemas de asignación dinámica.
Uno de los problemas a afrontar es la necesidad de
un mecanismo de detección de fin de trabajo.
Laboratorio de Paralelismo
IF - EHU
4
79
Metodología
4
Asignación
 Esquemas de asignación dinámica
- Esquemas centralizados: maestro – esclavos
Maestro
Colección de subproblemas
Petición de subproblemas / Resultados
Subproblemas
Esclavo 0
Laboratorio de Paralelismo
IF - EHU
Esclavo 1
…
Esclavo p-1
80
Metodología
Asignación
 Esquemas de asignación dinámica
- Esquemas centralizados: maestro – esclavos
Adecuado con un número moderado de esclavos y
cuando el coste de ejecutar los subproblemas es alto
comparado con el coste de obtenerlos.
Algunas estrategias para mejorar la eficiencia
(reduciendo la interacción entre maestro y esclavos):
- Planificación por bloques.
- Colecciones locales de subproblemas.
- Captación anticipada (solapar cálculo y comunic.).
Fácil determinación de fin (en el maestro).
Laboratorio de Paralelismo
IF - EHU
4
81
Metodología
4
Asignación
 Esquemas de asignación dinámica
- Esquemas completamente descentralizados
No existe un proceso maestro; los subproblemas se
encuentran distribuidos por todos los procesos.
Proceso i
Proceso j
Colección de subproblemas
Colección de subproblemas
Proceso k
Colección de subproblemas
Laboratorio de Paralelismo
IF - EHU
82
Metodología
Asignación
4
 Esquemas de asignación dinámica
- Esquemas completamente descentralizados
El equilibrio de carga es más difícil y requiere poder
transferir subproblemas a procesos ociosos (cuántos?):
- Transferencia iniciada por el receptor
(sondeo aleatorio, sondeo cíclico…)
- Transferencia iniciada por el emisor (cargas bajas)
La detección de fin es más compleja (algoritmo de
terminación de Dijkstra…)
Laboratorio de Paralelismo
IF - EHU
83
Índice
1. Introducción.
2. Análisis de algoritmos.
3. Metodología de desarrollo de programas
paralelos.
4. Esquemas de algoritmos paralelos.
5. Problemas numéricos. Librerías..
Laboratorio de Paralelismo
IF - EHU
Esquemas de algoritmos paralelos
4
 Un esquema algorítmico es un patrón común a la
resolución de distintos problemas.
En el caso paralelo se encuentran versiones
paralelas de esquemas secuenciales, esquemas que
son propiamente paralelos (maestro-esclavo,
granja de procesos…) o esquemas que son adecuados
para ciertos sistemas o topologías paralelas o para
esquemas concretos de descomposición/asignación
vistos en el apartado anterior.
Laboratorio de Paralelismo
IF - EHU
85
Esquemas de algoritmos paralelos
 Paralelismo de datos (bucles)
Normalmente en memoria compartida trabajando
distintos threads o procesos sobre una estructura de
datos común pero en zonas diferentes.
Algunos ejemplos:
- Suma de n números
- Ordenación por rango
- Evaluación polinomial (ejemplo 1)
- Multiplicación matriz-vector (ejemplo 4)
- Integración numérica (ejemplo 6)
Laboratorio de Paralelismo
IF - EHU
4
86
Esquemas de algoritmos paralelos
4
 Particionado de datos
Es una especie de paralelismo de datos con paso de
mensajes.
La diferencia está en que no sólo se reparte el trabajo
sino que hay que distribuir los datos entre los
procesos. Por tanto, hay que tener en cuenta las
necesidades de comunicación entre procesos (y la
topología sobre la que se trabaja).
Los mismos ejemplos que en el paralelismo de datos
se pueden programar mediante el particionado de
datos.
Laboratorio de Paralelismo
IF - EHU
87
Esquemas de algoritmos paralelos
4
 Esquemas en árbol y grafo
Muchos problemas tienen una representación en
forma de árbol (por ejemplo, la suma de n números).
Este tipo de problemas se resuelven asignando el
trabajo de diferentes nodos a distintos procesos, de
manera que la carga esté equilibrada.
Para minimizar sincronizaciones/comunicaciones la
asignación habrá que hacerla de manera que se
minimice el número de arcos entre nodos asignados a
procesos distintos.
Algunos ejemplos: barreras en árbol, mergesort…
Laboratorio de Paralelismo
IF - EHU
88
Esquemas de algoritmos paralelos
 Esquemas en árbol y grafo
Algoritmos de ordenación, de cálculo de
máximos...
(en general, “búsquedas” de algún tipo en grandes
cantidades de datos)
-- reparto de las tareas entre los procesadores, que
procesarán localmente un subconjunto de los
datos.
-- puede haber algo de comunicación, durante el
proceso de los datos o al final del mismo.
Laboratorio de Paralelismo
IF - EHU
4
89
4
Esquemas de algoritmos paralelos
 Esquemas en árbol y grafo
Interacciones entre N cuerpos (the N-body problem)
Cálculo de la posición y velocidad de cuerpos en el espacio
(o de partículas cargadas...).
F = G (M1M2/R2)
→
F = m Δv/Δt
→
Δx = v Δt
Cálculo de orden O(N3) → en paralelo, muchos mensajes,
ya que todos los cuerpos interaccionan con todos en
cada iteración de la simulación.
Laboratorio de Paralelismo
IF - EHU
90
Esquemas de algoritmos paralelos
 Esquemas en árbol y grafo
Interacciones entre N cuerpos (the N-body problem)
Reducir la comunicación mediante técnicas de clustering.
r
Laboratorio de Paralelismo
IF - EHU
d
Un grupo de cuerpos se
considera como uno solo
situado en el centro de
masas si se cumple, por
ejemplo, que r > d / .
4
91
Esquemas de algoritmos paralelos
 Algoritmos relajados o paralelismo “obvio”
(embarrassingly parallel)
El cálculo de cada proceso es independiente por lo
que no hay sincronización ni comunicación, excepto,
quizás, al comienzo y al final.
Algunos ejemplos: suma de n números, ordenación
por rango, multiplicación matrices, el ejemplo 6 de
integración numérica (si se determina el número de
subintervalos y el reparto entre los procesos).
Otros ejemplos
Laboratorio de Paralelismo
IF - EHU
4
92
Esquemas de algoritmos paralelos
 Algoritmos relajados o paralelismo “obvio”
Procesado de imagen
> desplazamiento:
> escalado:
> rotación:
(x, y) → (x+Δx, y+Δy)
(x, y) → (x*Sx, y*Sy)
x → x cos  + y sen 
y → -x sen  + y cos 
> recorte (clipping): borrar fuera de un área
Reparto de tareas: por filas, columnas, bloques...
Laboratorio de Paralelismo
IF - EHU
4
93
Esquemas de algoritmos paralelos
 Algoritmos relajados o paralelismo “obvio”
Cálculo de funciones tipo “Mandelbrot”
>
Iteración de una función con los puntos de una
determinada área hasta que se cumpla cierta
condición.
Por ejemplo: Zk+1 = Zk2 + C
(complejos)
hasta que |Zk| > 2
Reparto de puntos independientes; la asignación de
tareas podría ser dinámica.
Laboratorio de Paralelismo
IF - EHU
4
94
4
Esquemas de algoritmos paralelos
 Algoritmos relajados o paralelismo “obvio”
Procesos tipo “Montecarlo” (aleatoriedad)
Selección aleatoria de puntos para procesar una
determinada función.
Por ejemplo, cálculo de pi como
la relación de áreas entre un
cuadrado y un círculo.
x
x
x
x
x
x
Problemas con la generación de números aleatorios.
Laboratorio de Paralelismo
IF - EHU
95
Esquemas de algoritmos paralelos
 Computación pipeline o segmentada
El problema se divide en una serie de etapas.
Cada etapa se ejecuta, por ejemplo, en un
procesador, y pasa resultados a la siguiente.
f1
f2
f3
f4
Es un tipo de descomposición funcional, relacionado con
la repetición del mismo proceso sobre una serie larga de
datos (p.e., en tiempo real: procesado de vídeo).
Laboratorio de Paralelismo
IF - EHU
4
96
Esquemas de algoritmos paralelos
 Computación pipeline o segmentada
Condiciones:
-- que se ejecute más de una vez el mismo problema.
-- que se procese una serie larga de datos.
-- que se pueda pasar datos a la siguiente fase mucho
antes del final del cálculo de cada fase.
-- que el tiempo de proceso asociado a cada fase sea
similar (load balancing).
Topología ideal: cadena / anillo.
Laboratorio de Paralelismo
IF - EHU
4
97
Esquemas de algoritmos paralelos
 Computación pipeline o segmentada
Normalmente no se genera un número muy elevado
de procesos.
Algunos ejemplos:
-- procesado de señal (sonido, vídeo...)
-- simulaciones de procesos segmentados (computación)
Laboratorio de Paralelismo
IF - EHU
4
98
Esquemas de algoritmos paralelos
4
 Paralelismo síncrono
Es el caso más habitual. Dos tipos:
-- paralelismo de datos
-- procesos iterativos
Hay que sincronizar los procesos, bien al final de una
operación o bien al final de una iteración.
Lo más habitual es que la sincronización sea global (p.e.,
al final de cada iteración, para decidir si seguir o parar).
La implementación de la barrera debe ser eficiente.
Laboratorio de Paralelismo
IF - EHU
99
Esquemas de algoritmos paralelos
 Paralelismo síncrono
La sincronización / comunicación entre procesos
añade problemas:
-- carga añadida al tiempo de cálculo
→ reducción del speed-up.
-- posibles problemas con el reparto equilibrado
de tareas (load balancing).
-- posibles deadlocks.
Laboratorio de Paralelismo
IF - EHU
4
100
Esquemas de algoritmos paralelos
 Paralelismo síncrono
Como siempre, hay que intentar reducir las
necesidades de comunicación.
Un ejemplo: una determinada aplicación procesa una
matriz de N×N elementos entre P procesadores. Durante
la ejecución, los procesos necesitan intercambiarse los
datos de “la frontera”.
¿Cuál es el reparto más adecuado de los datos de la
matriz, por filas/columnas o por bloques?
Laboratorio de Paralelismo
IF - EHU
4
101
4
Esquemas de algoritmos paralelos
 Paralelismo síncrono
N/P
N/P1/2
N/P1/2
N
Total de comunicación:
2 veces N elementos
4 veces N / P1/2 elementos
Tiempo de comunicación (send + receive):
Tcol = 4 × (ti + te × N)
Laboratorio de Paralelismo
IF - EHU
Tblo = 8 × (ti + te × N/P1/2)
102
4
Esquemas de algoritmos paralelos
 Paralelismo síncrono
Tcol > Tblo
ti grande,
mejor por
columnas
→
ti / te < N × (1 - 2/P1/2)
150
N = 128
100
ti / te
N = 64
ti pequeño,
mejor por
bloques
50
N = 32
0
Laboratorio de Paralelismo
IF - EHU
1
10
P
100
1000
103
Esquemas de algoritmos paralelos
 Paralelismo síncrono
Otros ejemplos:
-- Resolución de un sistema de ecuaciones por el
método iterativo de Jacobi (ejemplo 2).
-- Difusión de calor en un determinado medio físico.
-- Autómatas celulares.
-- Multiplicación de matrices por el método Cannon.
-- Resolución de sistemas de ecuaciones lineales por
métodos iterativos.
-- El juego de la vida (problemas de simulación).
Laboratorio de Paralelismo
IF - EHU
4
104
4
Esquemas de algoritmos paralelos
 Paralelismo síncrono
-- Resolución de un sistema de ecuaciones por el
método iterativo de Jacobi
> Diferencias finitas: Jacobi
fácil de paralelizar
X
( t 1)
i, j

4 X i(,tj)  X i(t1), j  X i(t1), j  X i(,tj)1  X i(,tj)1
Laboratorio de Paralelismo
IF - EHU
8
Gauss-Seidel: más
eficiente, más complejo
X
(t 1)
i, j

4 X i(,tj)  X i(t1,1j)  X i(t1), j  X i(,tj11)  X i(,tj)1
8
“Red/black”
una alternativa
105
Esquemas de algoritmos paralelos
4
 Paradigma maestro-esclavo
Thread/proceso maestro que se encarga de poner en
marcha los esclavos dándoles trabajo y recopilando las
soluciones que van calculando.
 Granja de procesos
Conjunto de procesos que trabaja de manera conjunta pero
independiente en la resolución de un problema (similar al de
los algoritmos relajados). Similar a maestro-esclavo, pero los
procesos hacen un trabajo idéntico.
 Trabajadores replicados
Los workers son capaces de generar nuevas tareas que
pueden ejecutarlas ellos mismos y otros workers. Es una
versión descentralizada (control de finalización!).
Laboratorio de Paralelismo
IF - EHU
106
Índice
1. Introducción.
2. Análisis de algoritmos.
3. Metodología de desarrollo de programas
paralelos.
4. Esquemas de algoritmos paralelos.
5. Problemas numéricos. Librerías.
Laboratorio de Paralelismo
IF - EHU
Problemas numéricos. Librerías
 La computación paralela está ligada al desarrollo e
implementación de algoritmos numéricos,
principalmente los matriciales.
Por ello, el estudio de la implementación paralela de
algoritmos numéricos paralelos y de las librerías
numéricas matriciales paralelas es necesario para el
aprendizaje de la programación paralela.
Laboratorio de Paralelismo
IF - EHU
4
108
Problemas numéricos. Librerías
4
 Las primeras aplicaciones de la computación paralela
fueron la aceleración de todo tipo de algoritmos
numéricos, especialmente los matriciales.
La regularidad de las estructuras matriciales las
hace especialmente adecuadas para su procesamiento
paralelo.
Los problemas que se tratan suelen ser de gran
dimensión o problemas cuya respuesta debe
obtenerse en tiempo real.
Laboratorio de Paralelismo
IF - EHU
109
Problemas numéricos. Librerías
 Se han desarrollado numerosas librerías orientadas a
conseguir altas prestaciones (speed-up, eficiencia,
escalabilidad…).
Su legibilidad, portabilidad y eficiencia ha permitido
no tener que reescribir gran cantidad de código.
Sin embargo, desarrollar algoritmos matriciales
paralelos eficientes y precisos no suele ser una tarea
trivial (p.e., eficiencia versus estabilidad numérica).
Laboratorio de Paralelismo
IF - EHU
4
110
Problemas numéricos. Librerías
 Dos problemas tipo (muchos de los problemas se
reducen a éstos):
- Resolución de sistemas de ecuaciones lineales
Ax = b
- Cálculo de valores y vectores propios
Ax = λx
Laboratorio de Paralelismo
IF - EHU
4
111
Problemas numéricos. Librerías
4
 A su vez, estos problemas suelen utilizar en sus
cálculos productos escalares de vectores, productos
matriz-matriz, producto vector-matriz, etc.
Por ello se puede abordar el análisis computacional
con una visión de niveles, diseñando rutinas sencillas
pero eficientes que resuelvan estos cálculos
matriciales (nivel de núcleo) para utilizarlas en un
nivel más alto (nivel de librería).
Laboratorio de Paralelismo
IF - EHU
112
Problemas numéricos. Librerías
4
 Los problemas matriciales que se suelen resolver
mediante técnicas paralelas, normalmente, tienen una
característica clave para poderlos afrontar de una
manera eficiente:
Matrices de gran tamaño y con algún tipo
de estructura.

El tamaño de las matrices (104x104, 105x105) plantea
problemas en cuanto al coste de computación –suelen
ser algoritmos de O(n3)–, y en cuanto a la cantidad de
memoria necesaria –normalmente datos de doble
precisión, una matriz de 105x105 son 74 GB–.
Laboratorio de Paralelismo
IF - EHU
113
Problemas numéricos. Librerías
 En cuanto a la estructura, se pueden clasificar en:
- Matrices densas
con un patrón aleatorio en cuanto a valores y
posiciones en la matriz
- Matrices dispersas
con un número elevado de elementos con valor
cero
- Matrices estructuradas
la posición de los elementos no nulos de la matriz
sigue un patrón concreto
Laboratorio de Paralelismo
IF - EHU
4
114
Problemas numéricos. Librerías
 En cuanto a la estructura, se pueden clasificar en:
- Matrices estructuradas
Algunos ejemplos: matriz banda
A : Ai, j   0 si i  j  f  si j  i  c
c
f
0’s
0’s
Laboratorio de Paralelismo
IF - EHU
4
115
4
Problemas numéricos. Librerías
 En cuanto a la estructura, se pueden clasificar en:
- Matrices estructuradas
Otros ejemplos:
Matriz de tipo Toeplitz
T i, j   T  f , g  si i  j  f  g
3
8
6
9
Laboratorio de Paralelismo
IF - EHU
4
3
8
6
5
4
3
8
1
5
4
3
Matriz de tipo Hankel
H i, j   H  f , g  si i  j  f  g
3
4
5
1
4
5
1
2
5
1
2
7
1
2
7
8
116
Problemas numéricos. Librerías
4
 Núcleos computacionales y librerías
Los núcleos computacionales son un conjunto de
funciones o subprogramas que resuelven operaciones
vectoriales y/o matriciales sencillas: producto escalar,
suma vectores, producto matriz-vector…
Las librerías están constituidas por un conjunto de
rutinas que resuelven problemas de más alto nivel
utilizando los núcleos computacionales.
Laboratorio de Paralelismo
IF - EHU
117
Problemas numéricos. Librerías
4
 Núcleos computacionales: BLAS
Basic Linear Algebra Subprograms
http://www.netlib.org/blas/
BLAS 1 (1973)
Programada en Fortran77, sólo cubría operaciones
elementales de complejidad O(n), p.e.: producto escalar de
vectores, suma de vectores con escalado: y = ax + y
En la optimización de código para arquitecturas vectoriales
BLAS 1 puede ser un problema ya que oculta al compilador
la naturaleza de las operaciones matriz-vector impidiendo
su optimización.
Laboratorio de Paralelismo
IF - EHU
118
Problemas numéricos. Librerías
4
119
 Núcleos computacionales: BLAS
BLAS 2
Cubre un conjunto de operaciones sencillas de tipo matrizvector. Son operaciones de O(n2) del estilo:
y = aAx + by (A matriz, x e y vectores, a escalar)
A = axyT + A, × = A-1x (con A triangular superior)
Laboratorio de Paralelismo
IF - EHU
Problemas numéricos. Librerías
4
120
 Núcleos computacionales: BLAS
BLAS 3
Para computadores con jerarquía de memoria, la
descomposición por bloques manteniendo el cálculo matricial
es mejor que la descomposición matriz-vector, ya que se
consigue una mayor reutilización de los datos en la memoria
cache (o memoria local).
BLAS 3 cubre estas necesidades implementando operaciones
tales como:
C = aAB + bC, C = aAAT + bC, B = aT-1B (con T
triangular)
Laboratorio de Paralelismo
IF - EHU
Problemas numéricos. Librerías
 Librería LAPACK
http://www.netlib.org/lapack/
Escrita inicialmente en Fortran77; también puede
invocarse desde C.
Surge como una fusión mejorada de las librerías
LINPACK (resolución de ecuaciones lineales) y
EISPACK (cálculo de valores propios).
Laboratorio de Paralelismo
IF - EHU
4
121
Problemas numéricos. Librerías
4
 Librería LAPACK
Está compuesta de subrutinas para resolver sistemas
de ecuaciones lineales, problemas de mínimos
cuadrados lineales, y problemas de valores
propios y valores singulares.
También contiene las descomposiciones que
permiten resolver los problemas anteriores: LU,
Cholesky, QR, SVD,…).
Laboratorio de Paralelismo
IF - EHU
122
Problemas numéricos. Librerías
4
 Librería LAPACK
Utiliza sobre todo el núcleo BLAS 3. De este modo los
fabricantes pueden proporcionar versiones nativas de
BLAS y conseguir muy buenas prestaciones para
LAPACK.
Sirve para matrices densas y banda, pero no para
dispersas. Para datos reales y complejos de simple y
doble precisión.
Laboratorio de Paralelismo
IF - EHU
123
Problemas numéricos. Librerías
4
 Librería LAPACK
Contiene tres tipos de rutinas:
> Rutinas driver: resuelven un problema completo
(cálculo de valores propios de una matriz simétrica,
resolución de un sistema de ecuaciones lineales…).
> Rutinas computacionales: resuelven cálculos como
las factorizaciones matriciales (descomposición QR,
descomposición LDLT…), reducción de una matriz a la
forma diagonal, etc.
Laboratorio de Paralelismo
IF - EHU
124
Problemas numéricos. Librerías
4
 Librería LAPACK
Contiene tres tipos de rutinas:
> Rutinas auxiliares: realizan subtareas de los
algoritmos orientados a bloques; se pueden considerar
como extensiones de BLAS.
 Documentación en working notes (buena fuente de
aprendizaje de diseño de algoritmos numéricos
matriciales eficientes.
http://www.netlib.org/lapack/lawns/downloads/
Laboratorio de Paralelismo
IF - EHU
125
Problemas numéricos. Librerías
 Librería ScaLAPACK
http://www.netlib.org/scalapack/
Es la versión para memoria distribuida de la
librería LAPACK. Aparece a finales de los 90 y
contempla redes de computadores y paralelos
heterogéneos.
Resuelve problemas de álgebra lineal numérica:
sistemas de ecuaciones lineales, problemas de
mínimos cuadrados y problemas de valores propios.
Laboratorio de Paralelismo
IF - EHU
4
126
Problemas numéricos. Librerías
 Librería ScaLAPACK
Portable a cualquier computador en el que esté
instalado MPI, y está escrito siguiendo el modelo
SPMD.
Trabaja con matrices que están distribuidas por los
procesadores mediante una distribución cíclica por
bloques, y sirve para matrices densas y banda, no
para dispersas.
Los tipos de datos que contempla son reales y
complejos de simple y doble precisión.
Laboratorio de Paralelismo
IF - EHU
4
127
Problemas numéricos. Librerías
4
128
 Librería ScaLAPACK
Se basa en el núcleo PBLAS (Parallel Basic Linear
Algebra Subroutines), que es una extensión de BLAS
para el modelo de paso de mensajes. Al igual que BLAS,
está organizada por niveles (PBLAS 1, PBLAS 2 y PBLAS
3).
Para el diseño de PBLAS se diseñó otro paquete núcleo
computacional especializado en las comunicaciones
denominado BLACS (Basic Linear Algebra
Communications Subroutines), que a su vez utiliza MPI.
Laboratorio de Paralelismo
IF - EHU
4
Problemas numéricos. Librerías
 Librería ScaLAPACK
ScaLAPACK
PBLAS
LAPACK
BLAS
BLACS
Global
Local
Primitivas de paso de mensajes
(MPI, PVM…)
http://www.netlib.org/
Laboratorio de Paralelismo
IF - EHU
129
Referencias
Programación Paralela
• F. Almeida et al: Introducción a la programación paralela.
Paraninfo, 2008.
• I. Foster: Designing and Building Parallel Programs.
Addison Wesley (version on-line).
• B. Wilkinson, M. Allen: Parallel Programming Techniques and
Applications… Pearson, 2005 (2. ed.).
• M.J. Quinn: Parallel Programming in C with MPI and OpenMP.
McGraw Hill, 2003.
• A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to
Parallel Computing (2. ed.). Pearson, 2003.
Laboratorio de Paralelismo
IF - EHU

similar documents