Programación de algoritmos paralelos con PVM: diseño y configuración

ASIGNATURA

Ampliación de Sistemas Operativos

GRADO EN INGENIERÍA INFORMÁTICA

TEMA 3

Programación de algoritmos paralelos. Autor: Lorena Calavia Domínguez

UEMO universidad online UEMC Universidad Europea Miguel de Cervantes

TEMA 3

Programación de algoritmos paralelos

Unidad didáctica.

Tema 3: Programación de algoritmos paralelos

INDICE

1. PRESENTACION
2. OBJETIVOS.
3. ESQUEMA
4. CONTENIDO
1. Introducción a la programación paralela
2. Etapas del diseño de un algoritmo paralelo
3. Granularidad
4. Algoritmos paralelos
5. PVM (Parallel Virtual Machine).
1. Estructura de un programa con PVM.
2. Configuración de un sistema PVM con UBUNTU
3. Ejemplos PVM
1. Ejemplo I: Saludo
2. Ejemplo Il: Hola
3. Ejemplo III: Calculadora
5. RESUMEN
6. BIBLIOGRAFIA

UEMOP universidad online

TEMA 3

Programación de algoritmos paralelos

I. PRESENTACION

Este tema comienza con una introducción a la programación paralela que destaca la importancia de comprender el problema que se desea resolver y determinar si realmente se puede paralelizar ya que paralelizar no siempre implica una mejora en la velocidad de ejecución y es importante evaluar si la mejora compensará el esfuerzo a realizar.

Posteriormente se habla de las etapas de diseño en caso de que el algoritmo sea paralelizable. Uno de los primeros pasos es dividir el problema en "trozos" discretos de trabajo que se pueden distribuir en varias tareas. En este punto entra el concepto de granularidad: cómo se divide el problema en muchas tareas pequeñas o pocas tareas grandes. Cada una de estas opciones va a tener sus ventajas e inconvenientes y de manera general, la mejor solución va a ser una intermedia. Una vez definidas las tareas, es necesario establecer las relaciones de comunicación entre ellas para coordinarlas y luego asignar las tareas a los distintos nodos de computación.

Para programar un algoritmo paralelo existen librerías paralelas como Open MP, MPI y PVM que facilitan el trabajo. MPI es de creación estática, mientras que PVM permite la creación y destrucción dinámica de procesos durante la ejecución del programa. En nuestro caso, se estudiará PVM para poder desarrollar nuestros propios algoritmos de ejecución paralela.

El tema se va a dividir en 5 puntos:

• Introducción a la programación paralela
• Etapas del diseño de un algoritmo paralelo
• Granularidad
• Algoritmos paralelos
• PVM (Parallel Virtual Machine)

No es necesario tener conocimientos previos para tener éxito en el estudio y superación de este tema, aunque sí se recomienda tener conocimientos de programación en C.

UEMOP universidad online

TEMA 3

Programación de algoritmos paralelos

II. OBJETIVOS.

• Comprender cómo el paralelismo puede mejorar la eficiencia en la ejecución de algoritmos y saber que es necesario evaluar si la mejora compensa el esfuerzo a realizar.
• Aprender cómo llevar a cabo el diseño de un algoritmo paralelo
• Comprender la diferencia entre granularidad fina y granularidad gruesa y cómo elegir la mejor opción.
• Conocer los lenguajes de programación y herramientas habituales para desarrollar programas paralelos.
• Saber cómo instalar y configurar un entorno de programación paralela y ser capaz de desarrollar algoritmos haciendo uso del mismo.

III. ESQUEMA

El tema se va a estructurar de la siguiente manera:

Programación de algoritmos paralelos

Introducción a la programación paralela

Etapas del diseño de un algoritmo paralelo

Granularidad

Algoritmos paralelos

PVM (Parallel Virtual Machine)

UEMOP universidad online

TEMA 3

Programación de algoritmos paralelos

IV. CONTENIDO

1. Introducción a la programación paralela

Sin duda, el primer paso para desarrollar software en paralelo es comprender primero el problema que se desea resolver en paralelo. Si está comenzando con un programa en serie, esto significa comprender también el código existente.

Antes de dedicar tiempo a intentar desarrollar una solución paralela para un problema, habría que determinar si el problema es o no uno que realmente se puede paralelizar. El nivel de paralelismo va a depender de la independencia de las tareas del problema.

? ¿Si dividimos un programa en n trozos y lo lanzamos en un sistema de n procesadores paralelos, el programa se ejecutaría n veces más rápido que su equivalente secuencial en un solo procesador?

¿Cuándo es conveniente el paralelismo? Paralelizar un programa no implica siempre una mejora o incremento en la velocidad de su ejecución. Lo primero que hay que hacer es identificar las partes independientes de un programa y luego habrá que alterar el código para que este se ejecute en paralelo. En este punto tenemos que evaluar si la mejora del sistema va a compensar el esfuerzo a realizar.

En caso de que se puede paralelizar, en el diseño de un algoritmo paralelo hay que tener en cuenta:

• Concurrencia: al existir pasos, instrucciones, procesos que se ejecutan a la vez, debe existir una comunicación y una sincronización entre los mismos.
• Asignación de datos y código a cada unidad de proceso: ¿ cómo repartir cada tarea y cada bloque de datos entre los distintos procesadores, equipos, nodos o unidades de proceso?
• Escalabilidad: si el algoritmo está bien diseñado, al aumentar el hardware (más nodos), también debería aumentar la eficacia y el rendimiento. (Esta tarea es complicada).

UEMOP universidad online

TEMA 3

Programación de algoritmos paralelos

2. Etapas del diseño de un algoritmo paralelo

Uno de los primeros pasos en el diseño de un programa paralelo es dividir el problema en "trozos" discretos de trabajo que se pueden distribuir en varias tareas. Esto se conoce como descomposición o partición.

Hay dos formas básicas de dividir el trabajo computacional entre tareas paralelas: descomposición de dominio y descomposición funcional.

En la descomposición de dominio, se separan los datos asociados a un problema y luego cada tarea paralela trabaja en una parte de los datos.

En la descomposición funcional, la atención se centra en el cálculo que se va a realizar en lugar de en los datos manipulados por el cálculo. El problema se descompone de acuerdo al trabajo que se debe realizar. Luego, cada tarea realiza una parte del trabajo general.

Una vez establecidas las tareas hay que definir las relaciones de comunicación entre tareas para coordinarlas y después asignar las tareas a los nodos de computación

Características Arquitectura Descomposición Asignación Cálculo a paralelizar Descripción tareas + Estructura de Comunicación Correspondencia tareas-procesos

Figura 1. Etapas del diseño de un algoritmo paralelo

3. Granularidad

En computación paralela, la granularidad determina el grado de descomposición de las tareas y va a ser una medida cualitativa de la relación entre computación y comunicación.

Los períodos de cómputo normalmente están separados de los períodos de comunicación por eventos de sincronización.

Tenemos diferentes opciones al dividir el problema en tareas:

• Muchas tareas muy pequeñas (granularidad fina)

UEMOD universidad online

TEMA 3

Programación de algoritmos paralelos

• Pocas tareas, grandes (granularidad gruesa)

En una granularidad fina se realizan cantidades relativamente pequeñas de trabajo lo que facilita el balanceo de carga, pero implica una gran sobrecarga de comunicación y menos oportunidades para mejorar el rendimiento. Si la granularidad es demasiado fina, es posible que la sobrecarga requerida para las comunicaciones y la sincronización entre tareas suponga más tiempo que el cálculo.

En una granularidad gruesa se realizan cantidades relativamente grandes de trabajo computacional entre eventos de comunicación/sincronización con lo que habra una alta relación computación/comunicación implicando más oportunidades para aumentar el rendimiento, pero será más difícil de equilibrar la carga de manera eficiente

¿Cuál de las dos es el mejor?

La granularidad más eficiente depende del algoritmo y del entorno de hardware en el que se ejecuta. En la mayoría de los casos, la sobrecarga asociada con las comunicaciones y la sincronización es alta en relación con la velocidad de ejecución, por lo que es ventajoso tener una granularidad gruesa pero el paralelismo de grano fino puede ayudar a reducir los gastos generales debido al desequilibrio de carga.

T = Tiempo de proceso Tiempo de comunicación Nº de tareas

zona óptima

Figura 2. Granularidad óptima

4. Algoritmos paralelos

En un algoritmo paralelo lo habitual es que haya un reparto de tareas y datos para un procesamiento paralelo de los mismos y una etapa final de reunion y combinación de las diferentes respuestas para obtener un resultado final único.

Hay diferentes formas de organizar un algoritmo paralelo:

• organización maestro-esclavo

UEMOP universidad online

TEMA 3

Programación de algoritmos paralelos

• organización nodos iguales [con líder]

Los lenguajes de programación para máquinas paralelas más usados son C y Fortran.

Existen además librerías paralelas como Open MP/MPI/PVM (máquina virtual paralela) que facilitan el trabajo.

MPI es de creación estática de manera que todos los procesos son especificados antes de la ejecución. En este caso el sistema ejecutará con un número fijo de procesos cuya creación se realizará a nivel de la línea de comando.

En PVM la creación es dinámica de manera que los procesos pueden ser creados y sus ejecuciones iniciadas durante la ejecución de otros procesos. En este caso los procesos pueden ser destruidos dinámicamente y tanto la creación como la destrucción se realiza mediante constructores o llamadas a librerías que provean la funcionalidad paralela y puede ser realizada condicionalmente, por lo que el número de procesos puede variar durante la ejecución de un programa.

5. PVM (Parallel Virtual Machine)

PVM es una librería de rutinas de dominio público para programación paralela mediante el paso de mensajes. Las rutinas de PVM comunican procesos que pueden ejecutarse en el mismo o en diferentes procesadores. Está pensada para ejecutarse en plataformas heterogéneas.

Si los procesos residen en el mismo procesador, se comunicarán a través del sistema operativo, sino se comunican a través de la red de interconexión.

Procesador 1 Red de interconexión Pla pvmd 1 P1b Procesador 2 P2 pvmd 2 Procesador n Pn pvmd n

Figura 3. PVM

UEMOP universidad online