introducción a la programación paralelawebserver.dmt.upm.es/zope/dmt/members/hermanns/... ·...

Introduccion a laProgramacion

Paralela

Miguel Hermanns

Introduccion ymotivacion

Clasificacion logicadel paralelismo

Clasificacion fısicade ordenadores

Paradigmas deprogramacion

Conceptos yterminologıa

Lımites a laparalelizacion

Diseno deprogramasparalelos

Ejemplos deparalelizacion

Resumen

Introduccion a la Programacion Paralela

Miguel Hermanns

Universidad Politecnica de Madrid, Espana

19 de abril de 2007


Paralela

Miguel Hermanns









Resumen

Estructura de la clase

1 Motivacion de la programacion paralela

2 Clasificacion logica del paralelismo

3 Clasificacion fısica de ordenadores paralelos

4 Paradigmas de programacion paralela

5 Conceptos generales y terminologıa habitual

6 Diseno de programas paralelos

7 Ejemplos de paralelizacion


Paralela

Miguel Hermanns









Resumen

¿Que es el calculo en paralelo?

Tradicionalmente los programas se han desarrollado para elcalculo en serie:

Funcionan en un ordenador con una unica CPU

Un problema es dividido en un conjunto de instrucciones

Las instrucciones son ejecutas secuencialmente

Unicamente una instruccion es ejecutada cada vez

CPU

InstruccionesProblema

iN i3 i2 i1


Paralela

Miguel Hermanns









Resumen


El calculo en paralelo consiste en usar multiples recursossimultaneamente para resolver un problema dado:

Hace uso de un ordenador con varias CPUs

El problema es dividido en partes independientes

Cada parte es dividida en un conjunto de instrucciones

Las instrucciones son ejecutas secuencialmente

Las partes son resueltas simultaneamente

El calculo en paralelo es la evolucion naturaldel calculo en serie


Paralela

Miguel Hermanns









Resumen


El calculo en paralelo consiste en usar multiples recursossimultaneamente para resolver un problema dado:

CPU

CPU

CPU

CPU

Problema Instrucciones

iN i3 i2 i1


Paralela

Miguel Hermanns









Resumen

¿Por que hacer calculo en paralelo?

Los motivos clasicos mas importantes son:

Resultados en menos tiempo (wall clock time)

Resolucion de problemas mas grandes y complejos

Realizacion de barridos parametricos

Estudio de variaciones de un mismo problema

El motivo actual mas importante es:

Los procesadores actuales son paralelos: n-core

El paralelismo es el futuro de la computacion


Paralela

Miguel Hermanns









Resumen

¿Por que hacer calculo en paralelo?

Evolucion de los ordenadores mas rapidos del Mundo:

www.top500.org


Paralela

Miguel Hermanns









Resumen

¿Donde se realiza el calculo en paralelo?


Paralela

Miguel Hermanns









Resumen

¿Quien programa en paralelo?


Paralela

Miguel Hermanns









Resumen

La arquitectura de von NeumannTodos los ordenadores siguen el mismo patron:

La memoria almacena el programa y los datos

El programa son de instrucciones a seguir por la CPU

Los datos son informacion a utilizar por el programa

Memoria

CPU

Cargar Guardar

Almacenar

Procesar

La CPU carga los datos, los procesa segun el programay luego los guarda otra vez en memoria


Paralela

Miguel Hermanns









Resumen

Taxonomıa de Flynn

Es la clasificacion mas extendida del paralelismo:

Distingue entre instrucciones y datos

Estos pueden ser simples o multiples

Datos

Simples Multiples

Inst

rucc

iones

Multip

les

Sim

ple

s

SISD SIMD

MISD MIMD


Paralela

Miguel Hermanns









Resumen

SISD: Single Instruction, Single Data

Caracterısticas del modelo SISD:

La CPU procesa unicamente unainstruccion por cada ciclo de reloj

Unicamente un dato es procesadoen cada ciclo de reloj

Es el modelo mas antiguo deordenador y el mas extendido

Ejemplo: la mayorıa de los PCs,servidores y estaciones de trabajo

...

Carga A

Carga B

C = A + B

Guarda C

...

tiempo


Paralela

Miguel Hermanns









Resumen

SISD: Single Instruction, Single Data

Analogıa con una imprenta:

El acto de imprimir son las instrucciones del programa

La plantilla y el papel son los datos del programa

Cuanto mas rapida la imprenta, mas trabajo se realiza


Paralela

Miguel Hermanns









Resumen

SIMD: Single Instruction, Multiple Data

Caracterısticas del modelo SIMD:

Todas las unidades ejecutan la misma instruccion

Cada unidad procesa un dato distinto

Todas las unidades operan simultaneamente

...

Carga A(1)

Carga B(1)

C(1) = A(1) + B(1)

Guarda C(1)

...

Unidad 1

...

Carga A(2)

Carga B(2)

C(2) = A(2) + B(2)

Guarda C(2)

...

Unidad 2

...

...

Carga A(n)

Carga B(n)

C(n) = A(n) + B(n)

Guarda C(n)

...

Unidad n

tiempo


Paralela

Miguel Hermanns









Resumen


Dos maneras de obtener SIMD:

Matrices de procesadores:

Instruccion CPU CPU CPU CPU

A(1) A(2) A(3) A(4)

Procesadores vectoriales:

Instruccion CPU

A(1:4)


Paralela

Miguel Hermanns









Resumen





La matriz de imprentas serıa:

Cuantas mas imprentas simultaneas,mas trabajo se realiza


Paralela

Miguel Hermanns









Resumen





La imprenta vectorial serıa:

Cuanto mas vectorial sea la imprenta,mas trabajo se realiza


Paralela

Miguel Hermanns









Resumen

MISD: Multiple Instruction, Single Data

Caracterısticas del modelo MISD:

Cada unidad ejecuta una instruccion distinta

Cada unidad procesa el mismo dato

Aplicacion muy limitada en la vida real

...

Carga A

C(1) = A * 1

Guarda C(1)

...

Unidad 1

...

Carga A

C(2) = A * 2

Guarda C(2)

...

Unidad 2

...

...

Carga A

C(n) = A * n

Guarda C(n)

...

Unidad n

tiempo


Paralela

Miguel Hermanns









Resumen

MIMD: Multiple Instruction, Multiple Data

Caracterısticas del modelo MIMD:

Cada unidad ejecuta una instruccion distinta

Cada unidad procesa un dato distinto

Todas las unidades operan simultaneamente

...

Carga A

C = A * A

Guarda C

...

Unidad 1

...

Carga B

Llama F(B)

D = B + 1

...

Unidad 2

...

...

Carga E

G = E

E = 2

...

Unidad n

tiempo


Paralela

Miguel Hermanns









Resumen

MIMD: Multiple Instruction, Multiple Data

Analogıa con un simulador de vuelo:

Panel demandos

Integrador de lasecuaciones de vuelo

Visualizadorδv , δh, . . . x , y , z, . . .


Paralela

Miguel Hermanns









Resumen

Clasificacion de los ordenadores paralelos

Los ordenadores pueden clasificarse atendiendo a:

El tipo de procesador que utilizan

La manera de distribuir la memoria

La arquitectura del ordenador

Lo mas habitual es segun la distribucion de memoria:

Ordenadores de memoria compartida

Ordenadores de memoria distribuida

Ordenadores hıbridos


Paralela

Miguel Hermanns









Resumen


Caracterısticas principales:

Todas las CPUs acceden a la misma memoria

Cambios en la memoria son visibles por todas las CPUs

Hay principalmente dos tipos: UMA y NUMA

MemoriaCPU CPU

CPU

CPU


Paralela

Miguel Hermanns









Resumen


“Uniform Memory Access” (UMA):

Todas las CPUs estan igual de lejos de la memoria

Maquinas SMP (“Symmetric Multiprocessor”)

Ejemplo tıpico actual: procesadores Intel Xeon

Placa base Supermicro X7DB3


Paralela

Miguel Hermanns









Resumen


“Non-Uniform Memory Access” (NUMA):

Las CPUs no estan todas igual de lejos de la memoria

A menudo son maquinas SMP interconectadas

Ejemplo tıpico actual: procesadores AMD Opteron

Placa base Supermicro H8DA8


Paralela

Miguel Hermanns









Resumen


IBM System p5:

Arquitectura NUMA

64 CPUs con acceso a la misma memoria

2000 GB de memoria


Paralela

Miguel Hermanns









Resumen


Ventajas:

Conceptualmente faciles de programar

Compartir datos entre threads es muy facil y rapido

Desventajas:

La escalabilidad entre CPUs y memoria es mala

El programador es responsable de la sincronıa

Es muy costoso hacer ordenadores con muchas CPUs


Paralela

Miguel Hermanns









Resumen



Cada CPU tiene su propia memoria local

La memoria local de una CPU no es visible por lasdemas CPUs

Informacion es compartida entre CPUs por una red

Red

Memoria CPU

Memoria CPU

MemoriaCPU

MemoriaCPU


Paralela

Miguel Hermanns









Resumen


Cluster de ordenadores:

Se compone de equipos informaticos estandar

Red de bajo o alto rendimiento

Coste bajo para la potencia que se consigue


Paralela

Miguel Hermanns









Resumen


Ventajas:

La escalabilidad entre CPUs y memoria es muy buena

Acceso rapido y en exclusiva a la memoria

El coste es “lineal” con el numero de CPUs

Desventajas:

El programador es responsable de las comunicaciones

La conversion de programas seriales puede no ser trivial

La red de comunicaciones suele ser el cuello de botella


Paralela

Miguel Hermanns









Resumen



Grupos de CPUs comparten una misma memoria

Los grupos de CPUs se comunican por una red

Suelen ser maquinas SMP interconectadas entre sı

Red

MemoriaCPU

CPU

CPU

CPU

MemoriaCPU

CPU

CPU

CPU

MemoriaCPU

CPU

CPU

CPU

MemoriaCPU

CPU

CPU

CPU


Paralela

Miguel Hermanns









Resumen


NEC Earth Simulator (Japon):

640 nodos SMP con 8 CPUs por nodo

16GB de memoria por nodo

Total: 5120 CPUs y 10240 GB de memoria


Paralela

Miguel Hermanns









Resumen


Mare Nostrum (Espana):

5120 nodos SMP con 2 CPUs por nodo

4GB de memoria por nodo

Total: 10240 CPUs y 20480 GB de memoria


Paralela

Miguel Hermanns









Resumen


Ventajas:

La escalabilidad entre CPUs y memoria es razonable

El coste es “lineal” con el numero de grupos de CPUs

La red de comunicaciones es menos crıtica

Desventajas:

El programador es responsable de las comunicaciones

El programador es responsable de la sincronıa

La conversion de programas seriales puede no ser trivial


Paralela

Miguel Hermanns









Resumen

Evolucion historica


Paralela

Miguel Hermanns









Resumen

Paradigmas de programacion paralela

Existen varias formas de programar en paralelo:

Paso de mensajes

Memoria compartida

Tareas

Paralelismo de datos

Operaciones remotas en memoria

Modelos combinados

Todas estas formas:

NO son excluyentes entre sı

NO tienen nada que ver con el ordenador


Paralela

Miguel Hermanns









Resumen

Modelo de paso de mensajes

Caracterısticas del paradigma de programacion:

Un conjunto de procesos que disponen de memoria local

Los procesos intercambian datos mediante mensajes

El emisor y receptor del mensaje tienen que colaborar

Proceso 1 Proceso 2

Datos Datos

Enviar(Datos) Recibir(Datos)

El programador es responsable del envıo y la recepcion demensajes, que tıpicamente se hacen mediante llamadas a unalibrerıa


Paralela

Miguel Hermanns









Resumen

Modelo de paso de mensajesLa librerıa Message Passing Interface (MPI):

Su funcionalidad es definida por el MPI Forum

En 1994 se publico la version 1

En 1996 se publico la version 2

Es hoy por hoy la librerıa estandar

Todas las plataformas paralelas la tienen

www.mpi-forum.org


Paralela

Miguel Hermanns









Resumen

Modelo de paso de mensajes

Ejemplo de programa con paso de mensajes:

ID = Qu i en soy yo

S i soy ID = 1 entonce senv i o Datos a 2 y e sp e r o c on f i rmac i o n

S i soy ID = 2 entonce sr e c i b o Datos de 1 y env i o c on f i rmac i o n

Proceso 1 Proceso 2

Datos Datos

Enviar(Datos) Recibir(Datos)


Paralela

Miguel Hermanns









Resumen

Modelo de tareasCaracterısticas del paradigma de programacion:

Un programa serial define un conjunto de tareas

Cada tarea dispone de su memoria local

Cada tarea tiene acceso a una memoria conjunta

Las tareas son realizadas simultaneamente

Programa

Tarea 1 Tarea 2Tarea 3 Tarea 4

Sincronizacion

El programador es responsable de la sincronizacion


Paralela

Miguel Hermanns









Resumen

Modelo de tareas

El estandar OpenMP:

Lo define el OpenMP Architecture Review Board

En 1997 se publico la version 1.0



Lo incorporan la mayorıa de compiladores actuales

www.openmp.org


Paralela

Miguel Hermanns









Resumen

Modelo de tareasEjemplo de programa con tareas:

Hacer en p a r a l e l o e l bu c l e con i = 1 has ta 25La t a r e a 1 es i = 1 has ta 5La t a r e a 2 es i = 6 has ta 13La t a r e a 3 es i = 14 has ta 18La t a r e a 4 es i = 19 has ta 25

Haced l a s t a r e a s y os e s p e r o

Programa

Tarea 1 Tarea 2Tarea 3 Tarea 4

Sincronizacion


Paralela

Miguel Hermanns









Resumen

Conceptos generales y terminologıa habitual

Ejecucion serial: las tareas/instrucciones de unprograma son ejecutadas de manera secuencial, unacada vez

Ejecucion paralela: varias tareas/instrucciones de unprograma son ejecutadas de manera simultanea

Memoria compartida: las diferentes unidades decalculo (CPU) comparten una memoria comun a la cualtienen todos acceso en igualdad de condiciones

Memoria distribuida: las diferentes unidades decalculo (CPU) tienen una memoria propia a la cual lasdemas CPUs no tienen acceso directo


Paralela

Miguel Hermanns









Resumen


Speedup: la aceleracion experimentada por unprograma al hacer uso de N unidades de calculo (CPU)en vez de una unica:

Speedup =tserie

tparalelo

Eficiencia paralela: es la aceleracion alcanzada por unprograma comparada con la que podrıa alcanzar en elcaso ideal:

Eficiencia paralela =Speedup

N

Escalabilidad: evolucion del speedup de un programacon el numero de unidades de calculo (CPU)


Paralela

Miguel Hermanns









Resumen


speedup superlineal: habilidad de un programa detener una eficiencia paralela mayor que la unidad:

Wall clock time: tiempo fısico t requerido por unprograma para completar su ejecucion

Tiempo de CPU: tiempo logico t × N requerido porun programa para completar su ejecucion


Paralela

Miguel Hermanns









Resumen


Proceso: copia de un programa que se comunica conotros procesos/copias mediante pasos de mensajes

Tarea: parte de un programa que se comunica con otraspartes/tareas a traves de una memoria compartida

Sincronizacion: accion de poner en sincronıa a dos omas tareas/procesos ejecutadas en paralelo

Thread safe: una librerıa es thread safe cuando escapaz de ser utilizada de manera simultanea eindependiente por varias tareas ejecutadas en paralelo


Paralela

Miguel Hermanns









Resumen


Parallel overhead: sobrecoste debido a la ejecucionparalela de un programa, en especial la creacion ydestruccion de tareas

Procesamiento paralelo masivo: uso de un elevadonumero de procesadores para la resolucion de unproblema, hoy en dıa mas de 1000

Embarazosamente paralelo: programa/problema queno requiere de comunicaciones ni sincronismo para suejecucion/resolucion:


Paralela

Miguel Hermanns









Resumen


Comunicaciones: accion de enviar de datos oinstrucciones entre procesos pertenecientes a un mismoprograma

Latencia: el tiempo requerido por la red decomunicaciones en inicializar el envıo de datos

Ancho de banda: cantidad de datos que se puedenenviar en un segundo a traves de la red decomunicaciones


Paralela

Miguel Hermanns









Resumen


Granularidad: medida cualitativa del cociente entre entiempo dedicado a la computacion y el tiempo dedicadoa la comunicacion:

Granularidad fina: se hace relativamente pocacomputacion entre comunicaciones sucesivas:

tiempo

Granularidad gruesa: se hace mucha computacionentre comunicaciones sucesivas:

tiempo

Computacion Comunicacion


Paralela

Miguel Hermanns









Resumen

Lımites a la paralelizacion: ley de Amdahl

Ley de Amdahl:

Speedup teorico =1

(1− P) + P/N

donde:

P: fraccion de codigo que es paralelizable

N: numero de procesadores a usar

La parte no paralelizable limita la escalabilidad:

N:P 0.50 0.90 0.99

10 1.82 5.26 9.17100 1.98 9.17 50.25

1000 1.99 9.91 90.9910000 1.99 9.91 99.02

∞ 2.00 10.00 100.00


Paralela

Miguel Hermanns









Resumen

Lımites a la paralelizacion: ley de Amdahl

Muchos problemas mejoran su escalabilidad con el tamano:

∂T

∂t= α

∂2T

∂x2

Resolucion con ∆x1 y ∆t1:

Calculos numericos 85s 85.00%Fraccion serial 15s 15.00%

Resolucion con ∆x2 = ∆x1/2 y ∆t2 = ∆t1/4:

Calculos numericos 680s 97.84%Fraccion serial 15s 2.16%

Problemas en los que P crece con N son mas escalables


Paralela

Miguel Hermanns









Resumen

Lımites a la paralelizacion: las comunicaciones

La comunicacion entre procesos lleva su tiempo:

tcom = L +M

B

donde:

L: Latencia de la red

M: Tamano del mensaje a enviar

B: Ancho de banda de la red

Latencia Ancho de banda PrecioGigabit Ethernet 90µs 0.1 GBs 80eMyrinet-10G 2µs 1-2 GBsInfiniband 2µs 1-2 GBs 800eQuadrics 2µs 1-2 GBsMemoria RAM DDR2 0.02µs 4-8 GBs


Paralela

Miguel Hermanns









Resumen


Evolucion historica de las redes de comunicaciones:


Paralela

Miguel Hermanns









Resumen


Estrategias para reducir las comunicaciones:

Cambiar la formulacion del problema

Cambiar de metodo numerico

Duplicar ciertos calculos

Modificar el metodo numerico

Usar una granularidad mas gruesa

Estrategias para acelerar las comunicaciones:

Comprar una red con mas ancho de banda

Comprar una red con menos latencia

Usar memoria compartida


Paralela

Miguel Hermanns









Resumen

Diseno de programas paralelos

1 Entender el problema y el programa

2 Inhibidores del paralelismo

3 Identificacion de la carga y cuellos de botella

4 Estrategias de descomposicion del problema

5 Balance de la carga

6 Requerimientos de comunicacion

7 Seleccion del paradigma de programacion


Paralela

Miguel Hermanns









Resumen

¿Paralelizacion manual o automatica?

Existen herramientas capaces de autoparalelizar programas:

Analizan y buscan oportunidades de paralelismo

Tambien identifican inhibidores del paralelismo

Pero estas herramientas presentan serios problemas:

El programa puede proporcionar resultados erroneos

La eficiencia paralela puede ser mala

Limitado principalmente a bucles

Estas herramientas son principalmente para Fortran

La paralelizacion es un trabajo manual ylo seguira siendo durante muchos anos


Paralela

Miguel Hermanns









Resumen

Entender el problema y el programaHay problemas que son paralelizables y otros que no:

Problema paralelizable: calcular el potencial deenergıa de miles de conformaciones posibles de unamisma molecula y determinar la conformacion demınimo potencial de energıa

Problema no paralelizable: Calcular la serie deFibonacci mediante su formula de recurrencia:

Fk+2 = Fk+1 + Fk , F1 = 1, F2 = 1


Paralela

Miguel Hermanns









Resumen

Carga computacional y cuellos de botella

En un problema/programa hay que identificar:

Donde se produce la carga computacional y tratar deparalelizar solo esa parte

Donde estan los cuellos de botella y tratar dereducirlos o de reordenar convenientemente el programa

Donde van a hacer falta comunicaciones entreprocesos (modelo de paso de mensajes)

Donde van a hacer falta sincronizaciones entre tareas(modelo de tareas)


Paralela

Miguel Hermanns









Resumen

Inhibidores del paralelismo

El motivo mas comun es la dependencia de datos:

Dependencia de datos en bucles:

do i = 2, 100A(i) = A(i-1) * 2

enddo

Dependencia de datos fuera de bucles:

! Tarea 1 Tarea 2... ...

x = 2 x = 4... ...

y = x**2 z = x**3

x esta en memoria compartida: ¿Cual es su valor?


Paralela

Miguel Hermanns









Resumen

Inhibidores del paralelismo

El segundo motivo es la entrada y salida de datos (I/O):

Solo un proceso/tarea puede escribir en un fichero

Los anchos de banda de red y discos son crıticos

Estrategias para reducir la entrada y salida de datos:

Reducir al maximo las operaciones I/O

Crear ficheros independientes para cada proceso

Usar librerıas de lectura y escritura paralela


Paralela

Miguel Hermanns









Resumen

Descomposicion de dominios

Los datos a manipular son divididos en bloques a procesarpor las diferentes tareas del programa:

Juego de datos

Tarea 1 Tarea 2 Tarea 3 Tarea 4


Paralela

Miguel Hermanns









Resumen

Estrategias de descomposicion de dominios1D:

bloques cıclico

2D:

bloques,* *,bloques bloques,bloques

cıclico,* *,cıclico cıclico,cıclico


Paralela

Miguel Hermanns









Resumen

Descomposicion funcional

El problema es dividido atendiendo al trabajo a realizar envez de a los datos a manipular:

Juego de instrucciones



Paralela

Miguel Hermanns









Resumen

Descomposicion funcional: ejemplos

Modelos climaticos:

Cada submodelo representa una tarea independiente

Los submodelos intercambian informacion entre sı

Modelo atmosferico

Modelo oceanicoModelo hidrologico

Modelo terrestre


Paralela

Miguel Hermanns









Resumen

Descomposicion funcional: ejemplos

Turborreactor (Center for Turbulence Research):

El turborreactor es dividido en sus componentes

Los componentes interactuan entre sı


Paralela

Miguel Hermanns









Resumen

Balance de la carga

La descomposicion del problema debe ser equilibrada:

Todos los procesos deben estar trabajando siempre

Es fundamental para la eficiencia paralela

Tarea 1

Tarea 2

Tarea 3

Tarea 4

tiempo

Trabajando Esperando

Sin

croniz

aci

on


Paralela

Miguel Hermanns









Resumen

Balance de la carga

Maneras de equilibrar la carga:

Distribucion equitativa del trabajo entre los procesos:

Realizar la descomposicion de dominios en partes iguales

Dividir los bucles en tramos iguales

En ordenadores heterogeneos, realizar medidas develocidad para decidir la descomposicion del problema

Asignacion dinamica del trabajo:

La distribucion equitativa no siempre resuelve elproblema del balance de la carga

El trabajo es asignado a los procesos a medida queterminan las asignaciones anteriores


Paralela

Miguel Hermanns









Resumen

Requerimientos de comunicacion y sincronıa

No todos los problemas requieren la misma comunicacion:

No se necesita comunicacion o sincronıa:

Renderizacion de pelıculas

Plegado de proteınas

Procesamiento de imagenes y senales

Sı se necesita comunicacion o sincronıa:

Mecanica de fluidos computacional

Astrofısica

Elasticidad y resistencia de materiales


Paralela

Miguel Hermanns









Resumen

Seleccion del paradigma de programacion

Teniendo en cuenta todo lo anterior y ademas:

El tipo de ordenador paralelo que se vaya a utilizar

Las caracterısticas del problema/programa a paralelizar

El tiempo disponible para la implementacion paralela

se selecciona el paradigma de programacion apropiado:

Paradigma de paso de mensajes: MPI

Paradigma de tareas: OpenMP

Otro paradigma ...


Paralela

Miguel Hermanns









Resumen

Ejemplos de paralelizacion

Problemas a paralelizar:

Procesamiento de imagenes

Calculo de una integral

Ecuacion de ondas unidimensional

Ecuacion del calor bidimensional

Objetivos a alcanzar:

Asentar los conceptos del paralelismo

Ver el efecto de la naturaleza de los problemas

Ver el efecto de cambiar el metodo numerico

Ver el efecto de cambiar la estrategia de descomposicion


Paralela

Miguel Hermanns









Resumen

Procesamiento de imagenes

Problema: aplicar un filtrof (x , y , c) a una imagen dada

Version serial del algoritmo:

do j = 1, Numero_Pixels_en_j

do i = 1, Numero_Pixels_en_i

Color = Imagen(i,j)

Imagen(i,j) = f(i,j,Color)

enddo

enddo

La aplicacion del filtro a un pixel nodepende de los pixels vecinos

Es embarazosamente paralelo

f (x , y , c)


Paralela

Miguel Hermanns









Resumen

Procesamiento de imagenes: solucion 1

Descomposicion de dominios

Division equitativa de la imagen

Nula comunicacion entre procesos

La estrategia de descomposiciondepende del lenguaje (Fortran o C)

Cada proceso o tarea realiza:

j1 = Mi_Primera_Columna

j2 = Mi_Ultima_Columna

do j = j1 , j2


Color = Imagen(i,j)


enddo

enddo

1 2 3 4

(Fortran)


Paralela

Miguel Hermanns









Resumen


Version paralela del algoritmo:

ID = Quien_soy_yo

Si soy ID = Jefe entonces

Cargo Imagen desde fichero

Mando a cada Currito los valores j1 y j2

Mando a cada Currito su parte de Imagen

Recibo de cada Currito los resultados

Si soy ID = Currito entonces

Recibo j1 y j2 del Jefe

Recibo mi parte de Imagen del Jefe

do j = j1 , j2


Color = Imagen(i,j)


enddo

enddo

Devuelvo mi parte de Imagen al Jefe


Paralela

Miguel Hermanns









Resumen


Banco de tareas (pool of tasks):

Es una manera dinamica de balancear la carga

Se crea un banco de tareas/trabajos a realizar

Un proceso maestro:

Gestiona el banco de tareas

Envıa tareas a los procesos que lo requieren

Recolecta los resultados enviados por los procesos

Un proceso esclavo:

Recibe tareas del proceso maestro

Realiza las tareas encomendadas

Devuelve los resultados al proceso maestro


Paralela

Miguel Hermanns









Resumen


Version paralela del algoritmo (1 maestro y 1 esclavo):

ID = Quien_soy_yo


Mientras haya tareas en el banco

Mando al Currito la siguiente tarea (i,j)

Recibo del Currito los resultados

Avisa al Currito de que ha terminado


Mientras haya tareas que realizar

Recibo del Jefe la tarea (i,j)

Color = Imagen(i,j)


Mando los resultados al Jefe


Paralela

Miguel Hermanns









Resumen


Caracterısticas del metodo del banco de tareas:

Cada tarea consiste en aplicar el filtro al pixel (i,j)

El balance de carga es bueno

Poco calculo entre comunicaciones: granularidad fina

Una mejora serıa definir tareas con mas trabajo

El tamano optimo de tarea depende del problema


Paralela

Miguel Hermanns









Resumen


Problema: calcular la integral definida siguiente:

I =

∫ b

af (x) dx

Las integrales definidas tienen la siguiente propiedad:

I =

∫ x1

af (x) dx +

∫ x2

x1

f (x) dx + . . . +

∫ b

xN

f (x) dx

El propio problema indica la estrategia paralela a seguir:descomposicion de dominios

Calcular la integral es embarazosamente paralelo


Paralela

Miguel Hermanns









Resumen


Version paralela del algoritmo de integracion:

ID = Quien_soy_yo


Subdivido [a,b] en subintervalos

Mando a los Curritos sus valores a_i y b_i

Recibo de los Curritos los resultados

Sumo todos los resultados para obtener la integral


Recibo del Jefe los valores a_i y b_i

Integro f(x) desde a_i hasta b_i

Mando el resultado al Jefe


Paralela

Miguel Hermanns









Resumen


Problema: resolver la ecuacion diferencial

∂2u

∂t2=

∂2u

∂x2

con las condiciones de contorno e iniciales

u(0, t) = 0, u(π, t) = 0, u(x , 0) = f (x)

Con diferencias finitas de segundo orden:

d2ui

dt2=

ui+1 − 2ui + ui−1

∆x2, ∆x =

π

N

0 x1 x2. . . xi−1 xi xi+1

. . . xN−1 π

u0 = 0u1

u2ui1

uiui+1

uN−1

uN = 0


Paralela

Miguel Hermanns









Resumen


Estrategia paralela: descomposicion del dominio

0 π


ui−1

uiui+1

Hacen falta comunicaciones para resolver el problema:

d2ui

dt2=

ui+1 − 2ui + ui−1

∆x2

La carga esta balanceada si los bloques de nodos son iguales


Paralela

Miguel Hermanns









Resumen


Version paralela de las diferencias finitas:

ID = Quien_soy_yo

NID = Cuantos_somos

Divido el intervalo [0,pi] en NID partes

Me quedo con la parte ID del intervalo

Leo la condicion inicial que me corresponde

Mientras que t < t_final

Avanzo un paso temporal dt

Comunico a los procesos vecinos mis valores frontera

Recibo de los procesos vecinos sus valores frontera

Si ID = 0 o N impongo condiciones de contorno

¿Se puede hacer mejor que esto?


Paralela

Miguel Hermanns









Resumen


Cambio de metodo numerico: Fourier-Galerkin

u(x , t) =∞∑

k=1

uk(t) sin (kx)

El problema a resolver es:

d2uk

dt2= −k2uk , uk(0) =

1

π

∫ π

−πu(x , 0) sin (kx) dx

Estrategia paralela: descomposicion en frecuencias

No hacen falta comunicaciones

Este problema es embarazosamente paralelo

¡La estrategia paralela depende del metodo numerico!


Paralela

Miguel Hermanns









Resumen


Problema: resolver la ecuacion

∂T

∂t=

∂2T

∂x2+

∂2T

∂y2

con las condiciones

T (x , y , t)|∂Ω = g(s)

T (x , y , 0) = f (x , y)x

y

Metodo numerico: diferencias finitas de 2o orden

dTi ,j

dt=

Ti+1,j − 2Ti ,j + Ti−1,j

∆x2+

Ti ,j+1 − 2Ti ,j + Ti ,j−1

∆y2

Estrategia paralela: descomposicion de dominios


Paralela

Miguel Hermanns









Resumen


Tres maneras de hacer la descomposicion de dominios:

1 2 3 4

Organizacion de memoria buenapara Fortran

El volumen de comunicaciones esdel orden de NyNproc

1

2

3

4

Organizacion de memoria buenapara C

El volumen de comunicaciones esdel orden de NxNproc


Paralela

Miguel Hermanns









Resumen


Tres maneras de hacer la descomposicion de dominios:

1 2

3 4

La organizacion de memoria no esoptima, pero es buena

El volumen de comunicaciones esdel orden de (Nx + Ny )

√Nproc

NO exite la descomposicion perfecta:

Depende del lenguaje de programacion

Depende del ordenador paralelo

Depende del metodo numerico

Depende del problema ...


Paralela

Miguel Hermanns









Resumen

Resumen

1 Motivacion de la programacion en paralelo

2 Clasificacion logica del paralelismo

3 Clasificacion fısica de ordenadores paralelos

4 Paradigmas de programacion paralela

5 Conceptos generales y terminologıa habitual

6 Diseno de programas paralelos

7 Ejemplos de paralelizacion


Paralela

Miguel Hermanns









Resumen

Agradecimientos

Oscar FloresUniversidad Politecnica de Madrid

introducción a la programación paralelawebserver.dmt.upm.es/zope/dmt/members/hermanns/... ·...

Documents