Download Modelos de programación paralela. Paradigmas de programación

PROGRAMACIÓN PARALELA
Modelos de programación paralela
Paradigmas de programación
paralela
• Tipos de paralelismo
• Paso de mensajes
• Paralelismo de datos
• Memoria compartida
Programación Paralela
Paradigmas de programación paralela
1
Tipos de paralelismo
Las variaciones entre los paradigmas están motivadas por
varios factores:
 Diferencia de esfuerzo invertido en escribir programas
paralelos. Algunos lenguajes requieren menos esfuerzo
para el programador, mientras que otros requieren menos
trabajo pero generan un código menos eficiente.
 Un determinado paradigma de programación puede ser
más eficiente que otros al programar sobre determinadas
arquitecturas paralelas.
 Distintas aplicaciones tienen diferentes tipos de
paralelismo y por tanto se han desarrollado diferentes
lenguajes de programación para explotarlos.
Programación Paralela
Paradigmas de programación paralela
2
Paralelismo implícito/explícito
• Explícito :
– El
algoritmo
paralelo
debe
especificar
explícitamente cómo cooperan los procesadores
para resolver un problema específico.
– La tarea del compilador es sencilla, en cambio la
del programador es bastante difícil.
• Implícito:
– Se usa un lenguaje de programación secuencial y
el compilador inserta las instrucciones necesarias
para ejecutar el programa en un computador
paralelo.
– El compilador tiene que analizar y comprender las
dependencias para asegurar un mapeo eficiente
en el computador paralelo.
Programación Paralela
Paradigmas de programación paralela
3
Paso de mensajes/espacio de direcciones
compartido
Espacio de direcciones compartido:
• Los programadores ven el programa como una
colección de procesos accediendo a una zona central
de variables compartidas.
• Más de un proceso podría acceder a la misma zona
compartida en el mismo instante produciendo
resultados impredecibles. Los lenguajes proporcionan
primitivas para resolver estos problemas de exclusión
mutua.
Programación Paralela
Paradigmas de programación paralela
4
Paso de mensajes/espacio de direcciones
compartido
Paso de mensajes:
• Los programadores ven su programa como una
colección de procesos con variables locales privadas y
la posibilidad de enviar y recibir datos mediante paso
de mensajes.
• Los computadores de espacio de direcciones
compartido también se pueden programar usando el
paradigma de paso de mensajes.
Programación Paralela
Paradigmas de programación paralela
5
Paso de mensajes/espacio de direcciones
compartido
• Muchos lenguajes de programación para memoria
compartida o paso de mensajes son básicamente
lenguajes secuenciales aumentados mediante un
conjunto de llamadas de sistema especiales. Estas
llamadas producen primitivas de bajo nivel para el paso
de mensajes, sincronización de procesos, exclusión
mutua, etc.
• El problema de estos lenguajes es la portabilidad entre
arquitecturas. Recientemente han aparecido librerías
como
PVM,
MPI,
OpenMP,
con
primitivas
independientes del computador.
Programación Paralela
Paradigmas de programación paralela
6
Paralelismo de datos/de control
Paralelismo de datos:
• Aplicaciones en las que los datos están sujetos a idéntico
procesamiento.
• Es más apropiado para ejecutar en máquinas SIMD.
• También se pueden ejecutar en computadores MIMD. Se requiere
sincronización global después de cada instrucción, lo que resulta en
un código ineficiente. Solución: relajar la ejecución síncrona de las
instrucciones. Modelo SPMD. Cada procesador ejecuta el mismo
programa asíncronamente.
• Los lenguajes de paralelismo de datos ofrecen construcciones de
alto nivel para compartir información y manejar concurrencia.
Programas más fáciles de escribir y comprender. Aunque el código
generado por estas construcciones no es tan eficiente como el
obtenido usando primitivas de bajo nivel.
Programación Paralela
Paradigmas de programación paralela
7
Paralelismo de datos/de control
Paralelismo de control:
• Ejecución
simultánea
de
cadenas
de
instrucciones diferentes. Las instrucciones se
pueden aplicar sobre la misma cadena de datos
aunque normalmente se aplican a cadenas de
datos diferentes.
• Adecuados para mapear en MIMD ya que el
paralelismo de control requiere múltiples
cadenas de instrucciones.
Programación Paralela
Paradigmas de programación paralela
8
Paso de mensajes
Extensiones básicas: Son extensiones en los lenguajes secuenciales
para soportar el paso de mensajes.
 Existen dos primitivas básicas de comunicación: SEND y
RECEIVE.
La forma general de send es:
SEND (message, messagesize, target, type, flag)
– message contiene los datos que se envían,
– messagesize indica el tamaño en bytes,
– target es la etiqueta del procesador o procesadores destino,
– type es una constante con la que se distingue entre varios
tipos de mensajes, y
– flag indica si la operación del SEND es bloqueante o nobloqueante.
Programación Paralela
Paradigmas de programación paralela
9
Paso de mensajes
La primitiva RECEIVE lee un mensaje del buffer de comunicación
en la memoria.
Su forma general es:
RECEIVE (message, messagesize, source, type, flag)
– messsage indica el lugar donde se almacenan los datos,
– messagesize indica el número máximo de bytes a poner en
mensaje,
– source indica la etiqueta del procesador cuyo mensaje se va a
leer,
– type especifica el tipo de mensaje que se va a leer. Puede
haber más de un mensaje en el buffer de comunicación de los
procesadores fuente. El parámetro type selecciona un
determinado mensaje para leer,
– flag especifica si la operación de recibir es bloqueante o no
bloqueante.
Programación Paralela
Paradigmas de programación paralela
10
Paralelismo de datos
• Lenguajes de paralelismo de datos: facilitar al programador
la tarea de expresar el paralelismo disponible en un
programa de manera independiente de la arquitectura.
• Características:
– Se genera una sola cadena de instrucciones.
– Ejecución síncrona de instrucciones. Más fácil escribir y depurar
programas de paralelismo de datos puesto que los bloqueos son
imposibles.
– El programador especifica el paralelismo en el código.
– Asocia un procesador virtual con una unidad fundamental de
paralelismo. El programador expresa la computación en términos de
las operaciones realizadas por los procesadores virtuales.
– Permite que cada procesador tenga acceso a las posiciones de
memoria de otros procesadores.
Programación Paralela
Paradigmas de programación paralela
11
Paralelismo de datos
– Los compiladores para los lenguajes de paralelismo de datos deben
mapear los procesadores virtuales en procesadores físicos, generar
código para comunicar datos y esforzarse para la ejecución síncrona
de instrucciones.
– Los procesadores virtuales son emulados por procesadores físicos.
Si el número de procesadores virtuales es mayor que el número de
procesadores físicos, cada procesador físico emula varios
procesadores virtuales.
– Algunos lenguajes de paralelismo de datos contienen primitivas que
permiten al programador especificar el mapeo deseado de los
procesadores virtuales en los físicos.
Programación Paralela
Paradigmas de programación paralela
12
Paralelismo de datos
• Ejemplo: C*
Lenguaje de programación para paralelismo de datos.
Extensión del lenguaje C, diseñado por Thinking Machines
Corporation para el computador CM-2.
Incluye un método para describir el tamaño y la forma de los
datos paralelos y crear variables paralelas. Incluye
operadores y expresiones para los datos paralelos.
Programación Paralela
Paradigmas de programación paralela
13
Paralelismo de datos
• Variables:
– variables escalares: idéntica a una variable ordinaria. Se asignan
en el host.
– variables paralelas:
Se asignan en todos los nodos.
Tienen tantos elementos como número de procesadores.
Una variable paralela tiene una "forma" además de un tipo.
Una "forma" es una plantilla para los datos paralelos, o sea una
forma de configurar los datos lógicamente.
Define cuántos elementos paralelos existen y cómo están
organizados.
Una "forma" tiene un número de dimensiones, rango, con un
número de procesadores o posiciones en cada dimensión.
Programación Paralela
Paradigmas de programación paralela
14
Paralelismo de datos
shape [1024] ring
shape [1024][1024] mesh
int flag
int ring:a
int mesh:b
flag
a
b
Programación Paralela
Paradigmas de programación paralela
15
Paralelismo de datos
• C* no permite que el programador especifique
explícitamente el mapeo virtual a físico. C* mapea los
procesadores virtuales en procesadores físicos de
forma que los procesadores virtuales vecinos se
mapean en procesadores físicos vecinos.
• C* permite especificar a través de qué dimensiones de
la "forma" se hacen comunicaciones más a menudo. El
compilador usa esta información para reducir costos de
comunicación.
• Después de que se ha especificado una forma, se
pueden declarar variables paralelas de esa "forma".
Las variables paralelas tienen un tipo, una clase de
almacenamiento, y una forma.
Programación Paralela
Paradigmas de programación paralela
16
Paralelismo de datos
• Operaciones paralelas
– Si los operandos de una operación son escalares, el código C* es
igual que el código C y la operación se realiza en el host.
– Si los operandos son variables paralelas,
x+=y donde x e y son variables paralelas. Esta asignación añade
el valor de y en cada posición de la "forma" al valor de x en la
posición correspondiente de la forma. Todas las sumas tienen
lugar en paralelo. x e y deben ser de la misma "forma".
x=a, donde a es una variable escalar, el valor de a se almacena en
cada posición de x. Esto es similar a una operación de broadcast.
a =[4]x es válida y asigna a a el valor de x de la cuarta posición de
la forma.
a+=x suma todos los valores de x y los almacena en a.
Programación Paralela
Paradigmas de programación paralela
17
Paralelismo de datos
• Comunicación. C* soporta
comunicación interprocesador:
dos
métodos
de
– comunicación en red: las variables paralelas del
mismo tipo pueden comunicarse en patrones
regulares. Es bastante eficiente.
– comunicación general: el valor de cualquier elemento
de una variable paralela se puede enviar a cualquier
otro elemento aunque las variables paralelas no sean
de la mismo "forma".
Programación Paralela
Paradigmas de programación paralela
18
Espacio de direcciones compartido
• Primitivas para asignar variables compartidas.
Existen dos tipos de variables: compartidas (shared) y
locales (private)
• Primitivas para la exclusión mutua y sincronización.
Una sección crítica contiene código que sólo puede ser
ejecutado por un procesador en un momento determinado.
Los lenguajes proporcionan llaves (locks) para ayudar al
programador a cumplir la exclusión mutua en la ejecución
de secciones críticas.
Las primitivas de sincronización de barreras (barrier
synchronization) se usan cuando los procesos necesitan
sincronizarse antes de que acabe la ejecución. Cada
proceso espera en la barrera a los otros procesos, y
después de la sincronización todos los procesos continúan
con su ejecución.
Programación Paralela
Paradigmas de programación paralela
19
Espacio de direcciones compartido
• Primitivas para la creación de procesos
Se realiza mediante una llamada al sistema que crea
procesos idénticos al proceso padre. Estos procesos
comparten las variables declaradas "compartidas" por los
procesos padre así como las llaves declaradas e inicializadas
por los procesos padre. En la mayoría de computadores de
espacio de direcciones compartido, esta operación se llama
fork. Cuando todos los subprocesos terminan, se mezclan
usando otra primitiva, normalmente llamada join.
En vez de crear procesos al principio de la ejecución,
podemos tener un solo proceso, llamado proceso maestro.
Cuando el maestro necesita realizar una tarea en paralelo,
crea un número predeterminado de procesos, llamados
procesos esclavos. Cuando la tarea se completa, los
procesos esclavos terminan y devuelven el control al proceso
maestro.
Programación Paralela
Paradigmas de programación paralela
20
Compiladores paralelizantes
• Programa secuencial. El compilador se encarga de
paralelizarlo.
• Normalmente en sistemas de memoria compartida.
• Paralelizan bucles: dividen el trabajo en los bucles entre los
distintos procesadores
• Si puede haber dependencia de datos no paraleliza:
para i=1 to n
a[i]=b[i]+a[i-1]
finpara
• Se puede forzar la paralelización con opciones de
compilación, o con directivas (OpenMP).
• Generan ficheros con información de bucles paralelizados y
no paralelizados, y el motivo.
Programación Paralela
Paradigmas de programación paralela
21
Lenguajes paralelos de alto nivel
• Primitivas que debería contener un lenguaje paralelo:
– Paralelización de bucles,
– Pipeline,
– Crear grupo de procesos, …
• Asociar a cada constructor (esqueleto) una función de coste.
• Mapeo de los procesos generados en función de la función
de coste.
• Ejemplo mpC
Librerías para campos específicos de
trabajo
• Desarrollar librerías para campos donde más se usa la
computación paralela, con capacidades de autooptimización:
el usuario llama a la rutina y esta decide cuántos y qué
procesadores usar, la distribución de datos, …
• Álgebra lineal, transformada rápida de Fourier, …
Programación Paralela
Paradigmas de programación paralela
22