PDF de programación - Programación paralela - Computación de Alta Performance

Computación de Alta Performance

Curso 2009

PROGRAMACIÓN PARALELA

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

PROGRAMACIÓN PARALELA

• Modelo de programación paralela.
• Problemas con la computación paralela –

distribuida.

• Técnicas de programación paralela.
• Paralelizando aplicaciones existentes.
• Paralelizando aplicaciones existentes.
• Modelos de comunicación entre procesos.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO DE

PROGRAMACIÓN PARALELA
PROGRAMACIÓN PARALELA

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO DE PROGRAMACIÓN PARALELA

• Programación en máquina de Von Neumann

– Secuencia de operaciones (aritméticas, read/write

de memoria, avance de PC).

– Abstracciones de datos e instrucciones.
– Técnicas de programación modular.

• Programación en máquina paralela
• Programación en máquina paralela

– Incluye complicaciones adicionales.

– Multiejecución simultánea.
– Comunicaciones y sincronización.

– La modularidad pasa a ser fundamental, para manejar

la (potencialmente) enorme cantidad de procesos en
ejecución simultánea.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• El paradigma de diseño y programación difiere del

utilizado para diseñar y programar aplicaciones
secuenciales.
– Una buena estrategia de división del problema puede

determinar la eficiencia de un algoritmo paralelo.

– Es importante considerar la disponibilidad de

hardware.
hardware.

• Respecto a los mecanismos de comunicación entre
procesos, existen dos paradigmas de computacion
paralela
– MEMORIA COMPARTIDA.
– PASAJE DE MENSAJES.
– Existen también MODELOS HÍBRIDOS, que combinan ambas

técnicas.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

NIVELES DE APLICACIÓN DEL PARALELISMO

• El paralelismo puede aplicarse:

1. A nivel intrainstrucción (hardware, pipelines).
2. A nivel interinstrucción (SO, optimización de

código, compilador).

3. A nivel de procedimientos o tareas.

– Algorítmico tareas.

4. A nivel de programas o trabajos.
4. A nivel de programas o trabajos.

– Algorítmico funcional.

• Los niveles 1 y 2 corresponden a cursos de

arquitectura de sistemas y sistemas operativos.

• A lo largo del presente curso, básicamente

consideraremos los niveles 3 y 4 de aplicación de
las técnicas de paralelismo (enfocado al diseño y
programación de algoritmos paralelos).

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• GRAFOS DIRIGIDOS ACICLICOS (ADGs)

– Los nodos representan tareas o procesos (partes de

código que ejecutan secuencialmente).

– Als aristas representan dependencias (algunas tareas

preceden a otras).

• El problema a resolver se divide en tareas a

ejecutar cooperativamente en múltiples
ejecutar cooperativamente en múltiples
procesadores.

• Se debe:

– Definir tareas que pueden ejecutar concurrentemente.
– Lanzar la ejecución y detener la ejecución de tareas.
– Implementar los mecanismos de comunicación y

sincronización.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• Las dependencias entre tareas imponen

limitaciones al nivel de paralelismo.
– Dependencia de datos.
– Sincronizaciones.

• El camino crítico en el grafo de
• El camino crítico en el grafo de

tareas permite determinar el mínimo
tiempo posible de ejecución.
– Técnicas de IO permiten determinar

niveles de paralelismo (Gantt,
planificación).

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

HeNCE, herramienta gráfica para modelar procesos paralelos

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• No siempre es una buena decisión partir de un

algoritmo secuencial (“paralelizar” una
aplicación). En ocasiones será necesario diseñar un
nuevo algoritmo muy diferente.

• Resumiendo las etapas de diseño de aplicaciones

paralelas :
paralelas :
– Identificar el trabajo que puede hacerse en paralelo.
– Dividir el trabajo y los datos entre los procesadores.
– Resolver los accesos a los datos, las comunicaciones

entre procesos y las sincronizaciones.

DESCOMPOSICIÓN – ASIGNACIÓN – ORQUESTACIÓN – MAPEO

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• DESCOMPOSICIÓN

– Identifica concurrencia y decide el nivel y la forma

en la cual se explotará.

– Cantidad de tareas.
– Tareas estáticas o dinámicas.
– Criterios de división y utilización de recursos.

• ASIGNACIÓN

– Asigna datos a procesos
– Criterios de asignación:
– Estáticos o dinámicos.
– Balance de cargas.
– Reducción de costos de comunicación y

sincronización.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• ORQUESTACIÓN

– Decisión sobre parámetros de arquitectura, modelo de

programación, lenguaje o biblioteca a utilizar.

– Estructuras de datos, localidad de referencias.
– Optimizar comunicación y sincronización.

• MAPEO (SCHEDULING)

– Asignación de procesos a procesadores.
– Criterios de asignación:

– Performance.
– Utilización.
– Reducción de costos de comunicación y

sincronización.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO CONCEPTUAL DE PARALELISMO

• Los mecanismos para definir, controlar y sincronizar

tareas deben formar parte del lenguaje a utilizar o
ser intercalados por el compilador.

• Estos mecanismos deben permitir especificar:

– El control de flujo de ejecución de tareas.
– El particionamiento de los datos.

• Algunos ejemplos
• Algunos ejemplos

– Definición y ejecución de tareas: parbegin-parend (Pascal

concurrente), task (Ada), spawn (PVM), fork & join (C).

– Comunicación y sincronización: semáforos, monitores, barreras
(memoria compartida), mensajes sincrónicos (rendezvouz Ada)
y mensajes asincrónicos (C, PVM, MPI),(memoria distribuida).

– El particionamiento de los datos es una tarea usualmente

asignada al diseñador del algoritmo paralelo.

• El modelo se complica por características peculiares

de la computación paralela – distribuida.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO PARALELO-DISTRIBUIDO: PROBLEMAS

• CONFIABILIDAD

– Varios componentes del sistema pueden fallar:

– nodos, interfases, tarjetas, caches, bridges,

routers, repeaters, gateways, medios físicos.

– Problemas de utilizar equipamiento no dedicado:

– problemas de uso y tráfico (propio y ajeno), etc.
– no repetibilidad de condiciones de ejecución.
– no repetibilidad de condiciones de ejecución.

• NO DETERMINISMO EN LA EJECUCIÓN

– los programas tienen muchos estados posibles.
– adiós a “diagramas de flujo (en el tiempo)” para

especificar secuencias de control.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO PARALELO-DISTRIBUIDO: PROBLEMAS

• SEGURIDAD

– Acceso a equipos remotos.
– Datos distribuidos.

• DIFICULTAD DE ESTIMAR LA PERFORMANCE FINAL DE

UNA APLICACIÓN
– Como consecuencia del no determinismo en la

ejecución.
ejecución.

– Criterios estadísticos.

• DIFICULTAD DE TESTEAR/DEBUGGEAR PROGRAMAS

– difícil reproducir escenarios (múltiples estados,

asincronismo).

– datos y procesos no centralizados (un debugger en

cada nodo).

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO PARALELO-DISTRIBUIDO: PROBLEMAS

DEJA DE EXISTIR EL CONCEPTO DE “TIEMPO UNIVERSAL”

Nodo A

Nodo B

Ocurre evento X

Se reporta X al
Se reporta X al

nodo B

Se toma conocimiento

del evento X

Ocurre evento Y

Se reporta Y al

nodo A
nodo A

Se toma conocimiento

del evento X

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

MODELO PARALELO-DISTRIBUIDO: PROBLEMAS

• INCOMPATIBILIDADES ENTRE PRODUCTOS Y PLATAFORMAS

(para sistemas heterogéneos)

– Sistemas Operativos: AIX, Solaris, Linux, Windows

(NT, 2K, XP, etc.), OSF, VMS, etc.
(NT, 2K, XP, etc.), OSF, VMS, etc.

– Protocolos de comunicaciones: TCP/IP, DEC-NET, IPX,

NetBEUI, etc....

– Herramientas de software: PVM, MPI, C, LINDA,

etc....

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

TÉCNICAS DE

PROGRAMACIÓN PARALELA
PROGRAMACIÓN PARALELA

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

TÉCNICAS DE PROGRAMACIÓN PARALELA

• Introducción
• Técnica de descomposición de dominio
• Técnica de descomposición funcional
• Técnicas de paralelismo optimista
• Técnicas Híbridas
• Técnicas Híbridas
• Ejemplo

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

TÉCNICAS DE PROGRAMACIÓN PARALELA

• Se analizarán las técnicas de DESCOMPOSICIÓN

o PARTICIONAMIENTO, que permiten dividir un
problema en subproblemas a resolver en
paralelo.

• El objetivo primario de la descomposición

será dividir en forma equitativa tanto los
cálculos asociados con el problema como los
datos sobre los cuales opera el algoritmo.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

TÉCNICAS DE PROGRAMACIÓN PARALELA

• ¿ Cómo lograr el objetivo de la descomposición ?

– Definir al menos un orden de magnitud más de tareas

que de procesadores disponibles (utilización de
recursos)

– Evitar cálculos y almacenamientos redundantes.
– Generar tareas de tamaño comparable.
– Generar tareas escalables con el tamaño del
– Generar tareas escalables con el tamaño del

problema.

– Considerar varias alternativas de descomposición,

en caso de ser posible.

• Según se enfoque principalmente en la

descomposición de datos o de tareas, resultará
una técnica diferente de programación paralela.

COMPUTACIÓN DE ALTA PERFORMANCE – 2009

PROGRAMACIÓN PARALELA

DESCOMPOSICIÓN DE DOMINIO

• Se concentra en el particionamiento de los

datos del problema (data parallel).

– Se trata de dividir los datos en piezas

pequeñas, de (aproximadamente) el mismo tamaño.

• Luego se dividen los cálculos a realizar

– Asoc