sitemas paralelos clase 3

Vista previa del material en texto

Sistemas Paralelos 
Clase 8 
Facultad de Informática 
UNLP 
Modelos de Programación 
Paralela 
Modelos de computación paralela 
Modelo = representación física, matemática o lógica de una entidad 
real. 
Los modelos permiten simular fenómenos y pueden usarse para 
describir sistemas conceptuales 
En la Ciencia de la Computación pueden modelizarse entidades 
reales como por ejemplo computadoras, capturando características 
esenciales e ignorando detalles. 
Estos modelos sirven como herramienta para pensar y estudiar 
problemas, obtener ideas sobre distintas estructuras y expresar 
algoritmos como solución a esos problemas. 
12-05-2015 Clase 8 3 
Modelos de computación paralela 
Numerosos modelos en la CC: autómatas, máquinas de Turing, 
gramáticas formales, máquinas de acceso aleatorio (RAM), PRAM, 
LogP, BSP, ... 
La computación uniprocesador se benefició fuertemente con la 
existencia de un modelo teórico simple como RAM. 
Permitió desarrollar algoritmos uniprocesador y establecer correctitud 
y performance esperada en forma relativamente independiente de la 
máquina específica. 
Las optimizaciones a características de la máquina las realiza el 
compilador. 
Simplicidad de RAM + compiladores sofisticados → computación 
uniprocesador eficiente. 
12-05-2015 Clase 8 4 
Modelos de computación paralela 
¿Qué objetivos debiera tener un modelo para máquinas paralelas? 
 Ser simple de entender y fácil de usar. 
 Los algoritmos correctos en el modelo deben serlo en la arquitectura de 
destino. 
 Ser cercano a las arquitecturas reales para reducir el gap. 
 La performance real debe corresponderse con la predicha. 
 
 Gran cantidad de modelos paralelos pero ninguno tan sencillo 
como RAM, ni utilizable para todas las máquinas debido a la 
diversidad de éstas. 
 
12-05-2015 Clase 8 5 
Comentarios 
Cada modelo intenta brindar una abstracción para desarrollar 
algoritmos para una clase de máquinas paralelas. 
Esta simplificación se obtiene a expensas de introducir 
“imprecisiones”. 
La cantidad de modelos muestra que no existe consenso: cada uno 
pone énfasis en determinadas características en detrimento de otras. 
Un modelo unificado debería incluir características que representen 
los objetivos de programadores, diseñadores y constructores de 
computadoras. 
12-05-2015 Clase 8 6 
Paradigmas Paralelos 
Paradigmas de Programación Paralela 
Paradigma de programación: clase de algoritmos que 
resuelve distintos problemas, pero tienen la misma estructura de 
control. 
Para cada paradigma puede escribirse un esqueleto 
algorítmico que define la estructura de control común. 
Dentro de la programación paralela pueden encontrarse 
paradigmas que permiten encuadrar los problemas en alguno de 
ellos. 
En cada paradigma, los patrones de comunicación son muy 
similares en todos los casos. 
12-05-2015 Clase 8 8 
Master/slave o master/worker 
Basado en organizaciones del mundo real. 
El master envía iterativamente datos a los workers y recibe resultados de 
éstos. 
Posible “cuello de botella” (por ejemplo, por tareas muy chicas o slaves muy 
rápidos) → elección del grano adecuado. 
Dos casos de acuerdo a las dependencias de las iteraciones: 
 Iteraciones dependientes: el master necesita los resultados de todos los workers 
para generar un nuevo conjunto de datos. 
 Entradas de datos independientes: los datos llegan al maestro, que no necesita 
resultados anteriores para generar un nuevo conjunto de datos 
 
12-05-2015 
Maestro 
Esclavo Esclavo Esclavo 
Clase 8 9 
Master/slave o master/worker 
Dos opciones para la distribución de los datos: 
 Distribuir todos los disponibles, de acuerdo a alguna política (estático). 
 Bajo petición o demanda (dinámico). 
Existen variantes, pero básicamente un procesador es responsable de la 
coordinación y los otros de resolver los problemas asignados. 
Es una variación de SPMD donde hay dos programas en lugar de sólo uno. 
Casos: 
 Procesadores heterogéneos y con distintas velocidades → problemas con el 
balance de carga. 
 Trabajo que debe realizarse en “fases” → sincronización. 
 Generalización a modelo multi-nivel o jerárquico. 
12-05-2015 Clase 8 10 
Pipeline y Algoritmos Sistólicos 
El problema se particiona en una secuencia de pasos. El stream de 
datos pasa entre los procesos, y cada uno realiza una tarea sobre él. 
Ejemplo: filtrado, etiquetado y análisis de escena en imágenes. 
Mapeo natural a un arreglo lineal de procesadores. 
12-05-2015 
Etapa 1 Etapa 2 Etapa 3 
Pipe 
Clase 8 11 
Pipeline y Algoritmos Sistólicos 
Extensiones: 
 Procesadores especializados no iguales. 
 Más de un procesador para una tarea determinada. 
 El flujo puede no ser una línea simple (ejemplo: ensamble de 
autos con varias líneas que son combinadas) → procesamiento 
sistólico. 
12-05-2015 Clase 8 12 
Dividir y Conquistar 
División repetida de problemas y datos en subproblemas más chicos 
(fase de dividir); resolución independiente de éstos (conquistar), 
con frecuencia de manera recursiva. Las soluciones son combinadas 
en la solución global (fase de combinar). 
 
La subdivisión puede corresponderse con la descomposición entre 
procesadores. Cada subproblema puede mapearse a un procesador. 
Cada proceso recibe una fracción de datos: si puede los procesa; 
sino, crea un n° de “hijos” y les distribuye los datos. 
12-05-2015 Clase 8 13 
Dividir y Conquistar 
Ejemplos: MergeSort y Quicksort. Diferencia de complejidad en las 
fases. 
12-05-2015 
Pb 
Pb1 Pb2 Pb3 
Pb11 Pb12 Pb31 Pb33 Pb32 
Divide and Conquer 
Clase 8 14 
SPMD 
 El programador genera un programa único que ejecuta cada nodo sobre una 
porción del dominio de datos. La diferente evaluación de un predicado en 
sentencias condicionales permite que cada nodo tome distintos caminos del 
programa 
 Dos fases: 1) elección de la distribución de datos y 2) generación del 
programa paralelo 
12-05-2015 
P 
P 
P 
 
 
Datos 
SPMD 
1) Determina el lugar que ocuparán los datos 
en los nodos. La carga es proporcional al 
número de datos asignado a cada nodo. 
Dificultades en computaciones irregulares y 
máquinas heterogéneas. 
2) Convierte al programa secuencial en SPMD. 
En la mayoría de los lenguajes, depende de 
la distribución de datos. 
Clase 8 15 
EJEMPLOS 
Aplicaciones para analizar su paralelización 
 Ordenación de vectores. 
 N-Reinas. 
 Filtros en imágenes. 
 Alineación de secuencias de ADN. 
 
 
 
 
12-05-2015 17 Clase 8 
Ordenación de Vectores 
Ordenación por medio de Pipeline de procesos 
 Ordenación de vectores de N elementos. 
 Pipeline de N procesos. 
 
 
 
• Problemas. 
 Pipeline de K<<N procesos. 
 
 
 
• Mejoras. 
• Problemas. 
 
12-05-2015 Clase 8 19 
P0 P1 P2 P3 P4 PN 
P0 P1 P2 PK 
Ordenación Merge Sort 
 Procesos para los (log N) niveles 
• Problemas. 
 
 
 
 
 Procesos para K< (log N) niveles 
• Mejoras. 
• ¿Ordenación en las hojas? 
• ¿Cantidad de Procesos? 
 
12-05-2015 Clase 8 20 
P0 
P0 
P2 P0 
P1 
P1 P3 
P0 
P0 
P2 P0 
P1 
P1 P3 
Ordenación por bloques 
 Pasos: 
• Dividir el vector en bloques. 
 
 
 
 
• Ordenar cada bloque por método común (ej. Bubble sort). 
• Merge de los bloques ordenados. 
 
 
12-05-2015 Clase 8 21 
P0 P1 P2 P3 
P0 
P1 
P2 
P3 
Ordenación por bloques 
Distribución estática del vector 
 Tamaño de los bloques. 
• Arquitectura homogénea. 
• Arquitectura heterogénea. 
 
 ¿Quién realiza la distribución? 
• Descentralizada. 
• Centralizada en un Coordinador. 
• Centralizada en un Worker con función de Coordinador. 
 
 ¿Balance de carga? ¿Ociosidad? 
 
12-05-2015 Clase 8 22 
Ordenación por bloques 
Distribución dinámica del vector 
 Tamaño de los bloques. 
• Arquitectura homogénea. 
• Arquitectura heterogénea. 
 
 ¿Quién realiza la distribución? Ventajasy desventajas de 
cada caso. 
• Descentralizada. 
• Centralizada en un Coordinador. 
• Centralizada en un Worker con función de Coordinador. 
 
 ¿Balance de carga? ¿Ociosidad? 
 
12-05-2015 Clase 8 23 
Ordenación por bloques 
Distribución semidinámica del vector 
 Tamaño de los bloques estáticos y dinámicos. 
• Arquitectura homogénea. 
• Arquitectura heterogénea. 
 
 ¿Quién realiza la distribución? Ventajas y desventajas de 
cada caso. 
• Descentralizada. 
• Centralizada en un Coordinador. 
• Centralizada en un Worker con función de Coordinador. 
 
 ¿Balance de carga? ¿Ociosidad? 
 
12-05-2015 Clase 8 24 
Ordenación por bloques 
Ordenación de los bloques y Merge 
 Ordenación interna dentro de cada proceso. 
• Selección del método de ordenación. 
• Selección del tamaño a ordenar. 
 Ordenar bloque completo. 
 Dividir en subbloques y luego hacer merge. 
 
 Merge de los bloques. 
• Merge multinivel. 
• Merge multibloque. 
 
12-05-2015 Clase 8 25 
N-Reinas 
Aplicación N-Reinas 
 Definición del problema. 
 
 
 
 
 
 Características del problema. 
• Trabajo no predecible. 
• Tiempo de procesamiento >> Tiempo de comunicación. 
• Orden de complejidad creciente en forma exponencial. 
12-05-2015 Clase 8 27 





Solución válida 


 

Solución inválida 
Solución secuencial 
 Solución de fuerza bruta con heurística. 
 
 
 
 
 
12-05-2015 Clase 8 28 
 main () 
{ cantSol:=0 
 for (pos= 1..N/2) 
 ubicarReina (1,pos,tablero) 
 detPosVálida (posVálida,tablero,2) 
 cantSol:=cantSol + detSol (2,posVálida,tablero) 
} 
 (a) 
 
function detSol (fila, posVálida, tablero) 
{ i:= posiciónVálida (posVálida) 
 if (fila = N) and (i < N ) then 
 ubicarReina (fila,i,tablero) 
 return (cantidadSoluciones (tablero)) 
 else 
 total:=0 
 while (i < N) 
 ubicarReina (fila,i,tablero) 
 detPosVálida (nuevaPosVálida,tablero, fila+1). 
 total:= total + detSol (fila+1,nuevaPosVáalida,tablero ) 
 i:= posiciónVálida (posVálida) 
 return total 
} 
 
detPosVálida (p,t,f): determina el conjunto p de posiciones 
válidas para la fila f en el tablero t. 
posiciónVálida (p): retorna la primer posición válida dada en p. 
 
 
 
(b) 
function cantidadSoluciones (t) 
{ if (rot(t,90)=t) or (rot(t,90)=sim(t)) then return (2) 
 else if (rot(t,180)=t) or (rot(t,180)=sim(t)) then return (4) 
 else return (8) 
} 
 
rot(t,g): retorna el tablero t rotado en g grados. 
sim(t): retorna el tablero simétrico de t. 
 
 (c) 
Solución Paralela 
División en tareas 
12-05-2015 Clase 8 29 

Tarea 1 

Tarea 2 

Tarea 3 
Pocos pasos, con mucho trabajo irregular 
DIFICIL DE 
BALANCEAR 
Reducir la granularidad 
Atención en la distribución del trabajo entre los procesadores Importante 

Tarea1 

Tarea2 

Tarea3 

Tarea4 

Tarea5 

Tarea6 

Tarea7 
Solución Paralela 
Distribución estática de las tareas 
12-05-2015 Clase 8 30 
 Estática Homogénea 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... 93 94 95 96 97 98 99 100
m1 m2 m3 m4 m5 m6 m1 m2 m3 m4 m5 m6 m1 m2 m3 m4 m5 m6 m1 m2 m3 m4 m5 m6 ... m1 m2 m3 m4 m5 m6 m1 m2
Estática Heterogénea 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... 97 98 99 100
m1 m2 m3 m4 m5 m6 m1 m2 m3 m4 m1 m2 m1 m2 m3 m4 m5 m6 m1 m2 m3 m4 m1 m2 m5 m6 m1 m2
Combinaciones RestantesBloque 1 Bloque 2
Potencias de cálculo de cada máquina: m1=m2= 3; m3=m4=2; m5=m6= 1 
Pseudocódigo de la solución paralela 
Distribución estática de las tareas 
12-05-2015 Clase 8 31 
 
function detSolParcial (posFila1, posFila2, posFila3, tablero) 
{ ubicarReina (1,posFila1,tablero) 
 ubicarReina (2,posFila2,tablero) 
 ubicarReina (3,posFila3,tablero) 
 detPosVálida (posVálida, tablero,4). 
 return detSol (4, posVálida, tablero) 
} 
 
detPosVálida (p,t,f): determina el conjunto p de posiciones 
válidas para la fila f del tablero t. 
 
 
 
(c) 
main () //procesador i con i > 1 
{ cantSol:=0 
 while (procesador i tenga combinaciones) 
 determina la ubicación en la fila 1 (p1) 
 determina la ubicación en la fila 2 (p2) 
 determina la ubicación en la fila 3 (p3) 
 cantSol:= cantSol + detSolParcial (p1,p2,p3,tablero) 
 send(cantSol,1) 
 } 
(b) 
main () //procesador 1 
{ cantSol:=0 
 while (procesador 1 tenga combinaciones) 
 determina la ubicación en la fila 1 (p1) 
 determina la ubicación en la fila 2 (p2) 
 determina la ubicación en la fila 3 (p3) 
 cantSol:= cantSol + detSolParcial (p1,p2,p3,tablero) 
 for (i=2..B) 
 recv(cantOtroProc,i) 
 cantSol:= cantSol + cantOtroProc; 
 } 
 (a) 
Solución Paralela 
Distribución semidinámica de las tareas 
12-05-2015 Clase 8 32 
Semidinámica 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ... 98 99 100
m5 m6 m3 m4 m1 m4 m4 m2
m3 - m6 - m1 - m2 - m3 - m4 - m1 - ... - m4 - m4 - m2
m2
Lista de requerimientos
m1 m2
Combinaciones Iniciales (CI)
m3 m4
Combinaciones Restantes (CR)
m3 m6 m1
 main () // procesador i con i > 0 
{ cantSol:=0 
 recv(pri,ult,0) 
 while (pri<>end) 
 for (combinación= pri..ult) 
 determina la ubicación en la fila 1 (combinación, p1) 
 determina la ubicación en la fila 2 (combinación, p2) 
 determina la ubicación en la fila 3 (combinación, p3) 
 cantSol:=cantSol + detSolParcial (p1,p2,p3, tablero) 
 send(pedido,i,0) 
 recv(pri,ult, 0) 
 send(cantSol,0) 
} 
main () //procesador 0 
{ cantSol:= 0 
 for (i=1..B) 
 determina la primer combinación (pri) 
 determina la última combinación (ult) 
send (pri,ult,i) 
 while (haya combinaciones) 
 recv(pedido,i) 
 determina la primer combinación (pri) 
 determina la última combinación (ult) 
send (pri,ult,i) 
 for (i=1..B) 
 send (fin,fin,i) 
recv (cantOtroProc,i) 
 cantSol:= cantSol + cantOtroProc; 
} 
 
Filtros en Imágenes 
Definición del problema 
 Filtro de imágenes en el dominio espacial. 
 Crear una nueva imagen donde cada pixel toma un valor que 
depende del elemento en esa posición y de sus vecinos 
(máscara) en un radio r. 
• Valores originales. 
• Valores actualizados. 
 Ejemplo: suavizado de la imagen. 
12-05-2015 Clase 8 34 
División del trabajo 
 La imagen debe ser dividida y distribuida entre los procesos. 
Solapamiento entre porciones de los diferentes procesos: 
• Por grupos de filas. 
• Por grupos de columnas. 
• Por bloques o subimágenes. 
 Diferencias entre cada división 
12-05-2015 Clase 8 35 
División de la imagen en bloques 
12-05-2015 Clase 8 36 
Máscara 
División y distribución de la imagen 
 Elección de la división: 
• Relación con la arquitectura. 
• Relación con el tamaño de la imagen. 
• Relación con el tamaño de la máscara. 
• Relación con la cantidad de procesos. 
 ¿Distribución dinámica o estática? 
 
12-05-2015 Clase 8 37 
Algoritmo de alineación 
local de ADN 
Algoritmo de alineación local 
 Permite encontrar el grado de similitud entre 2 secuencias 
de ADN. 
 
 Alineación local. 
 
 Algoritmo Smith and Waterman. 
 
 Característica del algoritmo: 
• Dependencia de datos. 
• Etapa posiblemente paralelizable. 
• Etapa secuencial. 
 
 Forma de paralelizar (homogéneo o heterogéneo). 
 
 
 
12-05-2015 Clase 8 39