Post on 20-Sep-2018
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Metodologıa de la Programacion Paralela
Facultad Informatica, Universidad de Murcia
Introduccion a laComputacion Paralela
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Bibliografıa basica
Del curso, capıtulos 1 a 6
De esta sesion, capıtulos 1 y 2
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Contenido
1 Introduccion
2 Sistemas y Programacion Paralela
3 Paradigmas de Programacion ParalelaClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
4 Entornos de Programacion ParalelaEjemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Programacion Paralela
Uso de varios elementos de proceso trabajando juntos pararesolver una tarea comun:
Cada elemento de proceso trabaja en una porcion delproblemae intercambian datos, a traves de la memoria o por una red deinterconexion
¿Diferencia con programacion concurrente?¿Que visto en programacion concurrente?¿Y en arquitectura de ordenadores?
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Necesidad de la Programacion Paralela
Lımites de sistemas secuenciales:
MemoriaVelocidadIncremento economico superior al de prestaciones
Solucion⇒ paralelismo:
Dificultades fısicas: integracion, velocidad de acceso a datosDificultades logicas: uso, programacion
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Necesidad de la Programacion Paralela
Sistemas paralelos permiten resolver:
Problemas mayores (memoria)Mas rapidamente (velocidad)
Aplicacion en:
Problemas de alto coste computacionalProblemas de gran dimensionProblemas de tiempo real
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Aspectos de la Programacion Paralela
Dificultades fısicas:
Mayor velocidadde proceso que deacceso a memoriay comunicacionIntegracion
Lımites develocidad de laluzDisipacion decalor
Consultar TOP 500: www.top500.org
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Contenidos del curso
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Variedad de sistemas computacionales
Los sistemas computacionales actuales estan constituidos porvarios componentes, por lo que son sistemas paralelos,pero estos componentes estan organizados de formas distintas:
Sistemas con varios cores y una memoria comun a todos
Un sistema multicore con una tarjeta grafica con su propiamemoria
Redes de multicores, cada uno con su memoria yposiblemente su tarjeta grafica
Varias redes conectadas entre sı de forma remota
etc
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Variedad de estilos de programacion
Una unica secuencia de ejecucion de las instrucciones(programacion secuencial)
Una secuencia de ejecucion, con algunas instrucciones quemandan trabajo a realizar a otro componente computacional
Distintas secuencias que se ejecutaran en elementoscomputacionales distintos colaborando a traves de lamemoria
Distintas secuencias que se ejecutaran en elementoscomputacionales distintos colaborando intercambiandoinformacion por medio de mensajes
etc
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Conceptos de Programacion Paralela
Paralelismo en sistemas secuenciales
Concurrencia - Programacion Concurrente
Paralelismo - Programacion Paralela
Sistemas de tiempo real - Programacion en tiempo real
Sistemas multicore
Tarjetas graficas, GPU
Aceleradores: Xeon Phi, FPGA, DSP...
Redes de ordenadores, Clusters
Computacion heterogenea
Supercomputacion
Computacion de Altas Prestaciones, HPC
Programacion adaptativa
Computacion distribuida
Computacion en la nube, Cloud
Computacion ubicua
Virtualizacion
Otros tipos: Computacion Cuantica, Biologica...
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (I)
Multiples unidades funcionales
por ejemplo varios sumadores o multiplicadores
Unidades vectoriales
se realizan operaciones simultaneas sobre conjuntos de datos.
Hay librerıas para vectorizacion (SSE, Streaming SIMD Extensions)
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (II)
Los procesadores actuales consiguen acelerar la ejecucion haciendo uso delparalelismo de forma interna. Ejemplos:
Segmentacion encauzada (pipeline):
division de la ejecucion de las instrucciones en etapas
una instruccion empieza a ejecutarse antes de que hayan terminado las anteriores
varias instrucciones se procesan simultaneamente
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (III)
Procesador supersegmentado:
cada etapa se divide en subetapas
y se lanzan subetapas sin completar el ciclo de reloj
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (IV)
Procesador superescalar:
lanzar varias instrucciones simultaneamente,
para ejecucion fuera de orden o especulacion
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (V)
Very Long Instruction Word
procesamiento de varias instrucciones en paralelo
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (VI)
Division de memoria en bloques:
varios procesos pueden acceder a la vez a zonas de memoria distintas
Jerarquıa de memorias:
varios niveles de cache,
acceso mas rapido a las memorias mas cercanas
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (VII)
Multithreadingel sistema lanza varios threads (hilos) simultaneamente, quecomparten recursos
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Paralelismo en sistemas secuenciales (y VIII)
Paralelismo a nivel de instruccionreordenar las instrucciones para que se puedan ejecutar enparalelo sin afectar al resultado
Ejecucion fuera de ordense capturan los datos para estar disponibles cuando puedeejecutarse la instruccion
Especulaciondeterminar que resultados se van a necesitar y generarlosantes
Coprocesadores de E/Spermiten realizar entrada/salida mientras se computa
...
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Concurrencia - Paralelismo
Concurrencia, Programacion Concurrente
cuando varios elementos de proceso (hilos,procesos) trabajan de forma conjunta en laresolucion de un problema
Paralelismo, Programacion Paralela
lo mismo, pero se usan estos terminos cuando eltrabajo se utiliza para acelerar la resolucion de losproblemas
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Sistemas de tiempo real, Programacion de tiempo real
Para problemas que requieren respuesta en un espacio corto detiempopara lo que se necesita usar de manera eficiente los recursoscomputacionales,y por tanto realizar computacion paralela.Ejemplos:
Vıdeojuegos, Animaciones, que requieren generar al menos24 imagenes por segundo
Control, con informacion recogida por sensores, y el sistematiene que dar respuesta rapida
Robotica
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Multicore
Los sistemas multicore (multinucleo) contienen varios cores que tienen acceso a unespacio de memoria comun, organizado de forma jerarquica.
En la actualidad son los sistemas computacionales estandar, y sistemas mascomplejos se obtienen combinando varios de ellos.
Se programan a traves de hilos (threads), que comparten datos en la memoriacomun.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Tarjetas graficas, GPU
Originariamente para vıdeojuegos, en la actualidad tambien para procesamiento deproposito general (GPGPU).Normalmente como coprocesadores con un sistema multicore, que dispone de una ovarias GPUs.El programa se ejecuta en CPU y manda trabajos a la GPU.Programacion dependiente del fabricante (CUDA) y tambien hay software portable(OpenCL).Constan de muchos cores de GPU, organizados en bloques, y con organizacionjerarquica de la memoria.Varios tipos de tarjetas con distintas capacidades computacionales (Gforce, Tesla,Kepler...)
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Otros aceleradores
Los aceleradores computacionales o coprocesadores se utilizan normalmentemandandoles trabajo desde la CPU para que se encarguen de realizar calculoscomputacionalmente costosos.Ademas de las GPUs hay algunos tipos mas:
Intel Xeon Phi:Contiene hasta 61 cores, y cada core soporta 4 threads por hardware.Programacion mas cercana que la de las GPUs a la estandar en paralelo.
FPGA (Field Programmable Gate Array):Similares a circuitos integrados pero reprogramables.Programacion distinta a la paralela estandar.
DSP (Digital Signal Processor):Para tratamiento de senales y problemas en tiempo real.Normalmente para operaciones matematicas que se repite continuamente.
SBC (Single Board Computer):Normalmente para sistemas embebidos, con bajo consumo de potencia.Ejemplo: Raspberry Pi
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Clusters, Redes de ordenadores
Compuestos por varios componentes computacionales(nodos) conectados en red.
Los nodos pueden estar enrackados o de forma aislada.
En la actualidad los nodos suelen ser multicoresposiblemente con GPUs.
Pueden ser desde clusters pequenos formados por unospocos nodos hasta muchos nodos formando unsupercomputador.
En algunos casos los nodos comparten el sistema deficheros, que tambien puede ser distribuido.
Se suele usar un sistema de colas para mandar lostrabajos de los usuarios al sistema.
La programacion estandar es multihilo en los nodos ymultiprocesos entre nodos.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Computacion heterogenea
Los componentes de un sistema computacional presentandistintas fuentes de heterogeneidad:
Memorias primarias y secundarias de distinta capacidad ycon distinta organizacion.
Componentes computacionales con distinta velocidad.
Componentes computacionales de distinta arquitectura(ejemplo, multicore+GPU).
Redes de conexion a distinta velocidad.
...
lo que hace que haya que programarlos de forma especial paraaprovechar al maximo la capacidad de todos ellos, quizas conprogramacion paralela estandar pero asignacion balanceada detrabajos a los distintos componentes.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Supercomputacion
La que se realiza en loscomputadores mas potentes pararesolver los problemas cientıficos conmayores necesidadescomputacionales (simulacionclimatica, analisis de ADN...)
Varıa historicamente. Lista Top500contiene los 500 mas rapidos delmundo, se actualiza cada seis meses.
Problemas de gestion, sistemas deenfriamiento, reduccion del consumode energıa (Green computing)...
Sunway TaihuLighten el National Super Computer Center inWuxi, ChinaCluster de Intel Xeon + Xeon Phi10.649.600 corespotencia 15.371 kwrendimiento maximo 125.435,9 (93.014,6)Tflops/seg
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
HPC
La Computacion de Alto Rendimiento (o Altas Prestaciones,High Performance Computing) consiste en el aprovechamientoal maximo de las capacidades computacionales del sistema.
Normalmente en supercomputadores, pero tambien enclusters, multicores, y para tiempo real.
Programacion Adaptativa
Al compartirse los grandes sistemas o clusters entre variosusuarios las condiciones de los sistemas cambian a lo largodel tiempo.
Se pueden desarrollar programas que se adapten a lascondiciones del sistema durante su ejecucion.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Computacion Distribuida - Computacion en Grid
Computacion Distribuida
Componentes computacionales organizados en red colaboranen la resolucion de un problema.
Las redes pueden ser geograficamente locales (clusters) odistribuidas.
Interaccionan con envıo de mensajes.
Computacion en Grid
Como la distribuida, pero los componentes computacionalesestan mas separados geograficamente, son heterogeneos, sededican a distintas tareas...
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Cloud computing - Virtualizacion
Computacion en la nube
Uso de recursos computacionales, de almacenamiento, de servicios... ofrecidos atraves de algun sistema como Internet.
Normalmente se refiere a la oferta de los servicios. Hay proveedores de espacio yservicios, incluyendo computacion (por ejemplo, Amazon, Google Compute Engine).
Cuando se ofrece uso de elementos hardware el sistema ofrece esos recursos perono estan siempre asignados fısicamente al mismo hardware.
... Sky Computing, Jungle Computing...
Virtualizacion
Consiste en la oferta y uso de entornos virtuales, ya sea de hardware, sistemas,redes...
Puede permitir un mayor aprovechamiento de los recursos, pues varias maquinasvirtuales pueden estar usando la misma maquina real disminuyenso ası los puntosmuertos.
Ejemplo, rCUDA.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Computacion ubicua - Computacion voluntaria
Computacion ubicua
Se realiza en cualquier momento y con cualquier tipo de dispositivo (moviles,sensores, portatiles, clusters, supercomputadores...)
Puede incluir sistemas con autonomıa, por ejemplo, frigorıficos poniendoseen contacto directamente con la tienda.
Algunos conceptos relacionados: pervasive computing, computacion movil,Internet de las cosas...
Computacion voluntaria
Cuando los usuarios ofrecen sus recursos computacionales(almacenamiento y capacidad de computo) para la resolucion de problemas.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Computacion no convencionalExisten otros tipos de computacion no convencionales que no estan totalmentedesarrollados y que intrınsecamente incluyen paralelismo.
Computacion cuantica
Basada en las propiedades de la fısica cuantica.
Podrıan realizarse multiples operaciones de forma simultanea.
Requiere forma de programacion distinta a la actual.
Hay ya algunos computadores cuanticos, de alto coste y poca capacidad de computoen terminos cuanticos, pero que resuelven algunos problemas determinados de formamucho mas rapida que con la computacion convencional.
Computacion biologica
Basada en la capacidad de elementos biologicos (moleculas, proteınas, ADN...) paraalmacenar y procesar datos.
Se usa en algunas aplicaciones biologicas y de medicina, pero esta lejos de podertener un uso generalizado.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Futuro?
Un par de transparencias de la presentacion de Rafael Asenjo en las Jornadas de
Paralelismo de 2014
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Futuro?
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Clasiflicacion de Flynn
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Secuencial - SISD
Modelo Von Neuman
Instruccionesde memoria a procesador
Datosentre memoria y procesador
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
SIMD
Una unica unidad de control.La misma instruccion se ejecuta sıncronamente por todas lasunidades de procesamiento.Normalmente se consideran en este paradigma las GPU.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
MIMD
Cada procesador ejecuta un programa diferenteindependientemente de los otros procesadores.Es el modelo que usamos en esta asignatura
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Consideramos tres paradigmas basicos que se pueden considerarlos est andares actuales :
Programacion con Memoria Compartida.
Programacion con Paso de Mensajes.
Simple Instruccion Multiple Dato (SIMD).
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
MC- Sistemas
Los sistemas donde se realiza permitenver la memoria compartida por losdistintos elementos de computacion: losdistintos procesos o hilos,independientemente del procesador onucleo donde esten, tienen acceso directoa todas las posiciones de memoria.
Tıpicamente son sistemas multicore, conmemoria dividida en bloques y organizadajerarquicamente, pero en el programa seconsidera la memoria comun, aunquehabra distinto coste de acceso a los datosdependiendo de donde se encuentren.
Imagen de saturno, con hwloc
Problemas de:coherencia de datos (resuelto por el sistemaoperativo)
y contencion (empeoran el tiempo de
ejecucion).
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
MC- Hilos
Los elementos logicos de computacionson los hilos (threads).
Se asocian a elementos fısicos decomputacion, que son los nucleos(cores).
La asociacion hilos-cores se puederealizar de distintas formas (afinidad).
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
MC- Modelo programa
Modelo fork-join:
un hilo genera nuevos hilos (fork)
y los espera para sincronizarse (join)
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
MC- Regiones crıticasCuando los hilos acceden a zonas comunes de datos para variarlos es necesariasincronizacion. Los entornos de programacion en memoria compartida proporcionanherramientas:
Seccion crıtica: solo un hilo puede estar ejecutando esa parte del codigo en unmomento dado.Llaves, semaforos: se puede acceder a esa zona de codigo cuando se cumple unacondicion.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Entornos de programacion en Memoria Compartida
C, C++: tienen llamadas a rutinas del sistema, fork, join yotras.
Java: tiene bibliotecas de concurrencia.
Pthreads: interface de programacion (API) para trabajo conhilos.
OpenMP: especificacion de API para programacion paralelaen Memoria Compartida. Se puede considerar el estandarpara computacion en MC.Se encuentra en implementaciones de lenguajes, como gcc.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Sistemas
En los sistemas donde se realiza esta programacion no sepuede acceder a todas las posiciones de memoria desdetodos los elementos de proceso.
Cada nodo o procesador tiene asociados unos bloques dememoria, a los que puede acceder directamente.
Un proceso asignado a un procesador, para poder acceder adatos en bloques de memoria no accesibles desde eseprocesador, tiene que comunicarse con procesos enprocesadores a los que esta asociada esa memoria.
Son redes (clusters) de ordenadores, formados por nodosmulticore conectados en red, sistemas distribuidos..., perotambien se puede usar programacion por paso de mensajesen sistemas de memoria compartida.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Topologıas de red
Para programacion puede ser mas importante la topolog ıa logica de procesos que la
fısica de procesadores.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Cluster del laboratorio de CCPP
Consultar informacion en luna.inf.um.es/grupo investigacion (no actualizado)
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Procesos
Programa:
Puede haber un unico programa y ponerse en marcha variosprocesos con el mismo codigo. Modelo Simple ProgramaMultiple Dato (SPMD).
Aunque sea el mismo programa los codigos que se ejecutanpueden ser distintos si se compila para arquitecturas distintas.
Puede haber varios programas y generarse procesos concodigos distintos.
Generacion de procesos:
Generacion estatica: todos los procesos se ponen en marchaal mismo tiempo.
Generacion dinamica: unos procesos ponen en marcha otrosdurante la ejecucion.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Memoria
Generacion estatica
Generacion dinamica
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
PM- Mensajes
Los procesos se comunican con mensajes, que pueden ser:
Segun el numero de procesos:Punto a punto: un proceso envıa y otro recibe.Globales: intervienen varios procesos, posiblemente unoenviando o recibiendo datos de todos los demas.
Segun la sincronizacion:
Sıncronos: los procesos que intervienen se bloquean hastaque se realiza la comunicacion.Asıncronos: los procesos no se bloquean. El que envıamanda los datos y sigue trabajando, el que recibe, si no estandisponibles los datos continua con su trabajo.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Entornos de programacion por Paso de Mensajes
Java: tiene bibliotecas de paso de mensajes.
MPI (Message Passing Interface): especificacion de API paraprogramacion con Paso de Mensajes. Se puede considerar elestandar para computacion en sistemas distribuidos.API para varios lenguajes: C/C++, Fortran...Varias implementaciones gratuitas: MPICH, LAMMPI,OpenMPI ...
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
SIMD- Sistemas
Modelo SIMD: muchas unidades de proceso, cada unarealizando la misma operacion (SI) y cada una sobre susdatos (MD).
En la actualidad podemos considerar sistemas SIMDcoprocesadores como:
tarjetas graficas (GPU), hasta ≈ 2500 cores. En los sistemaspara graficos, se pueden programar para proposito general.Intel Xeon Phi, entre 57 y 61 cores, cada uno hasta 4 threadspor hardware.
pero tambien hacen computacion de forma asıncrona,normalmente trabajo en CPU y se manda parte delprocesamiento al coprocesador.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
GPU- Estructura
Constan de varios Streaming Multiprocessors (SMs), cada unocon varios Streaming Processors (SPs):
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
GPU- Memoria
Memorias independientes en CPU y GPU.
Con jerarquıa de memoria en cada una.
Mas compleja la de GPU: optimizar su uso para tener buenas prestaciones.
Y necesario minimizar copias entre memorias de CPU y GPU, o solapar las copiascon computacion.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
GPU- Modelo programacion
Los procesadores (SPs) de un SM ejecutan hilos independientes, pero encada instante ejecutan la instruccion leıda por la Instruction Unit (IU).
En cada SM los hilos los gestiona el hardware: bajo coste.
kernel es la parte de codigo en la CPU que lanza ejecucion a GPU:
Descompone un problema ensubproblemas y lo mapea sobre un grid,que es un vector 1D o 2D de bloques dehilos.
Cada bloque es un vector 1D, 2D o 3D dehilos.
Los hilos usan su identificador de threaddentro de un bloque y de bloque dentro delgrid para determinar el trabajo que tienenque hacer.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
ClasificacionesProgramacion con Memoria CompartidaProgramacion con Paso de MensajesSimple Instruccion Multiple Dato (SIMD)
Entornos de programacion de sistemas SIMD
Programacion de GPU es programacion especıfica:
CUDA para tarjetas NVIDIAOpenCL es estandar para tarjetas de diferentes fabricantes.
En Intel Xeon Phi se puede usar OpenMP y MPI,con compilacion diferenciada para CPU y para el Xeon Phi,peropudiendo trabajar de forma conjunta.
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Ejemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
Veremos ejemplos basicos de programacion paralela en:
Java
C/C++ con fork-join
Pthreads
para trabajar con alguno de ellos en las sesiones de practicas del5 y 10 de octubre.Otros entornos se veran en las sesiones siguientes:
OpenMP
MPI
CUDA
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Ejemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
El programa ejemplojava.java se compila con:javac ejemplojava.java
se ejecuta java ejemplojava X, con X el numero de datos aordenar.Revisar estas clases y metodos de Java para la sesion depracticas:
Se crea una clase (threadordenar) que implementaRunnable .el metodo run llama a ordenar la segunda mitad del array.Los datos y su tamano se declaran globales para que puedanacceder los dos hilos.Se declara un hilo de esa clase: Thread t = newThread(new threadordenar());
y se inicia su ejecucion con t.start().El hilo maestro espera mientras el hilo esclavo esta activo:t.isAlive().
En Java hay muchas otras posibilidades de gestionar laDomingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Ejemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
El programa ejemplofork.cpp se compila con:gcc -O3 ejemplofork.cpp -o ejecutable
se ejecuta ejecutable y se introduce el numero de datos.Revisarlo para la sesion de practicas:
Un proceso puede crear un proceso hijo con la funcion fork .fork devuelve al proceso que lo llama el identificador delproceso hijo, y al hijo el valor cero.El proceso hijo tiene una copia de las variables del procesopadre.y ejecuta el mismo codigo del padre a partir de la zona enque se ha creado.El padre puede usar la funcion wait para esperar que el hijoacabe.Para que padre e hijo trabajen con datos compartidos hayque utilizar funciones de comparticion de memoria, como porejemplo la mmap .
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Ejemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
El programa ejemplopthreads.cpp se compila con:gcc -O3 ejemplothreads.cpp -o ejecutable -lpthread
se ejecuta ejecutable y se introduce el numero de datos.Revisar las siguientes funciones y tipos para la sesion depracticas:
Se usa la librerıa pthreads.hSe declara un array de hilos:pthread t threads[NUM THREADS]
Los hilos se ponen en marcha conpthread create
que recibe la direccion del hilo (&threads[i]), la direccion dememoria de la funcion que ejecuta el hilo, y la direccion de laestructura que contiene los parametros que se pasan a lafuncion ((void *) &thread data array[i])Se espera a que acaben los hilos conpthread join(threads[i], &status)
Domingo Gimenez (domingo@um.es)
IntroduccionSistemas y Programacion Paralela
Paradigmas de Programacion ParalelaEntornos de Programacion Paralela
Ejemplo de uso de hilos en JavaEjemplo de fork-join en CEjemplo de paralelismo con Pthreads
Sesiones de la semana proxima
De teorıa:Programacion de memoria compartida, OpenMP.Consultar la parte correspondiente del capıtulo 3 del libro deIPP.
De practicas:Se trabajara con los ejemplos de Java, C y Pthreadsanteriores y con OpenMP.
Domingo Gimenez (domingo@um.es)