1
Programación Paralela yConcurrente
M. en C. Mario Farías-Elinos
Contenido
T IntroducciónT Paralelismo, Concurrencia, Pipeline.T Complejidad, Threads, Proceso.
T ObjetivosT Modelos de computación
T SISD, SIMD, MISD, MIMD
T ClasificaciónT Micros, Minis, Mainframes, Supercomputadora.
2
Contenido
T Filosofía de procesamiento:T Maestro-esclavo.T Misma jerarquía.
T Arquitecturas paralelas T Paralelismo
T Paradigma de HomoparalelismoT Paradigma de Heteroparalelismo
T Primitivas del Paralelismo
Contenido
T Concurrencia.T Tipos de concurrencia.
T EREW, ERCW, CREW, CRCW.
T Parallel Virtual Machine (PVM).T Tendencia.T Aplicaciones.T Conclusiones.
3
Definiciones
T Secuencialidad: Ejecución de una sóla instrucción en cada ciclo.
T Concurrencia:T Ejecución simultanea de instrucciones dentro
de una computadora.T Acceso simultaneo de datos en una
computadora.
Definiciones
T Procesamiento paralelo: Manejo deinformación que enfatiza la manipulación concurrente por uno o más procesadores para la solución de un problema.
T Computadora paralela: Computadoramulti-procesador con capacidad deprocesamiento paralelo.
T Supercomputadora: Computadora concapacidad de cómputo masívo.
4
Definiciones
T Pipeline: Ejecución de varias instruccionesen cada ciclo.
T Paralelismo: Aplicación de multiplesprocesadores que realizan la misma operación en forma simultanea sobre elementos de un conjunto de datos.
T Pipeline y Paralelismo incrementan laconcurrencia.
Definiciones
5
Definiciones
T Proceso: Se define como el ambiente detrabajo (variables de ambiente, código, PID, etc.) que involucra una tarea.
T thread o hilo: es la escencia del proceso(código, registros del procesador, etc.).
Complejidad
T Comportamiento de un algoritmo T Clases de complejidad:
T P: Problemas de decisión que se resuelven en un tiempo polinomial.
T NP: Problemas que se resuelven en un tiempo polinómico no determinístico.
T NP-completo: Problemas que se resuelven en un tiempo no polinómico.
6
Complejidad
T Notaciones de la complejidad:
O
o
asintoticamente a la cota superior
cota superior no asintoticamentecota inferior no asintoticamente
asintoticamente a la cota inferior
incluye las 4 anteriores
ω
θΩ
Complejidad
7
Introducción
T ¿Por qué el surgimiento del Paralelismo?
T ¿Por qué surgen las Arquitecturas Paralelas?
Objetivos
T Reducir el tiempo de cómputo.
T Reducir la complejidad del algoritmo.
T Aprovechas al máximo la capacidad de las computadoras multiprocesador.
8
Modelo SISD
T Simple Instruction, Simple Data.T Consiste de un procesador que recibe un simple
flujo de instrucciones y de datos.T Un algoritmo para esta clase se dice ser secuencial
o serial.
Modelo MISD
T Multiple Instruction, Single Data.T Existencia de N procesadores con un simple
flujo de datos ejecutando instrucciones diferentes en cada procesador.
9
Modelo SIMD
T Simple Instruction, Multiple Data.
T Existen N procesadores ejecutando la misma instrucción sobre los mismos o diferentes datos.
T Existencia de datos compartidos.
Modelo MIMD
T Multiple Instruction, Multiple Data.
T Existen N procesadores ejecutando instrucciones diferentes sobre los mismos o diferentes datos.
T Existencia de datos compartidos.
10
Microcomputadoras
T Procesadores de 32 y 36 bits (Direcc.), y 32 y 64 bits (Datos).
T Monousuario (NT/2k, Win9x) yMultiusuario (UNIX)
T Multiprocesador (NT, UNIX)
Minicomputadoras
T Procesadores de 32 y 64 bits (Direc.), y 32 y 64 bits (Datos).
T MultiusuarioT Multiprocesador
(RISC)
11
Mainframes
T Procesadores de 32 y 64 bits (Direc.), y 32 y 64 bits (Datos).
T MultiusuariosT Multiprocesadores
Supercomputadoras
T procesadores de 128 bits (Addr) y 128 bits (Datos).
T MultiusuarioT Multiprocesador
12
Maestro-esclavo
T Un procesador controlador (Maestro)
T Procesadores controlados (esclavos) que reportan al Maestro
Misma jerarquía
T Procesadores independientes, no reportan anadie.
T Inexistencia de un controlador
13
Arquitecturas
T Organización de los procesadores.T El método de conectar a los procesadores
en paralelo.T MallaT Arbol binarioT HiperárbolT PiramidalT Mariposa
T HipercuboT Hipercubo cíclicoT Transpaso-intercambioT de Bruijn
Arquitecturas
T Criterios de organizaciónT Diámetro: Máxima distancia entre dos nodos. Un
diámetro pequeño es el ideal, esto genera una cotainferior en la complejidad (comunicación).
T Ancho de Bisección: Es el número mínimo debordes que deben ser removidos a fin de dividir la red en dos mitades. Un alto AB es el ideal, estogenera una cota inferior en la complejidad(movimiento de datos).
14
Arquitecturas
T Número de bordes por nodo: Si este es un valorconstante e independiente al arreglo permite escalar facilmente al sistema con un mayornúmero de nodos.
T Máxima longitud de borde: Por razones deescalabilidad es mejor que el valor de contornosy nodos puedan ser constantes.
Malla
T Arreglo de nodos enrejilla q-dimensional.
T Un nodo se comunicacon 2q nodos.
T No hay jerarquía.
15
Arbol binario
T Existen 2k-1 nodos con una profundidad de k-1.
T Un nodo tiene a lo más tres ligas.
T En el interior un nodo sepuede comunicar a lo máscon dos nodos hijos y con elnodo padre.
T Diámetro pequeño.T Ancho de Bisección pobre.
T Maestro-esclavo
Hiperárbol
T Unión de árbol binario invertido y un árbolcon k hijos.
T Objetivo:T Mejorar el Ancho de Bisección.
16
Piramidal
T Combinación de una malla y un arbol.
T Reduce el diámetro conrespecto a la malla.
T El máximo número deligas por nodo no esmayor a 9.
Mariposa
T Consiste de (k+1)2k
nodos dividido en k+1renglones o rangos.
T k es el rango cuyo valoresta entre 0 y n.
T Los nodos internos tiene4 conecciones, y los externos 2 conecciones.
T Las ligas forman un patron de mariposa.
17
Hipercubo
T Consiste de 2k nodos formando unhipercubo k-dimensional.
T Los nodos se etiqueta de 0 a 2k-1.T Dos nodos son adyacentes si en la etiqueta
varia a lo más un bit en una posición.
nCUBE
T Procesadores: (64 bits) 8 hasta 8192.
T Memoria: 32 Mbhasta 262 Gb.
T Flops: T M5: 1.92 GflopsT M10: 34 Gflops
18
Cubo cíclico
T Es un hipercubo k-dimensional.
T Existen k nodos por vértice.
T Diámetro dos vecesmayor al hipercubo.
T Ancho de bisección es menor que al hipercubo
Transpaso-Intercambio
T Consiste de 2k nodos.T Dos tipos de ligas:
T Intercambio: Se realiza entre los procesadores donde cambia el bit más significativo.
T Transpaso: Se lleva a cabo entre el nodo i y elnodo 2i mod (n-1).
19
de Bruijn
T Existen 2k nodos.T Los procesadores de la Triton/1TM
(Universidad de Karlsruhe, 1992), estan conectados de esta manera.
Comparación
Organización Nodos Diámetro Anchode
bisección
Contornoconstante
Longitudconstante
Malla n-D nk n(k - 1) kn-1 Si SiArbol binario 2k - 1 2(k - 1) 1 Si No4-Hiperarbol 2k(2 k+1 - 1) 2k 2k+1 Si NoPiramidal (4k2 - 1) / 3 2 log k 2k Si No
Mariposa (k + 1)2k 2k 2k Si NoHipercubo 2k k 2k-1 No NoCubo cíclico k2k 2k 2k-1 Si No
Transpaso-Intercambio 2k 2k - 1 ≥2k-1 / k Si Node Bruijn 2k k 2k / k Si No
20
Paralelismo
T Concideraciones para la programación enparalelo:T Independencia de datos.T El tipo de problema y la cantidad de datos.
Homoparalelismo
T Crear subtareas idénticas de igual carga computacional.
T Ejecución simultanea.T Independencia.
21
Heteroparalelismo
T Creación de subtareas diferentes.T Ejecución simultanea.T Independencia.
Primitivas del paralelismo
T m_fork: Creación de cada thread que seejecutará en cada procesador.
T m_kill_procs: Eliminación de algún threadque se este ejecutando.
T m_set_proc: Indica el número deprocesadores a utilizar.
T m_get_numprocs: Obtiene el número deprocesadores que se estan utilizando.
22
Primitivas del Paralelismo
T m_park_procs: Bloquea un thread y libera los recursos
T m_rele_procs: Reactiva el thread bloqueado.T m_lock: Aisla una variable para evitar que
otro thread la accese.T m_unlock: Remueve el aislamiento de la
variable.
Primitivas del Paralelismo
T m_sync: Detiene la ejecución de un threadpara esperar que otros thread lleguen hasta ese punto del código y continuar en formasicronizada.
23
Concurrencia
T Se puede definir como la Programación entiempo real.
T Ejecutar varios procesos en formasimultanea en una computadora.
T Se utiliza un Schedule, el cual se encarga deadministrar a los procesos en ejecución.
Concurrencia
T Se recomienda utilizar Sistemas Operativoscon microkernel que permite laprogramación de threads.
T Modos de controlar la concurrencia en unsistema centralizado:T Candados (Locks).T Semaforos.T Mensajes.
24
EREW
T Exclusive Read, Exclusive Write.T Sólo un proceso puede leer y escribir al
mismo tiempo.T Puede caer en dead-lock (candado mortal).T Genera lentitud de procesos.
ERCW
T Exclusive Read, Concurrent Write.T Sólo un proceso puede leer y todos los
procesos pueden escribir en formasimultanea.
T Puede generar inconsistencia deinformación.
T Puede caer en dead-lock.
25
CREW
T Concurrent Read, Exclusive Write.T Todos los procesos pueden leer pero sólo un
proceso puede escribir.T Puede caer en dead-lock.
CRCW
T Concurrent Read, Concurrent Write.T Todos los procesos pueden leer y escribir
simultaneamente.T Puede generar inconsistencia de
información.T No se presentan dead-lock.
26
Parallel Virtual Machine (PVM)
T Software de dominio público (Internet).T Computadoras interconectadas en red
protocolo TCP/IP (Ethernet, FDDI, ATM).T Colección de computadoras UNIX
heterogeneas:
Parallel Virtual Machine (PVM)
T Memoria local ocompartida (SPARCstation).
T Multiprocesadores(Alpha-Server).
27
Parallel Virtual Machine (PVM)
T Procesamiento vectorial (CRAY).
Parallel Virtual Machine (PVM)
T Compartir los procesadores y memoria.T Programación en C y C++.T daemon controlador de comunicación y
procesos entre las computadoras.T Programación bajo la filosofia:
T Maestro-esclavo.T Misma jerarquía.
28
Parallel Virtual Machine (PVM)
T Versión Beta para Windows de 32 bits (9x y NT)
Tendencia
T Compartir el o los procesadores, además delos recursos de la computadora.
T Paralelismo distribuido.T Control de concurrencia:
T Candados.T Control óptimo de la concurrencia.T Estampa de tiempo.
29
Tendencia
T Implantar Sistemas Operativos Distribuidos.T Implica:
T Tolerancia a Fallas.T Transparente.T Escalabilidad.T Concurrencia.T Abierto.T Compartición de recursos.
Aplicaciones ULSA
T Control del Pendubot (Concurrente).T Control en tiempo real
T Datos de entradaT Datos de salida
30
Aplicaciones ULSA
T Visión artificial aplicado a Robótica.
Aplicaciones ULSA
T Cálculo de Testores por algoritmo paralelo.T Algoritmos paralelos para el procesamiento
de imágenes.T Algoritmos paralelos para el
Reconocimento de patrones utilizando unaRed Neuronal Difuza.
T Algoritmos de Autómatas Celulares
31
Aplicaciones ULSA
T Reasignación de procesos utilizando Lógica Difuza en en un Sistema Distribuido.
T Programación paralela de Redes Neuronales Artificiales.
Conclusiones
T Las técnicas de paralelismo ofrecen un mayor poder de cómputo.
T Reducción del tiempo de cómputo.T Con PVM no hay dependencia del set de
instrucciones del Hardware.T En un paralelismo distribuido hay
dependencia de la funcionalidad de la red.
32
Conclusiones
T Bajo PVM no hay control de la carga detrabajo que tenga el procesador anfitrión.
T Para algunes problemas es mejor utilizar programación concurrente (tiempo real) que programación paralela.
T Proyectos realizados por ESTUDIANTES.