Download 1.3. programacion paralela

1.3. PROGRAMACION PARALELA
• El enfoque tradicional, consiste en extraer el paralelismo de los
lenguajes actuales (C++, Fortran, Ada, Prolog, Lisp, etc). Esto se
puede lograr con un compilador que detecte el paralelismo en un
programa secuencial y que se produzca código objeto.
Programa fuente
Secuencial
Compilador
Escritura en lenguaje C,
Fortan, Lisp, Prolog, SQL
Detectar el paralelismo y
cuando asignar recursos.
Programa Objeto
Paralelo
Sistema de
Ejecución
Asigna recursos durante el
tiempo de corrida.
Programación paralela ...
• Para la programación de computadoras paralelas, existen 5 tipos de
estilos:
Prog. Procedural. Se basa en los conceptos de, memoria global,
asignaciones, estructuras de control secuenciales. Hay dos clases los
llamados lenguajes secuenciales (C, Fortran, Basic) y los lenguajes
concurrentes (ADA , OCCAM, C* ).
POO. Basada en objetos que se comunican por medio de pasos de
mensajes (Smalltalk, C++, OB-OCCAM).
Programación Funcional. Opera con una colección de funciones.
Existen dos clases: los lenguajes aplicativos (Lisp) y los lenguajes de
asignación única para flujo de datos.
Programación Lógica. Computación = Demostración. Prolog es el
predominante en este estilo y esta basado en las cláusulas de Horn;
calculo de predicados (Prolog).
Programación Basada en Conocimiento. Lenguajes de sistemas de
producción y los de redes semánticas.
Programación paralela ...
Programación Procedural ...
• Lenguajes Convencionales. Categoría que se desarrolló para la
programación de computadoras de Von Neumann.
• Lenguajes Concurrentes. Programación de flujo de control con
estructuras de control paralelas basadas en procesos, adicionando
mecanismos de comunicación y sincronización.Los mecanismos más
comúnmente usados son: pasos de mensajes, memoria compartida
global no protegida, memoria compartida protegida por módulos o
monitores, incluyen: señales, mensaje de sincronización, memoria
auxiliar, eventos semáforos, condiciones, colas y regiones criticas.
• El estilo SCMD (del inglés Same-Code/Multiple-Data)es el más
usado para máquinas SIMD-MIMD.
• SCMD consiste en distribuir los datos en la memoria de cada
procesador (PRAM) y ejecutar el mismo programa en cada
procesador.
Programación paralela ...
• Un programa SCMD consisten en bloques de código con llamadas
a rutinas de paso de mensajes; los procesadores ejecutan de
manera asíncrona el mismo bloque de código utilizando los datos
disponibles en su memoria local, entonces se intercambian datos
entre los procesadores; función de sincronización.1
Programador
Realiza algoritmo paralelo
para el problema particular
Programa fuente
Paralelo
Escritura en un lenguaje
Compilador
paralelo de C, Fortan, Lisp, etc.
Preserva el paralelismo y
cuando es posible asigna
recursos.
Programa Objeto
Paralelo
Sistema de
Ejecución
Asigna recursos durante el
tiempo de corrida.
Programación paralela ...
Paradigmas de la programación paralela:
• Mecanismos de procesamiento paralelo en máquinas
monoprocesadores:
–
–
–
–
Pipeline. Reducir el número de ciclos de reloj por Instrucciones. RISC.
Inclusión de más de una ALU, procesamiento simultaneo de operaciones.
Uso de DMA para dispositivos de I/O.
Multiprogramación y tiempo compartido.
• Facilidad vectorial. La mayoría de las aplicaciones de cómputo las
operaciones pueden manipularse por medio de matrices, las cuales
pueden tratarse como vectores de tamaño N, donde en un instante un
vector puede ser modificado en su totalidad.
• Máquinas con flujo de datos. Comprende tres fases:
– Selección: Instrucciones candidatas a ejecutarse.
– Discriminación: Instrucciones donde los operandos están completos pueden
ejecutarse.
– Ejecución: La operación se realiza y el resultado es usado para despertar a
otras instrucciones. Lenguajes funcionales.
Programación paralela ...
•
Máquinas de reducción. Estas consideran que una instrucción es la
aplicación de una función, la cual regresa un resultado. Esta
selecciona un instrucción cuando esta es requerida por el resultado
de otra. Se basa en el flujo de datos.
• En la mayoría de los sistemas paralelos existen primitivas para el
Control del paralelismo:
–
–
–
–
–
–
–
–
Funciones Fork y Join. Para sistemas con Granulo-Burdo.
Funciones PARBEGIN, PAREND. Para indicar un procedimiento paralelo.
Funciones COBEGIN, COEND. Para indicar un procedmiento concurrente.
Funciones de sincronización, Semáforos y monitores.
Funciones para Memoria compartida.
Funciones de Señales para sincronización.
Colas de mensajes para sincronización.
Funciones de Barrera, para asegurar que todos los procesos están listos antes
de continuar.
– Funciones de cerrojos para archivos.
Eficiencia de los sistemas Paralelos ...
• Uno de los criterios más utilizados para la evaluación de
computadoras es el desempeño (Performance). Número de
operaciones de punto flotante ejecutadas en un segundo (FLOPS).
• La máxima velocidad pico de un sistema se calcula por:
– Speed-UP = Tiempo del mejor programa secuencial / T del programa en P
Sp = T1 / Tp.
– Efficiency = Speed-UP / Numero de Procesadores (P)
Ep = Sp / p.
– Costo del programa paralelo = Tiempo * Número de procesadores.
Cp = T * p.
– Una medida de comparación es el ratio:
– Sp / Cp = Ep * Sp/T1
Aceleración Real VS Teorica
Acelaración (Sp)
50
40
30
Real
Teoría
20
10
0
Número de Procesadores (p)
Programación paralela …
• Investigar:
–
–
–
–
–
–
OCCAM
ADA
C*
Lenguajes para programación paralela
Nuevos lenguajes y tendencias
Elaborar un algoritmo Qsort Paralelo en un aquitectura
de malla